Java Linked List - dodaj metodę

Question

Klasa struktur danych, implementująca pojedynczą listę połączoną z głowami, ogonami i bieżącymi węzłami. Mając problem z metodą, może użyć przesunięcia we właściwym kierunku.

Z zadania, napisać metodę:

add (pozycja): dodaje element (string) po węźle bieżącym w liście i ustawia bieżący wskaźnik odnieść się do nowego węzła.

Moja próba:

Moja metoda add tylko wydaje się działać, gdy jestem dodawania elementów do środkowej części listy, a nie na obu końcach. Jeśli użyję go do dodania kilku elementów, a następnie wydrukuję listę, tylko pierwsza z nich, którą dodałem, znajdzie się na liście, podczas gdy moje metody poprzedzania i dołączania zostały przetestowane.

Czy istnieje jakiś poważny problem z moim kodem? Czuję, że brakuje mi czegoś oczywistego.

All:

public class LinkedList { 
    Node head = null; /* Head of the list */ 
    Node tail = null; /* Tail of the list */ 
    Node curr = null; /* Current node in the list */ 

    public void prepend(String item) { 
     if (head == null) { 
      head = tail = new Node(item, null); 
      curr = head; 
     } else { 
      head = new Node(item, head); 
      curr = head; 
     } 
    } 

    public void append(String item) { 
     if (head == null) { 
      head = tail = new Node(item, null); 
      curr = tail; 
     } else { 
      tail.next = new Node(item, null); 
      tail = tail.next; 
      curr = tail; 
     } 
    } 

    public void add(String item) { 
     if (curr != null) { 
      Node newNode = new Node(item, curr.next); 
      curr.next = newNode; 
      curr = newNode; 
     } else { 
      head = tail = new Node(item, null); 
      curr = head; 
     } 
    } 

    public void delete() { 
     if (curr.next == null) { 
      Node temp = head; 
      while (temp.next != curr) { 
       System.out.println(temp.item); 
       temp = temp.next; 
      } 
      temp.next = null; 
      curr = head; 
     } 
    } 

    public void find(String item) { 
     Node temp = new Node(curr.item, curr.next); 
     if (item.equals(temp.item)) 
      curr = temp; 
     else { 
      temp = temp.next; 
      while (temp.next != null && temp != curr) { 
       if (item.equals(temp.item)) 
        curr = temp; 
      } 
     } 
    } 

    public String get() { 
     if (curr != null) 
      return curr.item; 
     else 
      return ""; 
    } 

    public boolean next() { 
     if (curr != tail) { 
      curr = curr.next; 
      return true; 
     } else 
      return false; 
    } 

    public void start() { 
     curr = head; 
    } 

    public void end() { 
     curr = tail; 
    } 

    public boolean empty() { 
     if (head == null) 
      return true; 
     else 
      return false; 
    } 
} 

Node klasa:

class Node { 
    Node next; 
    String item; 

    Node(String item, Node next) { 
     this.next = next; 
     this.item = item; 
    } 
} 

Answer 1

Myślę, że problem jest

if (curr != null) { 
    Node newNode = new Node(item, curr.next); //<-- here (curr.next) 

//and 

Node(String item, Node next) { 
    this.next = next; //<-- here 

Try (Zmieniano):

Node newNode = new Node(item, curr); // pass curr to the constructor of Node 
curr = newNode; 

Answer 2

Nie widzę tu żadnych problemów, więc sądzę, że problem jest gdzie indziej.

Ok, jedyny problem widzę jest w kasowania:

public void delete() 
{ 
    Node temp = head; 

    while(temp != null && temp.next != curr) { 
     System.out.println(temp.item); 
     temp=temp.next; 

    } 

    if (temp != null && temp.next != null) { 
     temp.next = temp.next.next; 
    } 
    curr = head; 

} 

Answer 3

Chyba znalazłem problem. Jeśli użyjesz append(), dodaj go bezpośrednio po ogonie. Ale po dodaniu poprzednich węzłów po ogonie nie ustawiasz ogona na nowy węzeł. Oznacza to, że po dwukrotnym wywołaniu funkcji append() tracisz wszystkie węzły dodane po pierwszym dopełnieniu().

Krótki przykład:

public static void main(String[] args) { 
    LinkedList list = new LinkedList(); 
    list.add("First add"); 
    list.append("First Append"); 
    list.add("Second add"); 
    list.prepend("First prepend"); 
    list.add("Third add"); 
    list.prepend("Second prepend"); 
    list.add("fourth add"); 
    list.append("Second Append"); 
    list.add("Fifth add"); 
    list.add("Sixth add"); 

    list.start(); 
    do { 
     System.out.println(list.get().toString()); 

    } while (list.next()); 
} 

wyjściowa:

Second prepend 
fourth add 
First prepend 
Third add 
First add 
First Append 
Second Append 

Wniosek: "Drugi Dodaj" jest stracone, jak również "Piąta dodać" i "Szósty dodatek", ponieważ metoda next() zatrzymuje się, gdy tylko osiągnie ogon. Zawsze musisz zaktualizować ogon, jeśli dodasz nowy węzeł na końcu.

Mam nadzieję, że to pomoże. Pozdrowienia, Chnoch

Answer 4

Rzeczywiście problem występuje w add: nie aktualizuje się tail, gdy węzły już istnieją.Rozważmy taką sekwencję działań:

LinkedList list = new LinkedList(); 
list.add("one"); 
list.add("two"); 
list.append("three"); 

Jeśli było następnie wydrukować go za pomocą tego:

public void print() { 
    Node curr = this.head; 
    while(curr != null) { 
     System.out.println(curr.item); 
     curr = curr.next; 
    } 
} 

Jak to:

list.print(); 

Można by uzyskać następujące dane wyjściowe:

one 
three 

Dzieje się tak ause tail - na którym bazuje append - kontynuuje wskazywanie pierwszego Node po wykonaniu drugiej operacji add.