Post
Ask Question

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:
  1. public class DoubleLinkedList {  
  2.               DoubleNode head;  
  3.               DoubleNode tail;  
  4.              int size;  
  5.       
  6.      DoubleNode CreateDoublyLL(int nodeValue){  
  7.                  head = new DoubleNode();  
  8.                 DoubleNode node = new DoubleNode();  
  9.                 node.setValue(nodeValue);  
  10.                 node.setNext(null);  
  11.                node.setPrev(null);  
  12.                head = node;  
  13.               tail=node;  
  14.               size = 1;  
  15.               return head;  
  16.        
  17.            }  
  18. }  
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) 
  1. void InsertInDoublyLL(int nodeValue, int location){  
  2.   
  3. //create blank node   
  4. var node = DoubleNode();  
  5. node.setValue(nodeValue);  
  6. if(head==null)  
  7. Console.WriteLine("LinkedList doesnot exists");  
  8. return;  
  9. else if(location == 0){  
  10.   
  11.    node.setNext(head);  
  12.    npde.setPrev(null);  
  13.    head.setPrev(node);  
  14.    head=node;  
  15.   
  16. }else if(location >= size){ // last position  
  17.   
  18.    node.setNext(null);  
  19.    tail.setNext(node);  
  20.    node.setPrev(tail);  
  21.    tail= node;  
  22.   
  23. }else{  
  24.    DoubleNode tempNode = head;  
  25.    int index=0;  
  26.    while(index < location - 1){  
  27.       tempNode= tempNode.getNext();  
  28.       index++;  
  29.    }//end of while loop  
  30.    node.setNext(tempNode.getNext());  
  31.    node.setPrev(tempNode);  
  32.    tempNode.setNext(node);  
  33.    node.getNext().setPrev(node);  
  34.    }  
  35.    size++;  
  36. } // 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:
  1. void TraverseDDL(){  
  2.      if(head==null){  
  3.         Console.WriteLine("LinkedList does not exists");  
  4.        return;  
  5.     }else{  
  6.           DoubleNode tempNode = head;  
  7.            for(int i =0;i< size;i++){  
  8.                     Console.Write(tempNode.getValue);  
  9.                     Console.Write("-->");  
  10.                     tempNode= tempNode.getNext();  
  11.           }  
  12.     }  
  13.      Console.WriteLine("\n");  
  14. }  
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:
  1. void ReverseTraverseDDL(){  
  2.      if(head==null) {  
  3.            Console.WriteLine("Linked list doesnot exists");  
  4.           return;  
  5.     }else{  
  6.            DoubleNode tempNode = tail;  
  7.            for(int i=0;i<size;i++)  
  8.            {  
  9.                     Console.Write(tempNode.getValue());  
  10.                    Console.Write("<---");  
  11.                   tempNode= tempNode.getPrev();  
  12.            }  
  13.   
  14.    }  
  15.    Console.WriteLine("\n");  
  16. }  
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:
  1. bool SearchNodeInDDL(int nodeValue){  
  2.        if(head == null){  
  3.            Console.WriteLine("LinkedList does not exists");  
  4.            return ;  
  5.       }else{  
  6.           DoubleNode tempNode= head;  
  7.          for(int i=0;i<size;i++){  
  8.                 if(tempNode.getValue() == nodeValue){  
  9.                      Console.WriteLine("node  exists in the Linked list:"+ nodeValue);  
  10.                     return true;  
  11.                 }  
  12.            tempNode = tempNode.getNext();  
  13.         }  
  14.        return false;    
  15.      }  
  16.   
  17. }  

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) 
  1. // Deletes a node having a given value  
  2.     public void deletionOfNode(int location) {  
  3.         if (head==null) {  
  4.             Console.WriteLine("The linked list does not exist!!");// Linked List does not exists  
  5.             return;  
  6.         } else if (location == 0) { // we want to delete first element  
  7.             if (getSize() == 1) { // if this is the only node in this list  
  8.                 head = tail = null;  
  9.                 setSize(getSize() - 1);  
  10.                 return;  
  11.             }else {  
  12.                 head = head.getNext();  
  13.                 head.setPrev(null);  
  14.                 setSize(getSize() - 1);  
  15.             }  
  16.         } else if (location >= getSize()) { // If location is not in range or equal, then delete last node  
  17.             DoubleNode tempNode = tail.getPrev(); // temp node points to 2nd last node  
  18.             if (tempNode == head) { // if this is the only element in the list  
  19.                 tail = head = null;  
  20.                 setSize(getSize() - 1);  
  21.                 return;  
  22.             }  
  23.             tempNode.setNext(null);  
  24.             tail = tempNode;  
  25.             setSize(getSize() - 1);  
  26.   
  27.         } else { // if any inside node is to be deleted  
  28.             DoubleNode tempNode = head;  
  29.             for (int i = 0; i < location - 1; i++) {  
  30.                 tempNode = tempNode.getNext(); // we need to traverse till we find the location  
  31.             }  
  32.             tempNode.setNext(tempNode.getNext().getNext()); // delete the required node  
  33.             tempNode.getNext().setPrev(tempNode);  
  34.             setSize(getSize() - 1);  
  35.         } // end of else  
  36.   
  37.     }// 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!!!


Similar Articles