在Java中循环链表实现(Circular LinkedList implementation in

这是一个任务。 我要创建一个循环链表，并删除列表中的每个第三个数字。 当我的程序到达列表的末尾应该回到头部，直到只有一个人数仍然继续处理。

我在网上搜索和其他一些参考书，但没能解决我的问题。 大多数我发现引用的说的东西，如：

除了一个事实，即圆形名单没有结束，他们是完全一样常规列表

或者（在我的书取）：

单链接列表循环链接，如果最后一个节点的继任者是第一

但是，这些不告诉该怎么做。 我一直在使用一些代码，我在此网站上发现也试过，但没有明确的任何东西。

我能得到尽可能创建列表（我不知道这是否是一个循环链表），并显示它，但元素的顺序是奇怪的：

• 如果列表中有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

Answer 1:

当您添加一个新的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());
}

Answer 2:

您add方法后直接插入元素first ，如果第一已设置：

first.next = new Node(e, first.next);

这导致了观察到的行为。

你需要保持在列表的最后一个元素的轨道，并添加新的元素last.next如果你想新的元素在列表的末尾添加。 这样做的一个方法就是保存到列表类的成员变量的最后一个元素的引用，另一个是，直到找到连接到节点遍历列表first这将是最后一个节点。

文章来源: Circular LinkedList implementation in Java