Java中的循环链表

Question

Java中的循环链表

7

我正在通过阅读一本书来复习数据结构。其中有一个问题要求我构建一个循环单链表，但不能使用“first”和“last”指针，而是要允许通过使用一个引用“current”来访问它。我不确定我理解了这个问题，我总是认为至少需要“first”或“last”中的一个。这是我的实现方式，但它有“first”，我不确定如何解决这个问题。请评论一下我如何调整代码以消除对“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;
    }
    ...
}

- sam2015

3个回答

0

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

- Joop Eggen

0

由于链表是循环的，所以没有第一个和最后一个元素。

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

因此，Node类只会有一个下一个引用，而CircularLinkedList将只有当前引用。

希望这可以帮助到您。
祝您好运。

- Tanmay Patil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Erick Robertson · Accepted Answer

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

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

在这种环境下，当您向列表添加第一个节点时，它的“next”指针将指向自身。当您添加第二个节点时，每个“next”指针都将指向另一个节点。当您添加第三个节点时，它们将分别指向下一个节点，并且可能以某种方式进行排序。每添加一个额外的节点都将插入到循环中的适当位置。

像这样的数据结构的一个好用途是重复每天或每小时的日程安排。所有事件都可以存储在循环列表中，“current”指针始终指向下一个计划安排。

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

编辑：如下面（详尽的）评论中所讨论的那样，这里似乎需要一个“tail”指针来进行插入操作。以下是我发布的原始方法，已更名为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为当前项。