Вставка в дважды круговой связанный список в Java

Question

Для домашней работы я должен создать круговой связанный список, используя узлы и указатели.
Это мой класс узлов

class Node implements Serializable {
    public String theName; //the wrapped name
    public Node next;      //the next node in the sequence
    public Node prev;      //the previous node in the sequence

    public Node(Node p, String s, Node n){
        prev = p;
        theName = s;
        next = n;
    }
}

Я пытаюсь вставить строки (имена) в началеПеречислите их, а затем распечатайте, используя метод обхода.
Пока это мои методы обхода и вставки ...

public class ListImpl /*implements List*/ {
    Node list;

    public ListImpl() {
        list = new Node(list, null, list);
    }

    public void insert(String s) {


        if (list == null) {
            list = new Node(list, s, list);
        } else {
            list = new Node(list.prev, s, list);
            list.next.prev = list;
            list.next.next = list;



        }
    }

    public void traverse(ASCIIDisplayer out) {

        Node p = new Node(null, null, null);
        p = list;
        if (list != null) {

            while(true) {
                out.writeString(p.theName);
                p = p.next;
            }
        } else {
            throw new EmptyListException();
        }
    }
}

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

public class Main {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        ASCIIDisplayer a = new ASCIIDisplayer();
        ListImpl List;

        List = new ListImpl();
        List.insert("Steve");
        List.insert("Kuba");
        List.insert("Taylor");
        List.insert("Jane");

        List.traverse(a);
    }
}

Вывод, который я получаю: Тейлор Джейн Тейлор Джейн Тейлор Джейн Тейлор Джейн ... повторил.
Я ожидал, что результатом будет: Стив Куба Тейлор Джейн Стив Куба Тейлор Джейн... повторяется.

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

Извините за длинный вопрос, надеюсь, вам хватит информации, чтобы помочь мне!Заранее спасибо!

Answer 1

Замените это:

    list = new Node(list.prev, s, list);
    list.next.prev = list;
    list.next.next = list;

на это:

    Node tmpList = new Node(list.prev, s, list);
    list.next.prev = tmpList;
    list.prev.next = tmpList;
    list = tmpList;

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

Кроме того, когда вы вставляете первый узел, вы делаете это:

if (list == null) {
    list = new Node(list, s, list);

В этом случаеоба параметра list, передаваемые в ваш конструктор, null, вы должны исправить это, либо создав новый конструктор, который принимает только значение String и затем ссылается на себя, либо установив prev и nextвручную.

Вот решение конструктора:

class Node implements Serializable {

public String theName; //the wrapped name
public Node next;      //the next node in the sequence
public Node prev;      //the previous node in the sequence

public Node(Node p, String s, Node n){
    prev = p;
    theName = s;
    next = n;
}
public Node(String s){
    prev = this;
    theName = s;
    next = this;
}}

Answer 2

Посмотрите внимательно на ветку else внутри функции insert и подумайте, действительно ли вы хотите установить list.next.next=list.

Answer 3

Эта часть вашей вставки выглядит неправильно

} else {
    list = new Node(list.prev, s, list);
    list.next.prev = list;
    list.next.next = list;

Последняя строка должна быть:

    list.prev.next = list

Answer 4

У вас есть проблема в вашем методе вставки:

    list.next.prev = list;
    list.next.next = list;

Что-нибудь там кажется асимметричным?

Не имеет отношения, но подумайте над вопросами: может ли list быть null? Это должно быть?