Вставка в двойной круговой связанный список в 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

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

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

Все, кажется asymmetic там?

Несвязанный, но подумайте о вопросах: может list когда-либо быть null? Должно быть?

Answer 3

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

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

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

list.prev.next = list 

Answer 4

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