LinkedList - 実装を理解しようとしています

Question

私は複雑なアルゴリズムを解決することを学んでいます。そのために、私はLinkedListの実装を見つけました。私は上記の解決策を理解しようとしています。 appendToTailではwhileループとwhileループの後のwhileループについてはわかりません。 deleteNodeでは、ノードが削除された場所を見ることができません。

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

ここでは、考慮すべき2つのケースがあります。まず、ノードがリストの先頭にある場合。次に、ヘッドはちょうど次のノードに移動され、最初のノードはもはやリストの一部ではなくなります。

2番目のケースでは、ノードごとにリスト全体のノードを反復処理します。次のノードが削除を必要とするノード（if文でチェックされます）に到達すると、削除されたノードの次のノード（if文内の最初の行）のノードを保持するように変更されます。これにより、リストからノードが削除されます。ここでは、削除するノードの前にあるすべての要素が削除されます（削除されたノードの後に​​ノードに変更された場合）。

ノードbが削除されるはずである場合、aのすべてのノードは、b（c）の後にノードをポイントすることです。あなたがhereを確認することができ、よりよい可視化と説明については

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

を：これは、リストがどのように見えるかです。一般的なケースの部分は、2番目のケースが記述されている場所です。取り除かれたオブジェクトの処分は、ガベージコレクタによって実行されるため、移植時には明示的に行われません。

Answer 2

LinkedListsにはいくつかの実装があります。一部の人はpointerをリストのheadに保ちます。あなたが頭から

1 --> 2 --> null 
^ 
head 

を開始リストを反復しなければならないので、他の人はそうthisはの頭を指し、この実装は、何のテールポインタを保持していないO(1)

で最後尾に追加達成するために尾を追跡しますリスト。それは上記の例で

（Nにおける次のノードポインタがヌルに等しくなるまで）ループは、ここで

n n.next 
2 null 

ループだろう次いで出口とを終了させる最後に到達するまで、またはwhileループは、リスト内を移動しますセット：

1 --> 2 --> 3 
^ 
head