Java中的循环链表，何时指向第一个节点

Question

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

public class SList<E> implements IList<E> {
    protected SNode<E> firstNode = null;
    public SList() {
        firstNode = null;
    }

因此，基本上每个列表都以一个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的下一个节点与firstNode的节点匹配（意味着它在最后一个位置），它就会停止遍历列表，然后它会将其nextNode更改为我们想要添加的节点newNode，并将newNode指向firstNode。

理论上，这应该是可行的，但由于在这个方法之前我从未真正将最后一个元素指向第一个元素（这是我的主要问题，默认情况下如何将最后一个子元素指向第一个子元素），因此当代码到达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;
}