How to remove a node from a doubly linked list?

Question

I need to create a method to remove a given node (the node called "Jack") from a doubly linked list.

here is my code:

linked list class:

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

}

Execute button code: I have already added 3 nodes as you can see and I want to remove the "Jack" node.

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. Find the node n
   1. if n.Next is not null, set n.Next.Prev to n.Prev
   2. if n.Prev is not null, set n.Prev.Next to n.Next
   3. if n == head, set head to n.Next

Basically, you find the node you want to remove, and make the node to its left point to the node to its right, and vice-versa.

To find node n, you can do something like this:

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;

    //...
}

Note: these algorithms usually involve two invariants. You have to make sure that, at all times, the first node's Prev property and the last node's Next property are null - you can read this as: "no node comes before the first node, and no node comes after the last node".

Answer 2

Your code should include Previous pointer to make it doubly linked list.

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