Post

# Doubly Linked List in C#

• 76.2k
• 0
• 5

## Introduction

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)
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:
3.               DoubleNode tail;
4.              int size;
5.
6.      DoubleNode CreateDoublyLL(int nodeValue){
8.                 DoubleNode node = new DoubleNode();
9.                 node.setValue(nodeValue);
10.                 node.setNext(null);
11.                node.setPrev(null);
13.               tail=node;
14.               size = 1;
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

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)
node.prev=null----------------------------------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);
8. return;
9. else if(location == 0){
10.
12.    npde.setPrev(null);
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{
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 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
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(){
4.        return;
5.     }else{
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. }

Algorithm

Step 2: if(head is null) return error------------O(1)
Step 3: else
print currentNode.value -----------O(1)

Time Complexity: O(n)
Space Complexity : O(1)

Let's see the code for above algorithm:
1. void ReverseTraverseDDL(){
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){
4.            return ;
5.       }else{
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
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) {
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 {
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
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!!!

Recommended Free Ebook
Similar Articles