Циклический связанный список в Java, когда указывать на первый узел?

Мне нужно реализовать круговую структуру данных односвязного списка. У меня проблемы с пониманием того, когда и где я должен указывать, что последний узел списка должен указывать на первый узел. У меня есть следующий пустой конструктор для построения списка:

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

    protected SNode<E> firstNode = null;

    public SList() {
        firstNode = 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 на firstNode.

Теоретически это должно работать, но поскольку я никогда не указываю последний элемент на первый до этого метода (это мой главный вопрос, как указать последний элемент на первый по умолчанию), я получаю nullPointer исключение, когда код достигает итерации while.

Любая помощь будет оценена, спасибо.


java list nodes circular-reference
person VDG    schedule 22.02.2015    source источник
comment
Проверьте нулевой указатель. Вот как вы понимаете, что находитесь в конце хвоста.   -  person Robert Harvey    schedule 22.02.2015
comment
Возможно связанный вопрос о кольцевых буферах Java на stackoverflow.com/questions/7266042/java-ring-buffer. Если вы не делаете это в качестве упражнения, возможно, стоит подумать об использовании Apache Commons CircularFifoBuffer.   -  person paisanco    schedule 22.02.2015
comment
@RobertHarvey Да, я могу проверить нулевой указатель, но это будет работать только для первого вызова метода, потому что после этого последний элемент будет указывать на первый. Я предполагаю, что смысл использования кругового списка в том, чтобы не иметь нулевого указателя.   -  person VDG    schedule 22.02.2015
comment
@paisanco да, это для упражнения, чтобы получить полное представление о том, как работают списки. В любом случае спасибо за ссылку, проверю!   -  person VDG    schedule 22.02.2015
comment
Вы можете указать последний элемент на первый, если хотите, но вместо этого я бы сохранил указатель головы и хвоста с логикой для обхода. См. en.wikipedia.org/wiki/Circular_buffer.   -  person Robert Harvey    schedule 22.02.2015

Ответы (1)


arrow_upward
1
arrow_downward

Единственный особый случай - это когда 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;
}
person Jean Logeart    schedule 22.02.2015
comment
Понятно, спасибо за это! Так что можно с уверенностью сказать, что по умолчанию нет способа сообщить Java, что мой последний элемент указывает на первый, мне просто нужно изменить все мои методы, чтобы сделать это? - person VDG; 22.02.2015