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:

Insert a new node before Head
Insert a new node at the End of the list
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

Create a blank node and insert a new value in it.
Set the prev value to null, since we are inserting this node in the first position.
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:

We need to create a blank node and insert a new value in it
Set the reference of next to null
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

Create a blank node and insert value in the node
Create a link between the previous node and new node by storing the previous node reference in a temp variable
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:

Delete a node from first postion
Delete a node from last position
Delete a node from middle of linked list

Delete a node from first position

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

Delete a node at last Position

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

Delete the node at the middle of linked list

We need to check if Linked list exists
We need to check if current node is the only element in the linked list
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!!!