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将停止遍历列表，然后将其下一个节点更改为我们要添加的节点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;
}