在從雙向鏈表中刪除節點時遇到問題

Question

我有一個雙重鏈接列表和我應該刪除給定節點的方法。它最初與我的3個測試節點一起工作，當我最初開發代碼時，但是當我向雙鏈表添加更多節點時，它停止工作，現在我得到一個NullReferenceException：「對象引用未設置爲對象的實例」我知道我可以使用通用鏈表，但我想了解雙鏈表如何工作。

我將在代碼中標記行，我在行的開頭使用「**」（它位於雙鏈表類的RemoveNode方法中）獲取此異常。

這裏是我的代碼：

雙向鏈表類：

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 Node FindNode(object n) //Find a given node in the DLL 
    { 
     current = head; 
     while ((current != null) && (current.data != n)) 
      current = current.next; 

     if (current == null) 
      return null; 
     else 
      return current;      
    } 


    public string RemoveNode(object n)//remove nodes 
    { 
     String Output = ""; 

     if (head == null) 
     { 
      Output += "\r\nLink list is empty"; 
     } 
     else 
     { 
      current = FindNode(n); 

      if (current == null) 
      { 
       Output += "Node not found in Doubly Linked List\r\n"; 
      } 
      else 
      {     
       ****current.next.prev = current.prev;**   
       current.prev.next = current.next; 
       current.prev = null; 
       current.next = null; 
       Output += "Node removed from Doubly Linked List\r\n"; 
      } 
     } 
     return Output; 
    } 

    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; 
    } 

} 

Node類：

class Node 
{ 
    public Node prev, next; // to store the links 
    public object data; // to store the data in a node 

    public Node() 
    { 
     this.prev = null; 
     this.next = null; 
    } 

    public Node(object data) 
    { 
     this.data = data; 
     this.prev = null; 
     this.next = null; 
    } 

    public Node(object data, Node prev) 
    { 
     this.data = data; 
     this.prev = prev; 
     this.next = null; 
    } 

    public Node(object data, Node prev, Node next) 
    { 
     this.data = data; 
     this.prev = prev; 
     this.next = next; 
    } 

} 

Answer 1

我得到它的工作。雖然我稍微改變了你的邏輯。我使用current字段來標記尾部，並使用一個單獨的變量進行搜索。現在，我跟整數值測試它和什麼原因導致的一個問題是，你比較值

(current.data != n) 

在那裏你可以得到行10！= 10，因爲值被裝箱和引用不同。改用current.data.Equals(n)即可。 Equals()是一種虛擬方法，可以將真實對象氣泡下來，並比較數據而不是參考。

此外，您的刪除邏輯必須更復雜。您也可以通過刪除所有必要的if/else語句來使其更具可讀性。

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 
    { 
     var newNode = new Node(n, current); 
     current.next = newNode; 
     current = newNode; //current is pointed to the newly added node 
    } 
} 

public Node FindNode(object n) //Find a given node in the DLL 
{ 
    var index = head; 
    while (index != null) 
    { 
     if (index.data.Equals(n)) 
      break; 

     index = index.next; 
    } 

    return index ?? null; 
} 

public string RemoveNode(object n) //remove node 
{ 
    if (head == null) 
     return "\r\nLink list is empty"; 

    var node = FindNode(n); 

    if (node == null) 
     return "Node not found in Doubly Linked List\r\n";   

    if (node != head) 
     node.prev.next = node.next; 

    if (node.next != null) 
     node.next.prev = node.prev; 

    return "Node removed from Doubly Linked List\r\n"; 
} 

Answer 2

你嘗試從列表中刪除的對象只有一個元素（ = head）？您遇到錯誤，請檢查您的刪除例程。您正在通過使用FindNode（它會返回您的頭節點）接收到一個元素，之後您將調用current.prev.next = current.next;，這將失敗，因爲您的頭節點既沒有previous也沒有next節點。

我會假設你remove函數應類似於此：

public string RemoveNode(object n)//remove nodes 
{ 
    String Output = ""; 

    if (head == null) 
    { 
     Output += "\r\nLink list is empty"; 
    } 
    else 
    { 
     var toRemove = FindNode(n); 

     if (toRemove == null) 
     { 
      Output += "Node not found in Doubly Linked List\r\n"; 
     } 
     else 
     {     
      if(toRemove.prev != null) 
       toRemove.prev.next = toRemove.next != null ? toRemove.Next : null; 
      if(toRemove.next != null) 
       toRemove.next.prev = toRemove.prev != null ? toRemove.prev : null; 

      Output += "Node removed from Doubly Linked List\r\n"; 
     } 
    } 
    return Output; 
}