LinkedList - Versuchen, die Implementierung zu verstehen

Question

Ich lerne, komplexen Algorithmus zu lösen. Dafür bin ich auf die Implementierung von LinkedList gestoßen. Ich versuche die obige Lösung zu verstehen. In appendToTail verstehe ich while-Schleife und die Zeile nach der while-Schleife nicht. In deleteNode kann ich nicht sehen, wo der Knoten gelöscht wird.

class Node { 
    Node next = null; 
    int data; 

    public Node(int d) { 
     data = d; 
    } 

    void appendToTail(int d) { 
     Node end = new Node(d); 
     Node n = this; 
     while (n.next != null) { 
      n = n.next; 
     } 
     n.next = end; 
    } 

    Node deleteNode(Node head, int d) { 
     Node n = head; 
     if (n.data == d) { 
      return head.next; /* moved head */ 
     } 
     while (n.next != null) { 
      if (n.next.data == d) { 
       n.next = n.next.next; 
       return head; /* head didn’t change */ 
      } 
      n = n.next; 
     } 
    } 
} 

Answer 1

Nun, hier sind zwei Fälle zu beachten: Erstens, wenn der Knoten der erste in der Liste ist. Dann wird der Kopf einfach zum nächsten Knoten bewegt und der erste Knoten ist nicht länger Teil der Liste.

Im zweiten Fall durchlaufen wir nur die gesamte Liste Knoten für Knoten. Wenn wir den Knoten erreichen, dessen nächster Knoten gelöscht werden muss (was durch die if-Anweisung überprüft wird), wird er so geändert, dass er den Knoten nach dem gelöschten Knoten als nächsten Knoten hält (erste Zeile innerhalb der if-Anweisung). Dies entfernt den Knoten aus der Liste. Hier bleibt der Kopf gleich, wenn er geändert wird, werden alle Elemente vor dem Knoten gelöscht, der gelöscht werden soll (wenn er nach dem gelöschten Knoten in den Knoten geändert wurde).

Wenn der Knoten b soll gelöscht werden, alle Knoten a zu tun hat, ist mit dem Knoten nach b (c) zu zeigen. Dies ist, wie die Liste aussehen würde:

... a -> b -> c -> ... // before deletion 
... a -> c -> ...  // after deletion, now a points to c 

Für eine Erklärung mit schöner Visualisierung Sie here überprüfen können. Der allgemeine Fallteil ist der Fall, in dem der zweite Fall beschrieben wird. Die Entsorgung des Entfernten erfolgt nicht explizit bei der Implantation, wie es vom Garbage Collector durchgeführt wird.

Answer 2

LinkedLists haben mehrere Implementierungen. Einige halten nur einen pointer an den head der Liste. Andere verfolgen den Schwanz an Schwanz Diese Implementierung unterhält keine Endzeiger in O(1)

Anfügen zu erreichen, so dass Sie durch die Liste zu durchlaufen haben, aus dem Kopf

1 --> 2 --> null 
^ 
head 

Start

So this auf den Kopf bezieht sich die Die Liste. Die while-Schleife bewegt sich durch die Liste, bis er das Ende oder die (bis zum nächsten Knotenzeiger in n gleich null)

In dem obigen Beispiel erreicht würde die Schleife hier beenden

n n.next 
2 null 

die Schleife würde dann beenden und set:

n.next = end 

Die neue Liste sieht wie folgt aus:

1 --> 2 --> 3 
^ 
head