Java中的循环LinkedList [英] Circular LinkedList in Java

问题描述

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

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

然后是列表本身:

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

推荐答案

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

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.

显然，当搜索这样的列表时，您需要保留对第一个节点的引用.这是您知道是否已搜索整个列表的唯一方法，因为它没有以空的"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.

如下面的(广泛的)注释所述，对于插入操作，"tail"指针似乎是一个非常好的主意.这是我发布的原始方法，已重命名为insertAfter:

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:

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).这是新的插入方法:

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:

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方法:

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

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

像这样用于创建列表时...

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

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

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

这篇关于Java中的循环LinkedList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！