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

问题描述

我正在通过阅读一本书来复习我的数据结构，它提出的一个问题是通过不使用first"& 来构建循环单链表.last"指针，而是允许通过使用一个current"引用来访问它.我不确定我是否理解这个问题，我一直认为我至少需要第一个或最后一个.这是我的实现，但它有第一"，不知道如何解决它.你能评论一下我如何调整我的代码以消除对第一次的依赖吗?

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.

正如下面(广泛的)评论中所讨论的，尾"指针在这里对于插入操作似乎是一个非常好的主意.这是我贴出的原始方法，已重命名为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中的循环链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！