LinkedList Insert Last

Question

Ich versuche, Element am Ende einer verknüpften Liste insertAtEnd() einzufügen. Wenn ich den Code debugge, sehe ich eine node(0,null) wird standardmäßig am Anfang der Einfügung eingefügt. Ich denke, das verursacht das Problem beim Durchlaufen der Liste. Irgendwelche Vorschläge, wie das zu beheben?

package com.ds.azim; 

public class Node { 
    //Node has 1. Data Element 2. Next pointer 
    public int data; 
    public Node next; 
    //empty constructor 
    public Node(){ 
     // 
    } 
    public Node(int data){ 
     this.data= data; 
     this.next = null; 
    } 
    public Node(int data, Node next){ 
     this.data = data; 
     this.next = next; 
    } 
} 

//*************************************//  

package com.ds.azim; 

    public class SingleLinkedList { 
     //Single Linked list has a head tail and has a length 
     public Node head; 
     public Node tail; 
     public int length; 
     //constructor 
     public SingleLinkedList(){ 
      head = new Node(); 
      length = 0; 
     } 
     public void insertAtFirst(int data){ 
      head = new Node(data,head); 
     } 
     public void insertAtEnd(int data){ 
      Node curr = head; 
      if(curr==null){ 
       insertAtFirst(data); 
      }else{ 
       while(curr.next!=null){ 
        curr = curr.next; 
       } 
       curr.next = new Node(data,null); 
      } 
     } 
     public void show(){ 
      Node curr = head; 
      while(curr.next!=null){ 
       //do something 
       System.out.print(curr.data+","); 
       curr = curr.next; 
      } 
     } 
     public static void main(String[] args){ 
      SingleLinkedList sll = new SingleLinkedList(); 
      sll.insertAtFirst(12); 
      sll.insertAtFirst(123); 
      sll.insertAtFirst(890); 
      sll.insertAtEnd(234); 
      sll.show(); 


     } 
    } 

Answer 1

Ihr Code initialisiert die Liste mit einem Node enthält (0, null) und head auf sie zeigen. Um das zu beheben, tu das nicht.

public SingleLinkedList() { 
    head = new Node(); 
    length = 0; 
} 

Auch in diesem Code festgelegt Sie length = 0;, aber eigentlich ist die Länge 1. Entfernen Sie beide Zuweisungen aus dem Konstruktor. Dann haben Sie eine Struktur mit null Mitgliedern und die Länge wird korrekt sein.

Answer 2

Sie haben eine tail Variable, die auf den letzten Knoten in Ihrer Liste zeigen sollte. Sie sollten es auf dem neuesten Stand sein zu halten:

class SingleLinkedList { 
    private Node head = null; 
    private Node tail = null; 

    public void addAtHead(int data) { 
     if (head == null) { 
      addFirst(data); 
     } else { 
      head.next = new Node(data, head.next); 
      if (tail == head) 
       tail = head.next; 
     } 
    } 

    public void addAtTail(int data) { 
     if (head == null) { 
      addFirst(data); 
     } else { 
      assert tail != null; 
      assert tail.next == null; 
      tail.next = new Node(data); 
      tail = tail.next; 
     } 
    } 

    private void addFirst(int data) { 
     assert head == null; 
     assert tail == null; 
     head = new Node(data); 
     tail = head; 
    } 
} 

Wenn Sie die tail Variable entfernen möchten, dann:

class SingleLinkedList { 
    private Node head = null; 

    public void addAtHead(int data) { 
     if (head == null) { 
      head = new Node(data); 
     } else { 
      head.next = new Node(data, head.next); 
     } 
    } 

    public void addAtTail(int data) { 
     if (head == null) { 
      head = new Node(data); 
     } else { 
      Node curr = head; 
      while (curr.next != null) 
       curr = curr.next; 
      curr.next = new Node(data); 
     } 
    } 
} 

Answer 3

Zusammen mit diesem Teil des

public SingleLinkedList() { 
    head = new Node(); 
    length = 0; 
} 

Änderungscode entfernen Ihre Show-Funktion auch, weil das letzte Element

while(curr.next!=null){ 
       //do something 
       System.out.print(curr.data+","); 
       curr = curr.next; 
      } 

nicht gedruckt wird

Danach legen Sie eine weitere print-Anweisung, um das letzte Element zu drucken.

System.out.print(curr.data); 

Dies wird die Fehler beheben.