Java中的循环链表，什么时候指向第一个节点？

Question

我需要实现一个循环单链表数据结构。我无法理解的是我必须在何时何地声明列表的最后一个节点必须指向第一个节点。我有以下空构造函数来构建列表：

public class SList<E> implements IList<E> {

    protected SNode<E> firstNode = null;

    public SList() {
        firstNode = null;
    }

所以基本上每个列表都以一个再次指向 null 的空对象开始，表示列表的结尾：

public class SNode<E> {

E elem;
public SNode<E> nextNode = null;
...

然而我不知道的是如何使当列表包含至少一个节点时，该节点将指向列表的第一个节点。

例如，看一下我为常规链表实现的这个 addLast() 方法：

    public void addLast(E newElem) {
        SNode<E> newNode= new SNode<E>(newElem);
        SNode<E> nodeTraveler = firstNode;
        while (nodeTraveler.nextNode != null) {
            nodeTraveler= nodeTraveler.nextNode;
        }
        nodeTraveler.nextNode = newNode;
     }

我必须将其更改为：

    public void addLast(E newElem) {
    SNode<E> nodeTraveler = firstNode;
    SNode<E> newNode = new SNode<E>(newElem);
    while (nodeTraveler.nextNode != firstNode){
        nodeTraveler = nodeTraveler.nextNode;
    }
    nodeTraveler.nextNode = newNode;
    newNode.nextNode = firstNode;
}

nodeTraveler一旦下一个节点匹配到第一个节点（即在最后一个位置），就会停止遍历列表，然后将其nextNode更改为我们要添加的newNode，并将newNode指向第一个节点。

从理论上讲，这应该可行，但由于在使用此方法之前我实际上从未将最后一个元素指向第一个元素（这是我的主要问题，默认情况下如何将最后一个元素指向第一个元素），当代码到达 while 迭代时，我得到一个 nullPointer 异常。

如有任何帮助，我们将不胜感激。

Answer 1

唯一的特殊情况是 firstNode == null，这是初始情况。

之后第一个add会给出下一个元素为self的节点：

public void addLast(E newElem) {
    SNode<E> newNode = new SNode<E>(newElem);
    if(firstNode == null) {
        firstNode = newNode;
    } else {
        SNode<E> traveler = firstNode;
        for( ; traveler.nextNode != firstNode ; traveler = traveler.nextNode) {}
        traveler.nextNode = newNode;
    }
    newNode.nextNode = firstNode;
}

Java中的循环链表，什么时候指向第一个节点？

Circular linked list in Java, when to point to first node?

java

list

nodes

circular-reference