Doubly Linked List in C#

Introduction

 

In this article, you will learn about the Doubly Linked list in C#. 

 

Doubly Linked List

 

Before going to Doubly LL, let me tell you the drawbacks of Singly LL. A node deletion in Singly LL cannot be removed unless we know the pointer of its predecessor, whereas, in doubly LL, we can delete a node even if we do not have the address of predecessor. 

 

Pictorial representation of a Doubly Linked list:

 

 

Create a Doubly Linked List 

 

To create a node in doubly LL. First, we need to create a Head reference, Tail reference, and Blank node. Insert a value in the blank node, say 15. So this becomes the first node in the doubly linked list. So we set the value of next node i.e tail node to null and Head node to null (there is no node previous to this). Because this is the only node in the linked list. Now the next step is to create the reference. So, for example, say the node "15" is stored in the reference "111". So we need to insert a value of "Head" with "111". To create a reference between node and head. In Tail also the reference should be "111" since this is the first node.

 

Below is the pictorial representation:

 

 

 

Let's take a look at the algorithm for this:

 

Step1: CreateDoublyLL(node) ----------------------------------------------------O(1)

Step2: create a blank node--------------------------------------------------------O(1)

Step3: node.value= node //insert 15 in node value--------------------------O(1)

Step4: head=node// keeping reference 111------------------------------------O(1)

Step5: tail= node // Keeping reference 111------------------------------------O(1)

Step 6: node.prev = node.net= null // because this is the only node in the doubly LL.---------------O(1)

 

Time and Space Complexity: O(1) 

 

Let's look at the code now:

public class DoubleLinkedList {
              DoubleNode head;
              DoubleNode tail;
             int size;

     DoubleNode CreateDoublyLL(int nodeValue){
                 head = new DoubleNode();
                DoubleNode node = new DoubleNode();
                node.setValue(nodeValue);
                node.setNext(null);
               node.setPrev(null);
               head = node;
              tail=node;
              size = 1;
              return head;

           }
}

The important thing here to note is that in Singly LL we never had prev node, but in Doubly LL we have pre node. That is the only difference in the code we see between singly and doubly LL.

 

Insert a Node in a Doubly Linked List

 

To insert a node in the Doubly LL we have 3 cases:

1. Insert a new node before Head
2. Insert a new node at the End of the list             
3. Insert a new node in the middle of the list.

Now let's see all the above 3 cases.

 

Insert a new node before head

1. Create a blank node and insert a new value in it.
2. Set the prev value to null, since we are inserting this node in the first position.
3. The head reference needs to be updated with a new node reference and the next reference of the new node should be pointed to the next node in the list.

 

 

Insert new node at the end of the list:

1. We need to create a blank node and insert a new value in it
2. Set the reference of next to null
3. Set the prev to refer to the last node in the linked list. The tail reference needs to be updated with a new node reference

Insert new node in the middle of the doubly linked list

1. Create a blank node and insert value in the node
2. Create a link between the previous node and new node by storing the previous node reference in a temp variable
3. Set the temp.next value in prev reference of the new node. 

 

We have seen all the 3 cases in the pictorial representation. Now let's look at the implementation of Inserting a node in a doubly linkedlist.

 

Algorithm

 

Step1: InsertNodeInDoublyLL(head, nodeValue, location) ----------------------------------O(1)

Step 2: create a blank node // this is for new node----------------------------------O(1)

Step 3: node.value= nodeValue---------------------------------------------------------------O(1)

Step 4: if(head== null) return error----------------------------------O(1)

Step 5: else if(location==0) // insert at first position----------------------------------O(1)

Step 6: node.next = head----------------------------------O(1)

             node.prev=null----------------------------------O(1)

             head.prev=node----------------------------------O(1)

             head=node ----------------------------------O(1)

Step 7: else if(location equals last) // insert at the end of the LL----------------------------------O(1)

            node.next= null;----------------------------------O(1)

            node.prev= tail----------------------------------O(1)

            tail.next= node----------------------------------O(1)

            tail=node----------------------------------O(1)

Step 8: else //Insert at specifie location (middle)----------------------------------O(1)

             loop: tempNode= 0 to location-1----------------------------------O(n) //depends on length of the LL and Position where we want to insert

             node.next= tempNode.next----------------------------------O(1)

             node.prev = tempNode----------------------------------O(1)

             tempNode.next = node----------------------------------O(1)

            node.next.next.prev= node ----------------------------------O(1)

 

Time Complexity : O(n)

Space Complexity : O(1) 

void InsertInDoublyLL(int nodeValue, int location){

//create blank node
var node = DoubleNode();
node.setValue(nodeValue);
if(head==null)
Console.WriteLine("LinkedList doesnot exists");
return;
else if(location == 0){

   node.setNext(head);
   npde.setPrev(null);
   head.setPrev(node);
   head=node;

}else if(location >= size){ // last position

   node.setNext(null);
   tail.setNext(node);
   node.setPrev(tail);
   tail= node;

}else{
   DoubleNode tempNode = head;
   int index=0;
   while(index < location - 1){
      tempNode= tempNode.getNext();
      index++;
   }//end of while loop
   node.setNext(tempNode.getNext());
   node.setPrev(tempNode);
   tempNode.setNext(node);
   node.getNext().setPrev(node);
   }
   size++;
} // end of the method

Traversing in Doubly linked list from head to tail

 

Traversing in doubly LL is the same as traversing in Singly LL. Let's see the algorithm for this:

 

Algorithm

 

Step 1:  TraverseDDL() ------------------------------O(1)

