Java中的循环LinkedList

Question

我通过阅读一本书来刷新我的数据结构,其中一个问题是通过不使用"第一"和"最后"指针来构建循环单链接列表,而是允许通过使用一个引用来访问它当前".我不确定我是否理解这个问题,我一直以为我至少需要第一个或最后一个.这是我的实现,但它有"第一",不知道如何解决它.您能评论我如何调整我的代码以消除对第一个的依赖吗？

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;
}

因此,在这种环境中,当您将第一个节点添加到列表中时,它的"下一个"指针将指向自身.添加第二个节点时,每个"下一个"指针将指向另一个节点.当你添加第三个节点时,它们将分别指向下一个节点,并且可能是以某种方式对它进行排序.添加的每个附加节点将插入循环中的适当位置.

像这样的数据结构的良好用法是每天或每小时重复的计划.所有事件都可以存储在循环列表中,"当前"指针始终指向下一个计划的任何一个.

显然,在搜索这样的列表时,您需要保留对第一个节点的引用.这是你可以知道你是否已经搜索整个列表的唯一方法,因为它不会以空的"下一个"指针结束.

编辑:正如下面(广泛)评论中所讨论的,对于插入操作,"尾部"指针似乎是一个非常好的主意.这是我发布的原始方法,已重命名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为当前.