如何從雙向鏈表中刪除節點？

Question

我需要創建一個方法來從雙向鏈表中刪除給定的節點（稱爲「傑克」的節點）。

這裏是我的代碼：

鏈表類：

class DoublyLinkedList 
{ 
    public Node head, current; 

    public void AddNode(object n) // add a new node 
    { 
     if (head == null) 
     { 
      head = new Node(n); //head is pointed to the 1st node in list 
      current = head; 
     } 
     else 
     { 
      while (current.next != null) 
      { 
       current = current.next; 
      } 

      current.next = new Node(n, current); //current is pointed to the newly added node 
     } 
    } 

    public void RemoveNode(object n) 
    { 

    } 

    public String PrintNode() // print nodes 
    { 
     String Output = ""; 

     Node printNode = head; 
     if (printNode != null) 
     { 
      while (printNode != null) 
      { 
       Output += printNode.data.ToString() + "\r\n"; 
       printNode = printNode.next; 
      } 
     } 
     else 
     { 
      Output += "No items in Doubly Linked List"; 
     } 
     return Output; 
    } 

} 

執行按鈕代碼： 我已經添加了3個節點，你可以看到，我想刪除「傑克」節點。

private void btnExecute_Click(object sender, EventArgs e) 
    { 
     DoublyLinkedList dll = new DoublyLinkedList(); 
     //add new nodes 
     dll.AddNode("Tom"); 
     dll.AddNode("Jack"); 
     dll.AddNode("Mary"); 
     //print nodes 
     txtOutput.Text = dll.PrintNode(); 

    } 

Answer 1

1. 找到節點n
   1. 如果n.Next不null，設置n.Next.Prev到n.Prev
   2. 如果n.Prev不null，設置n.Prev.Next到n.Next
   3. 如果n == head，設置head到n.Next

基本上，你找到你要刪除的節點，使節點到其左指向節點其右，反之亦然。

爲了找到節點n，你可以做這樣的事情：

public bool Remove(object value) 
{ 
    Node current = head; 

    while(current != null && current.Data != value) 
     current = current.Next; 

    //value was not found, return false 
    if(current == null) 
     return false; 

    //... 
} 

注：這些算法通常涉及到兩個變量。您必須始終確保第一個節點的Prev屬性和最後一個節點的Next屬性爲空 - 您可以將其讀爲：「沒有節點出現在第一個節點之前，並且沒有節點出現在最後一個節點之後」。

Answer 2

你的代碼應該包含Previous指針，使它成爲雙向鏈表。

public void RemoveNode(object n) 
{ 
    Node lcurrent = head; 

    while(lcurrent!=null && lcurrent.Data!=n) //assuming data is an object 
    { 
     lcurrent = lcurrent.Next; 
    } 
    if(lcurrent != null) 
    { 
     if(lcurrent==current) current = current.Previous; //update current 
     if(lcurrent==head) 
     { 
      head = lcurrent.Next; 
     } 
     else 
     { 
      lcurrent.Previous.Next = lcurrent.Next; 
      lcurrent.Next.Previous = lcurrent.Previous; 
      lcurrent.Next = null; 
      lcurrent.Previous = null; 
     } 
    } 
}