Java中的循环LinkedList

Question

我正在读一本书，重新整理了我的数据结构，它提出的一个问题是不使用“第一个”和“最后一个”指针来构建一个循环的单链表，而是通过使用一个引用来访问它。当前”。我不确定我是否理解这个问题，我一直以为我至少需要第一个或最后一个。这是我的实现，但是它具有“
first”，不确定如何解决。您能否评论一下如何调整代码以消除对第一代码的依赖？

class Link {
    public int iData;              
    public Link next;

    public Link(int id) { // constructor
        iData = id;                         
    }

    public void displayLink() {
        System.out.print(iData + " ");
    }
}  // end class Link

然后是列表本身：

public class CircularLinkedList {
    private Link first;
    private Link current;

    public Link getCurrent(){
        return current;
    }

    public void setCurrent(int data){

    }

    public void advance(){
        current = current.next;
    }

    public void insert(int data) {
        Link newLink = new Link(data);
        if (first == null) { 
            first = current = newLink;
        } else {
            current.next = newLink;
        }
        current = newLink;
        newLink.next = first;
    }
    ...
}

Answer 1

如果您有一个循环链表，则每个节点都指向连续循环中的下一个节点。因此，没有最后也没有第一。在这种情况下，您只需要将一个指针指向数据结构（该问题称为“当前”），因为您可以遍历整个列表，直到返回起点为止。

一个节点可能看起来像这样：

public class ListNode<T> {
    private T element;
    private ListNode<T> next;
}

因此，在这种环境下，当您将第一个节点添加到列表中时，它的“下一个”指针将指向自身。当您添加第二个节点时，每个“下一个”指针将指向另一个。当您添加第三个节点时，它们将分别指向下一个节点，并且大概以某种方式对其进行了排序。添加的每个其他节点将插入循环中的适当位置。

像这样的数据结构的一个很好的用法是可以每天或每小时重复一次的时间表。所有事件都可以存储在循环列表中，并且“当前”指针始终指向下一个计划的位置。

显然，当搜索这样的列表时，您需要保留对第一个节点的引用。这是您知道是否搜索了整个列表的唯一方法，因为它没有以空的“ next”指针结尾。

编辑： 正如下面的（大量）注释中所述，对于插入操作，“尾巴”指针似乎是一个非常好的主意。这是我发布的原始方法，现已重命名insertAfter：

public void insertAfter(int data) {
    Link newLink = new Link(data);
    if (current == null) { 
        newLink.next = newLink;
        current = newLink;
    } else {
        newLink.next = current.next;
        current.next = newLink;
    }
}

尾指针将始终指向列表的最后一个节点。这也是第一个节点之前的节点，因为列表是循环的。因此，(tail.next == current)在操作指针时一定要维护。这是新的插入方法：

public void insert(int data) {
    Link newLink = new Link(data);
    if (current == null) { 
        current = newLink;
        tail = newLink;
        newLink.next = newLink; // tail.next = current!
    } else {
        tail.next = newLink; // tail.next = current!
        newLink.next = current;
        current = newLink; // tail is unchanged, newLink is current
    }
}

插入值应该正确地使它们混乱。为了在添加时保持顺序，add应使用以下方法：

public void add(int data) {
    this.insert(data);
    this.advance();
}

这是的代码advance：

public void advance() {
    if (current != null) {
        tail = current;
        current = tail.next; // tail.next = current!
    }
}

像这样用来创建列表时…

list1.add(1);
list1.add(2);
list1.add(3);
list2.insert(3);
list2.insert(2);
list2.insert(1);

…两个列表都按1-2-3顺序排列，其中1作为当前顺序。