Implementieren einer Linkedlist in Java

Question

Ich lerne Datenstrukturen aktuell und unten ist meine Implementierung für LinkedList.Ich habe es so einfach wie möglich gehalten, wie mein Ziel hier ist es, die Logik zu verstehen.

/* 
* Singly linked list 
*/ 
package linkedlisttest; 


class Node { 
    int data; 
    Node next; 

    public Node(int data) 
    { 
     this.data = data; 
    } 

} 

class LinkedList { 

    Node head; 

    public void add(int data) 
    { 
     if (head == null) 
     { 
      head = new Node(data); 
      return; 
     } 

     Node current = head; 
     while (current.next != null) { 
      current = current.next; 
     } 
     current.next = new Node(data); 
    } 

    public int getSize() { 
     int i = 0; 
     Node current = head; 
     while (current != null) { 
      i += 1; 
      current = current.next; 
     } 
     return i; 
    } 

    public void add(int data, int index) 
    { 
     if (head == null && index == 0) 
     { 
       head = new Node(data); 
       return; 
     } else if (head == null && index != 0) { 
       return; // invalid position 
     } else if (index > getSize()) { 
      return; 
     } 

     Node current = head; 
     //iterate through whole list 
     int pos = -1; 
     Node previous = null; 
     Node next = null; 
     Node newNode = new Node(data); 
     //find next and previous nodes with relation to position 
     while (current != null) { 
      if (pos == index - 1) { 
       previous = current; 
      } else if (pos == index + 1) { 
       next = current; 
      } 
      pos++; 
      current = current.next; 
     } 
     previous.next = newNode; 

     newNode.next = next; 

    } 

    public void print() 
    { 
     Node current = head; 
     while (current.next != null) { 
      System.out.print(current.data + "->"); 
      current = current.next; 
     } 
     System.out.print(current.data); 
    } 

} 

public class LinkedListTest { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     LinkedList lt = new LinkedList(); 
     lt.add(3); 
     lt.add(5); 
     lt.add(6); 
     lt.add(4,1); 
     lt.print(); 
    } 

} 

Der Fehler passiert, für lt.add(4,1) und ich vermute, seine ein durch einen Fehler aus.

Erwartete Ausgabe: 3->4->6

tatsächliche Ausgang: 3->5->4

Vielen Dank für die Hilfe Jungs ...

bearbeiten

Dank @StephenP und @rosemilk Für ihre Hilfe. In der Tat hat der Code oben eine logische BU g wie es den Wert am Index ersetzt und nicht hinzufügt.

Hier ist der neue optimierte Code

/* 
* Singly linked list 
*/ 
package linkedlisttest; 

class Node { 

    int data; 
    Node next; 

    public Node(int data) { 
     this.data = data; 
    } 

} 

class LinkedList { 

    Node head; 
    int size; 

    /** 
    * 
    * @param data element to add to list 
    * Time Complexity : O(n) 
    */ 
    public void add(int data) { 
     if (head == null) { 
      head = new Node(data); 
      size += 1; 
      return; 
     } 

     Node current = head; 
     while (current.next != null) { 
      current = current.next; 
     } 
     current.next = new Node(data); 
     size += 1; 
    } 

    /** 
    * 
    * @return size of list 
    * Time Complexity: O(1) 
    * This is because we use a class 
    * variable size to keep track of size of linked list 
    */ 
    public int getSize() { 
     return size; 
    } 
    /** 
    * 
    * @param data element to insert 
    * @param index position at which to insert the element (zero based) 
    * Time Complexity : O(n) 
    */ 
    public void add(int data, int index) { 

     if (index > getSize()) { 
      return; // invalid position 
     } 

     Node current = head; //iterate through whole list 
     int pos = 0; 
     Node newNode = new Node(data); 

     if (index == 0) // special case, since its a single reference change! 
     { 
      newNode.next = head; 
      head = newNode; // this node is now the head 
      size += 1; 
      return; 
     } 
     while (current.next != null) { 
      if (pos == index - 1) { 
       break; 
      } 
      pos++; 
      current = current.next; 
     } 
     // These are 2 reference changes, as compared to adding at index 0 
     newNode.next = current.next; // here we are changing a refernce 
     current.next = newNode; // changing a reference here as well 
     size += 1; 

    } 

    /** 
    * Prints the whole linked list 
    * Time Complexity : O(n) 
    */ 
    public void print() { 

     if(getSize() == 0) { //list is empty 
      return; 
     } 
     Node current = head; 
     while (current.next != null) { 
      System.out.print(current.data + "->"); 
      current = current.next; 
     } 
     System.out.print(current.data + "\n"); 
    } 
} 

public class LinkedListTest { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     LinkedList lt = new LinkedList(); 
     lt.print(); 
     lt.add(3); 
     lt.add(5); 
     lt.add(6); 
     lt.print(); 
     lt.add(4, 1); 
     lt.print(); 
     lt.add(4, 7);// 7 is an invalid index 
     lt.add(8, 3); 
     lt.print(); 
    } 

} 

Answer 1

Derzeit wenn Sie pos in der Schleife ausdrucken, sind die Indizes -1, 0, 1 (anstelle von 0, 1, 2), so dass es‘ ll nie "finden" die richtige next. Ersetzen Sie int pos = -1; durch int pos = 0; und es wird funktionieren.

Ich stimme @stephenP, dass die Ausgabe sollte (wohl) 3->4->5->6 sein, aber das ist eine Design-Entscheidung.

Answer 2

Ihre add (int , int) Funktion hat einen logischen Fehler und kann besser gemacht werden. Sie benötigen keine vorherigen aktuellen und nächsten Referenzen und können die Liste clever bearbeiten, indem Sie nur den Verweis auf den aktuellen Knoten verwenden, indem Sie die Trennung von Index 0 separat behandeln. Ich würde die add Funktion schreiben, wie

public void add(int data, int index) 
{ 
    if (index > getSize()) { 
     return; // invalid position 
    } 

    Node current = head; //iterate through whole list 
    int pos = 0; 
    Node newNode = new Node(data); 

    if (index == 0) // special case, since its a single reference change! 
    { 
     newNode.next = head; 
     head = newNode; // this node is now the head 
     return; 
    } 
    while (current.next != null) { 
     if (pos == index - 1) { 
      break; 
     } 
     pos++; 
     current = current.next; 
    } 
    // These are 2 reference changes, as compared to adding at index 0 
    newNode.next = current.next; // here we are changing a refernce 
    current.next = newNode; // changing a reference here as well 

} 

auch folgt, Ihre print Funktion gibt eine NullPointerException wenn Sie versuchen, eine leere Liste zu drucken. Ich würde die Druckfunktion so schreiben,

public void print() 
{ 
    Node current = head; 
    while (current != null) { 
     System.out.print(current.data + "->"); 
     current = current.next; 
    } 
    System.out.println("null"); // this is just to say last node next points to null! 
} 

this helps :)