如何从双向链表中删除节点？

Question

我需要创建一个方法来从双向链表中删除给定节点（名为“Jack”的节点）。

这是我的代码：

链表类：

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 个节点，并且我想删除“Jack”节点。

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

属性为 null - 您可以将其读作：“没有节点出现在第一个节点之前，也没有节点出现在第一个节点之后。最后一个节点”。

Answer 2

您的代码应包含

Previous

指针以使其成为双向链表。

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

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

        if(lcurrent == head) {
           head = lcurrent.Next;
        } else {
           lcurrent.Previous.Next = lcurrent.Next;
           lcurrent.Next.Previous = lcurrent.Previous;
           lcurrent.Next = null;
           lcurrent.Previous = null;
        } 
    }
}