LinkedList - 試圖瞭解實現

Question

我正在學習解決複雜的算法。爲此我遇到了LinkedList的實現。我想了解上述解決方案。在appendToTail中，我不明白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

那麼這裏有兩種情況需要考慮：首先，當節點是列表中的第一個。然後頭部移動到下一個節點，第一個節點不再是列表的一部分。

在第二種情況下，我們只是遍歷整個列表節點。如果我們到達下一個節點需要刪除（由if語句檢查）的節點，它會更改爲將刪除節點之後的節點保存爲下一個節點（if語句內的第一行）。這會從列表中刪除節點。這裏的頭部保持不變，因爲改變它會刪除應該刪除的節點之前的所有元素（如果它在刪除節點之後被改變爲節點）。

當節點b應該被刪除時，所有節點a所要做的就是指向b（c）之後的節點。這個列表是什麼樣子：

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

對於具有更好的可視化解釋，你可以檢查here。一般情況下的部分是描述第二種情況的地方。移除的處理並不是在植入中明確完成，因爲它是由垃圾收集器執行的。

Answer 2

LinkedLists有幾個實現。有些人只保留pointer到列表的head。其他保持尾部的軌道來完成追加到尾部O(1)

這種實現保持無尾指針，所以你必須在列表中迭代從頭部

1 --> 2 --> null 
^ 
head 

所以this指的頭部開始列表。 while循環移動通過列表，直到它到達端部或（直到在n中的下一節點指針等於null）

在上述例子中的循環將在這裏終止

n n.next 
2 null 

環路將然後退出並設置：

n.next = end 

新的名單看起來是這樣的：

1 --> 2 --> 3 
^ 
head