從約束鏈表中刪除元素

Question

這是一個相當簡單的問題，但我很困惑：

給定一個單向鏈表，編寫一個函數來刪除一個給定的節點。

1）它必須接受指向開始節點的指針作爲第一個參數，並刪除節點作爲第二個參數，即指向頭節點的指針不是全局的。 2）它不應該返回指向頭節點的指針。 3）它不應該接受指向頭節點的指針。

Java中的解決方案如下：

void deleteNode(Node node, Node n) { 

    if (node == n) { 
     if (node.next == null) { 
      System.out.println("There is only one node. The list " 
          + "can't be made empty "); 
      return; 
     } 

     node.data = node.next.data; 
     n = node.next; 
     node.next = node.next.next; 
     System.gc(); 

     return; 
    } 

    // When not first node, follow the normal deletion process 
    // find the previous node 
    Node prev = node; 
    while (prev.next != null && prev.next != n) { 
     prev = prev.next; 
    } 
    if (prev.next == null) { 
     System.out.println("Given node is not present in Linked List"); 
     return; 
    } 
    prev.next = prev.next.next; 
    System.gc(); 

    return; 
} 

我很困惑，爲什麼在刪除頭節點，我們不修改頭指針，但複製的區域，而不是（更改內容）但是在刪除其他節點時，只是簡單地使用prev.next = prev.next.next 如果我們只是在刪除頭節點時做head = head.next，它會起作用嗎？

謝謝！

Answer 1

代碼複製數據而不是修改引用頭的變量的原因是該列表的其他用戶將具有對頭節點的引用。更改本地變量將不會影響其引用，因此您不會實際刪除該節點。將數據複製到頭節點可以有效地將其刪除。

因此，舉例來說，如果你有代碼，做了以下內容：

Node head = new Node("A"); 
Node tail = new Node("B"); 
head.next = tail; 
deleteNode(head, head); 

然後你會期望head.data爲「B」，因爲原始節點已被刪除。如果你只是做node = node.next那麼head仍然會指向原來的刪除節點。

您發佈的代碼存在不少問題，因此如果您希望提出有關應該改進的建議，請添加評論。它不是從鏈表中刪除節點的典型算法。

您詢問的一個明確問題是使用System.gc。沒有必要。 Java代碼需要顯式控制垃圾收集的情況很少見。這不是其中之一。在this question的接受答案中有一個很好的解釋。

您在評論中詢問了爲什麼刪除頭需要移動數據，而刪除其他節點時只需要在節點周圍進行重定向。原因是因爲您無法訪問頭部的引用（如上面的答案中所述）。您可以訪問對其他節點的引用（即前節點的next），以便可以直接更改它們，而不必複製數據。

爲了供您參考，更爲標準的實現是讓列表本身存儲對頭部的引用。然後可以完全避免複製節點數據。另外請注意，由於節點類是私有的，因此這與值進行比較。

static class LinkedList<T> { 
    private class Node { 
     private final T value; 
     private Node next = null; 

     public Node(T value) { 
      this.value = value; 
     } 
    } 

    private Node head = null; 

    public void add(T value) { 
     Node node = new Node(value); 
     node.next = head; 
     head = node; 
    } 

    public void remove(T value) { 
     while (head != null && head.value.equals(value)) 
      head = head.next; 
     Node prev = head; 
     while (prev != null && prev.next != null) { 
      if (prev.next.value.equals(value)) 
       prev.next = prev.next.next; 
      else 
       prev = prev.next; 
     } 
    } 
} 

這就避免了在你不能夠刪除的頭，如果它是唯一的節點提供了這樣的例子中，任意限制。