Having trouble with removing a node from a Doubly linked List

Question

I have a Doubly Linked List and I method which is supposed to remove a given node. It originally worked with my 3 test nodes when I originally developed the code but when I added more Nodes to the Doubly Linked List it stopped working, now I am getting an NullReferenceException:"Object reference not set to an instance of an object" I know I could just use a generic linked list but I am trying to learn how doubly linked lists work.

I will mark the line in my code where I am getting this exception with "**" at the beginning of the line(it is in the RemoveNode method in the Doubly Linked List class).

Here is my code:

Doubly 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 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:

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

I got it working. Although I slightly altered you logic. I use the current field to mark a tail and for searching I use a separate variable. Now, I tested it with integer values and what caused a problem was the line where you compare values

(current.data != n)

where you can get that 10 != 10 because the values are boxed and references differs. Just use current.data.Equals(n) instead. Equals() is a virtual method that bubbles down to the real objects and compares data rather then references.

Furthermore, your removing logic has to be more complex. You can also do it more readable by removing all those necessary if/else statements.

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

Do you try to delete an object from a list with only one Element (= head)? You got an error there, check your delete routine. You're receiving an element by using FindNode (which will then return your head node), afterwards you're calling current.prev.next = current.next;, which will fail because your headnode has neither a previous nor next node.

I'd assume your remove function should look similar to this:

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