Java中的循环LinkedList实现
这是一项任务。 我必须创建一个循环链表并删除列表中的每三个数字。 当我的程序到达列表的末尾时，它应该返回到头部并继续该过程，直到只剩下一个数字。
我在网上搜索了一些其他的参考书，但无法解决我的问题。 我发现的大多数参考文献都说如下：
除了循环列表没有结束这一事实外，它们与常规列表完全相同
或（取自我的教科书）：
如果最后一个节点的后继节点是第一个节点，则单个链接列表循环链接
但这些并没有说明如何做到这一点。 我也试过使用我在这个网站上找到的一些代码，但这并没有清楚。
我可以创建一个列表（我不知道它是否是循环链表）并显示它，但元素的顺序很奇怪：
- 如果列表有6个数字，则列表为1,6,5,4,3,2。
- 如果列表有8个数字，则列表为1,8,7,6,5,4,3,2。
如果没有正确的列表，我可以正确删除。 以下代码有什么问题：
public class LastNumberDemo { public static void main(String[] args) { LastNumberNode ll=new LastNumberNode(); System.out.println("how long is the list: "); Scanner keyboard = new Scanner(System.in); int input = keyboard.nextInt(); if(input<=0) { System.out.println("no number to creat list"); } if(input==1) { System.out.println("The Last number is 1."); } else { String[] n=new String[input]; for(int index=0; index<n.length; index++) n[index]=Integer.toString(index+1); for(String e:n) ll.add(e); System.out.print("The list contains: \n"); ll.print(); System.out.print("\nThe last number is: "); ll.remove(); ll.print(); } } } //The circular linked list class class LastNumberNode{ private class Node{ String value; Node next; Node(String val, Node n){ value = val; next = n; } Node(String val){ value=val; next=null; } } //This brace was missing - Edd private Node first; public LastNumberNode(){ first = null; } public boolean isEmpty(){ return first == null; } public int size(){ int count = 0; Node p = first.next; while (p != first){ count ++; p = p.next; } return count; } public void add(String e) { Node p=new Node(e); if(first==null){ first=p; first.next=first; } else{ first.next=new Node(e,first.next); } } public void remove(){ while(size()>0){ Node target=first.next.next; Node temp=first; target=target.next; last.next=temp; first=target; } } public void print(){ Node ref=first; for(int index=-1; index<size();index++) System.out.print(ref.value+" "); ref=ref.next; } } //Extra brace removed - Edd
当您将新Node添加到列表中时，将新Node添加到第二个位置（ first.next指向新添加的节点），但是这个新添加的节点first作为其下一个节点，其余列表未引用（因此垃圾收集和销毁）。 使用你的add方法，你的列表不可能包含0,1或2 Node的任何东西。 将新Node添加到列表中间有点奇怪; 要么将它添加到前面（ newnode.next = first; first = newnode; last.next = first; ），要么保持对列表后面的引用（正如其他人建议的那样），并将其添加到那里。
就个人而言，我重构了LastNumberNode类，以便它具有以下操作链表的方法：
-
private void addNode(Node node) -
private void removeNode(Node node) -
private Node findNode(Node nextNode)
如果您维护对列表中最后一个节点的引用，那么您的addNode(Node node)方法可能类似于以下内容：
if(isEmpty()) { first = node; last = node; } else { Node tail = last; tail.next = node; node.next = first; last = node; }
removeNode(Node node)基于以下内容：
Node prevNode = findNode(node); if(node == first) { first = node.next; last.next = first; } else if(node == last) { prevNode.next = first; last = prevNode; } else { prevNode.next = node.next; }
如果我要实现这个，我可能会使用这种方法将列表缩减为单个Node ：
public String reduceList() { Node curNode = first; while(first != last) { removeNode(curNode.getNext().getNext()); curNode = curNode.getNext().getNext(); } return first.getValue(); }
最后一点，我不打算用序号填充数组，然后走它以将元素添加到列表中。 我会直接找到类似下面的内容：
for(int i = 1; i <= input; i++) { linkedlist.add(new Integer(i).toString()); }
如果已经设置了first一个元素，则add方法first直接插入元素：
first.next = new Node(e, first.next);
这导致观察到的行为。
如果要在列表末尾追加新元素，则需要跟踪列表的最后一个元素并将新元素添加为last.next 。 一种方法是简单地保存对列表类的成员变量中的最后一个元素的引用，另一种方法是遍历列表，直到找到链接到first一个节点的节点为止。