Step 2: if(head is null) return error-----------------O(1)

Step 3: else 

               loop : head to tail--------------------------O(n)

               print the currentnode.value ------------O(1)

 

Time Complexity : O(n)

Space Complexity: O(1)

 

Let's see the code for the above algorithm:

void TraverseDDL(){
     if(head==null){
        Console.WriteLine("LinkedList does not exists");
       return;
    }else{
          DoubleNode tempNode = head;
           for(int i =0;i< size;i++){
                    Console.Write(tempNode.getValue);
                    Console.Write("-->");
                    tempNode= tempNode.getNext();
          }
    }
     Console.WriteLine("\n");
}

Traverse Doubly linked list in reverse order (from tail to head) 

 

Algorithm

 

Step 1: ReverseTraverseDDL(head)---------O(1)

Step 2: if(head is null) return error------------O(1)

Step 3: else

            loop: tail to head-----------------------O(n)

              print currentNode.value -----------O(1)

 

Time Complexity: O(n)

Space Complexity : O(1)

 

Let's see the code for above algorithm:

void ReverseTraverseDDL(){
     if(head==null) {
           Console.WriteLine("Linked list doesnot exists");
          return;
    }else{
           DoubleNode tempNode = tail;
           for(int i=0;i<size;i++)
           {
                    Console.Write(tempNode.getValue());
                   Console.Write("<---");
                  tempNode= tempNode.getPrev();
           }

   }
   Console.WriteLine("\n");
}

Search a Node in Doubly Linked List

 

Algorithm

 

Step 1: SearchNodeInDDL(nodeValue)

Step 2: if(head is null) return error

Step 3: loop : head to tail

             if(tempNode.value equals nodeValue)

                 print node found

              else

                 print node does not exists 

 

 Now let's see the code for this:

bool SearchNodeInDDL(int nodeValue){
       if(head == null){
           Console.WriteLine("LinkedList does not exists");
           return ;
      }else{
          DoubleNode tempNode= head;
         for(int i=0;i<size;i++){
                if(tempNode.getValue() == nodeValue){
                     Console.WriteLine("node  exists in the Linked list:"+ nodeValue);
                    return true;
                }
           tempNode = tempNode.getNext();
        }
       return false;
     }

}

Delete a node from Doubly Linked list at given position

 

To delete a nodefrom doubly linked list. We have 3 cases:

1. Delete a node from first postion
2. Delete a node from last position
3. Delete a node from middle of linked list

Delete a node from first position

1. We need to check if Linked list exists
2. We need to check if current node is the only element in the linked list
3. Delete a node from fisrt position and update the head reference with next node

                             

Delete a node at last Position

1. We need to check if Linked list exists
2. We need to check if current node is the only element in the linked list
3. Delete a node at last position and update the tail reference with previous node

Delete the node at the middle of linked list

1. We need to check if Linked list exists 
2. We need to check if current node is the only element in the linked list
3. If node exits delete the node at the specified position and update the prev and next node of linked list

 

 

Now let's see the algorithm for all three cases.

 

Algorithm

 

Step 1: DeleteNodeInDLL(location) ------------------------------------------------O(1)

Step 2: If(head is null) return error------------------------------------------------O(1)

Step 3: else if(location =0)------------------------------------------------O(1)

            if(size equals 1) ------------------------------------------------O(1)

             then set head = tail = null // only single node in the list------------------------------------------------O(1)

            else

                 head = head.next------------------------------------------------O(1)

                 node.prev = null------------------------------------------------O(1)

                 size--;

             else if ( location >= last)------------------------------------------------O(1)

               if( size equals 1)

                   then set head = tail = null // only single node in the list return------------------------------------------------O(1)

                 tail= tail.prev------------------------------------------------O(1)

                 tail.next= null------------------------------------------------O(1)

          else // if any middle element to be deleted------------------------------------------------O(1)

            loop : tempNode = start to location-1------------------------------------------------O(n)

                      tempNode.next= tempNode.next.next // link current node with next node------------------------------------------------O(1)

                      tempNode.next.prev = tempNode// link next node with current node ------------------------------------------------O(1)

 

           Time Complexity: O(n)

           Space Complexity: O(1) 

// Deletes a node having a given value
    public void deletionOfNode(int location) {
        if (head==null) {
            Console.WriteLine("The linked list does not exist!!");// Linked List does not exists
            return;
        } else if (location == 0) { // we want to delete first element
            if (getSize() == 1) { // if this is the only node in this list
                head = tail = null;
                setSize(getSize() - 1);
                return;
            }else {
                head = head.getNext();
                head.setPrev(null);
                setSize(getSize() - 1);
            }
        } else if (location >= getSize()) { // If location is not in range or equal, then delete last node
            DoubleNode tempNode = tail.getPrev(); // temp node points to 2nd last node
            if (tempNode == head) { // if this is the only element in the list
                tail = head = null;
                setSize(getSize() - 1);
                return;
            }
            tempNode.setNext(null);
            tail = tempNode;
            setSize(getSize() - 1);

        } else { // if any inside node is to be deleted
            DoubleNode tempNode = head;
            for (int i = 0; i < location - 1; i++) {
                tempNode = tempNode.getNext(); // we need to traverse till we find the location
            }
            tempNode.setNext(tempNode.getNext().getNext()); // delete the required node
            tempNode.getNext().setPrev(tempNode);
            setSize(getSize() - 1);
        } // end of else

    }// end of method

That's all about the Doubly Linked list. I hope I have covered all the basic scenarios. That's it guys. Thank you!!!