java Java中的循环链表

Circular LinkedList in Java

提问by sam2015

I am brushing up on my data structures by reading a book and one of the questions it asks is to build a circular Single Linked List by not using "first" & "last" pointers, but rather allow access to it by using one reference "current". I am not sure I understand the question, I always thought I needed at least either first or last. Here is my implementation but it has "first", not sure how to get around it. Can you please comment on how I can adjust my code to eliminate reliance on 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

Then here's the list itself:

然后这里是列表本身：

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

采纳答案by Erick Robertson

If you have a circular linked list, then each node points to the next node in a continuous loop. So there is no last and no first. In this situation, you only need one pointer into the data structure (which the question is calling "current") because you can walk the whole list until you get back to where you started.

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

One node might look like this:

一个节点可能如下所示：

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

So in this environment, when you add your first node to the list, it's "next" pointer will point to itself. When you add the second node, each "next" pointer will point to the other. When you add the third node, then they will each point to the next one, and presumably this is being ordered in some way. Each additional node added will be inserted into the appropriate place in the loop.

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

A good usage for a data structure like this would be a schedule that gets repeated every day or every hour. All of the events can be stored in a circular list and the "current" pointer always points to whichever is scheduled next.

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

Obviously, when searching a list like this, you need to keep a reference to the first node. This is the only way you can know if you've searched the whole list since it doesn't end with a null "next" pointer.

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

Edit:As discussed in the (extensive) comments below, a "tail" pointer would seem to be a very good idea here for insert operations. Here is the original method that I posted, which has been renamed insertAfter:

编辑：正如下面（广泛的）评论中所讨论的，“尾”指针在这里对于插入操作似乎是一个很好的主意。这是我发布的原始方法，已重命名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;
    }
}

A tail pointer would always point to the last node of the list. This would also be the node before the first node, since the list is circular. So be sure to maintain (tail.next == current)when manipulating the pointers. Here is the new insert method:

尾指针将始终指向列表的最后一个节点。这也将是第一个节点之前的节点，因为列表是循环的。所以(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
    }
}

Inserting values should rightly put them out of order. To maintain order when adding, an addmethod should be used:

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

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

Here's the code for advance:

这是代码advance：

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

When used like this to create lists...

当像这样使用来创建列表时......

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

...both lists are ordered 1-2-3 with the 1 as current.

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

回答by Tanmay Patil

Since the linked list is circular, there would be no first and last element.

由于链表是循环的，因此不会有第一个和最后一个元素。

You can traverse entire list starting from any node (current in this context).

您可以从任何节点（在此上下文中为当前节点）开始遍历整个列表。

So Nodeclass would only have a next reference, and CircularLinkedListwill have only current reference.

所以Node类只有下一个引用，并且CircularLinkedList只有当前引用。

Hope this helps.
Good luck.

希望这可以帮助。
祝你好运。

回答by Joop Eggen

Use Node current, int currentIndex, int size. Have the last Node's nextpoint to the first node of the list (= circular). With the current index you can walk (size - 1) elements to reach the previous node of current.

使用Node current, int currentIndex, int size. 让最后一个节点next指向列表的第一个节点（= 循环）。使用当前索引，您可以遍历 (size - 1) 个元素以到达 的前一个节点current。