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;
  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;
  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){
  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){
  11. node.setNext(head);
  12. npde.setPrev(null);
  13. head.setPrev(node);
  14. head=node;
  16. }else if(location >= size){ // last position
  18. node.setNext(null);
  19. tail.setNext(node);
  20. node.setPrev(tail);
  21. tail= node;
  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. }
  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. }
  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);
  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
  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!!!