Here’s the basic structure of the doubly linked list.

Every linked list has a head and tail node. The Head node has no “prev” (previous pointer) node, and the tail node has no “next” node. Here’re some important terms for a doubly linked list:

Prev: Each node is linked to its previous node. It is used as a pointer or link. Next: Each node is linked to its next node. It is used as a pointer or link. Data: This is used to store data in a node. “Data” can hold other Data Structures inside it. For example, string, dictionary, set, hashmap, etc can be stored in the “Data”.

Here is the basic structure of a single node in the doubly linked list:

Operations of Doubly Linked List

The operations of a doubly linked list include adding and deleting nodes, inserting and removing nodes, and traversing the linked list from the top to the bottom. Here’s the list of operations we can implement using the doubly linked list:

Insertion in front Insertion in the tail or last node Insertion after a node Insertion before a node Deletion from front Deletion from tail Search and delete a node Traverse head to tail Traverse tail to head

We’ll see the implementation and pseudocode for all the operations above.

Insertion in front of Doubly Linked List

Insertion in front means we need to create a node in the linked list and place it at the beginning of the linked list. For example, there’s a given node “15”. We need to add this to the head node. Here’re two important conditions while doing this operation:

The new node will be the head node if there’s no node in the Doubly Linked List. If there’s already a head node, the previous head will be replaced by the new node.

Here’s the pseudo-code for this operation:

function insertAtFront (ListHead, value): newNode = Node() newNode.value = value ListHead.prev = NewNode NewNode.next = ListHead newNode.prev = NULL return ListHead

Insertion at the end of Doubly Linked List

“Insertion at the end” means we will create a node in the linked list and place it at the end. To perform this, we can use two methods:

Method 1: Start traversing from the head of the Doubly Linked List until the “next” becomes null. Then link the new node with the “next”. Method 2: Take the last node of the Doubly Linked List. Then, the “next” node of the last node will link to the new node. Now, the new node will be the tail node.

Here’s the pseudo-code for insertion at the tail node:

function insertAtTail(ListHead, value): newNode = Node() newNode.value = value newNode.next = NULL while ListHead.next is not NULL: then ListHead = ListHead.next newNode.prev = ListHead ListHead.next = newNode return ListHead

Insertion after a node

Let’s say we have an existing doubly linked list like the following:

We want to insert a given node that will be linked after the node, which has the value of “12”. Here’re the steps for this: Step 1) Traverse from the head to the last node. Check which node has the value of “12”. Step 2) Create a new node and assign it as the next pointer of node “12”. The “next” node of the new node will be 15. Here’s the pseudo-code for inserting a node after a node in doubly linked list:

function insertAfter(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.value is not equal searchItem then List = ListHead.next List = List.next NewNode.next = List.next NewNode.prev = List List.next = NewNode

Insertion before a node

This operation is more similar to the “insertion after a node”. We need to search for a specific node’s value to perform this. Then we will create a new node and insert it before the searched node. Let’s say we want to insert a given node “15” before the node “12”. Then here’re the steps for doing it: Step 1) Traverse the linked list from the head node to the tail node. Step 2) Check whether the next pointer of the current node has the value of “12” or not. Step 3) Insert the new node as the “next” node of the current node. Here’s the pseudo-code for inserting a node before a node in doubly Linked List:

function insertBefore(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.next.value is not equal searchItem then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode

Delete the head of the doubly linked list

The head node in the doubly linked list that doesn’t have any previous node. So, the next pointer will be the new head node if we want to delete the head node. We also need to free the memory occupied by a node while deleting a node. Here’re the steps for deleting the head node: Step 1) Assign a variable to the current head node. Step 2) Visit the “next” node of the current head node and make the “prev” (previous pointer) node as ‘’NULL”. This means we are disconnecting the second node from the first node. Step 3) Free the occupied memory by the previous head node. Here’s the pseudo-code for deleting the head from a doubly linked list:

function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead

It is necessary to delete the allocated memory after performing any kind of deletion operation. Otherwise, during the entire runtime of the program, the memory for the deleted block will remain occupied. No other application can use that memory segment.

Delete the tail of the doubly linked list.

This operation is kind of the same as the deletion of the head. Here, instead of the head, we need to delete the tail. To identify a node as a tail node, we should check if the next pointer or next node is null or not. After deleting the tail, we need to free the memory. This operation is also known as the “deletion from the back”. Here’re the steps to do this: Step 1) Traverse until the tail node of the doubly linked list. Step 2) Assign a variable or pointer to the tail node. Step 3) Make the “next” node as NULL and free the memory of the tail node. Here’s the pseudo-code for deleting the tail node:

function DeleteTail( ListHead ): head = ListHead while ListHead.next is not NULL: ListHead = ListHead.next Tail = ListHead.next ListHead.next = NULL free memory( Tail ) return head

Search and delete a node from Doubly Linked List

This operation allows us to search for a specific node data and delete that node. We need to perform a linear search as the linked list is a linear data structure. After deleting, we also need to free the memory. Here’re the steps for searching and deleting a node in the doubly linked list: Step 1) Traverse the linked list from the head until the node’s value equals the search item. Step 2) Assign a variable “deleteNode” to the matched node. Step 3) Assign the previous node of the “deleteNode” to the next node. Step 4) Free the memory of the “deleteNode” Here’s the pseudocode for searching and deleting a node from a linked list:

function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead

Traverse a doubly linked list from forward

To traverse from the head node and iterate over the next node until we find “NULL”. While traversing each node, we can print the value of the node. Here are the steps for traversing from the front (forward direction): Step 1) Assign a pointer or variable to the current head node. Step 2) Iterate to the next node of the head until getting “NULL” Step 3) Print the node’s data in each iteration. Step 4) Return the head node. Here’s the pseudo-code for traversing a Doubly Linked List from the front:

function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead

Here, the return is not mandatory. But it’s a good practice to return the head node after the operations.

Traverse a doubly linked list from the backward

This operation is the inverse of the traverse from the front. The approach is the same with a little difference. We must traverse to the end node and then traverse from the end node to the front node. Here’re the steps for traversing a doubly linked list from the back: Step 1) Traverse until we reach the tail node. Step 2) From the tail node, we will traverse until we get the previous node as “NULL”. The “prev” (previous pointer) will be null for the head node Step 3) At each iteration, we will print the node data. Here’s the pseudo-code for traversing from back:

function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead

Difference between Singly and Doubly linked list

The main difference between Singly and the Doubly Linked list is the number of links.

Here’s the difference between the nodes of a Singly Linked list and the Doubly Linked List’s node structure:

Doubly Linked List in C++

#include using namespace std; struct node{ int data; struct node next; struct node prev; }; void insertFront(node &listHead, int value){ node newNode = new node(); newNode->data = value; newNode->prev = NULL; newNode->next = NULL; if(listHead!=NULL) { listHead->prev = newNode; newNode->next = listHead; }

listHead = newNode; cout«“Added “«value«” at the front”«endl; } void insertEnd(node * &listHead, int value){ if(listHead==NULL) { insertFront(listHead,value); } node* newNode = new node(); newNode->data = value; newNode->prev = NULL; newNode->next = NULL; node head = listHead; while(head->next!=NULL){ head = head->next; } head->next = newNode; newNode->prev = head; cout«“Added “«value«” at the end”«endl; } void insertAfter(node * &listHead, int searchValue,int value){ node newNode = new node(); newNode->data = value; newNode->prev = NULL; newNode->next = NULL; node head = listHead; while(head->next!=NULL && head->data!=searchValue){ head = head->next; } newNode->next = head->next; head->next = newNode; newNode->prev = head; if(newNode->next !=NULL){ newNode->next->prev = newNode; } cout«“Inserted “«value«” after node “«searchValue«endl; } void insertBefore(node * &listHead, int searchValue,int value){ node newNode = new node(); newNode->data = value; newNode->prev = NULL; newNode->next = NULL; node *head = listHead; while(head->next!=NULL && head->next->data!=searchValue){ head = head->next; } newNode->next = head->next; head->next = newNode; newNode->prev = head; if(newNode->next !=NULL){ newNode->next->prev = newNode; } cout«“Inserted “«value«” before node “«searchValue«endl; } void traverseFromFront(node listHead){ node head = new node(); head = listHead; cout«“Traversal from head:\t”; while(head!=NULL){ cout«head->data«"\t “; head = head->next; } cout«endl; } void traverseFromEnd(node listHead){ node head = new node(); head = listHead; cout«“Traversal from head:\t”; while(head->next!=NULL){ head = head->next; } node *tail = head; while(tail!=NULL){ cout«tail->data«"\t”; tail = tail->prev; } cout«endl; } void searchAndDelete(node *listHead, int searchItem){ node head = new node(); head = (*listHead); while(head->next!=NULL && head->data!=searchItem){ head = head->next; } if(*listHead == NULL || head == NULL) return; if((*listHead)->data == head->data){ *listHead = head->next; } if(head->next != NULL){ head->next->prev = head->prev; }

if(head->prev != NULL){ head->prev->next = head->next; } free(head); cout«“Deleted Node\t”«searchItem«endl; return; } int main(){ node *head = NULL; insertFront(head,5); insertFront(head,6); insertFront(head,7); insertEnd(head,9); insertEnd(head,10); insertAfter(head,5,11); insertBefore(head,5,20); traverseFromFront(head); traverseFromEnd(head); searchAndDelete(&head,7); traverseFromFront(head); traverseFromEnd(head); }

Output:

Added 5 at the front Added 6 at the front Added 7 at the front Aded 9 at the end Added 10 at the end Inserted 11 after node 5 Inserted 20 before node 5 Traversal from head: 7 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6

Doubly Linked List in Python

class node: def init(self,data = None, prev=None, next = None): self.data = data self.next = next self.prev = prev class DoublyLinkedList: def init(self): self.head = None

def insertFront(self, val): newNode = node(data=val) newNode.next = self.head if self.head is not None: self.head.prev = newNode self.head = newNode print(“Added {} at the front”.format(val))

def insertEnd(self,val): newNode = node(data=val) if self.head is None: self.insertFront(val)

temp = self.head
while temp.next is not None:
  temp = temp.next
temp.next = newNode
newNode.prev = temp
print("Added {} at the end".format(val))

def traverseFromFront(self): temp = self.head print(“Traversing from head:\t”,end=””) while temp: print(”{}\t”.format(temp.data),end="") temp = temp.next print()

def traverseFromEnd(self): temp = self.head print(“Traversing from Tail:\t”,end="") while temp.next is not None: temp = temp.next tail = temp while tail is not None: print("{}\t".format(tail.data),end="") tail = tail.prev print()

def insertAfter(self,searchItem, value): newNode = node(data=value)

temp = self.head
while temp.next is not None and temp.data is not searchItem:
  temp = temp.next

newNode.next = temp.next
temp.next = newNode
newNode.prev = temp

if newNode.next is not None:
  newNode.next.prev = newNode
print("Inserted {} after node {}".format(value,searchItem))

def insertBefore(self,searchItem, value): newNode = node(data=value)

temp = self.head
while temp.next is not None and temp.next.data is not searchItem:
  temp = temp.next

newNode.next = temp.next
temp.next = newNode
newNode.prev = temp

if newNode.next is not None:
  newNode.next.prev = newNode
print("Inserted {} before node {}".format(value,searchItem))

def searchAndDelete(self,searchItem): temp = self.head

while temp.next is not None and temp.data is not searchItem:
  temp = temp.next

if self.head is None or temp is None:
  return

if self.head.data is temp.data:
  self.head = temp.next

if temp.next is not None:
  temp.next.prev = temp.prev

if temp.prev is not None:
  temp.prev.next = temp.next

print("Deleted Node\t{}".format(searchItem))
return

doublyLinkedList = DoublyLinkedList() doublyLinkedList.insertFront(5) doublyLinkedList.insertFront(6) doublyLinkedList.insertFront(7) doublyLinkedList.insertEnd(9) doublyLinkedList.insertEnd(10) doublyLinkedList.insertAfter(5, 11) doublyLinkedList.insertBefore(5, 20) doublyLinkedList.traverseFromFront() doublyLinkedList.traverseFromEnd() doublyLinkedList.searchAndDelete(7) doublyLinkedList.traverseFromFront() doublyLinkedList.traverseFromEnd()

Output:

Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Added 10 at the end Inserted 11 after node 5 Inserted 20 before node 5 Traversing from head: 7 6 20 5 11 9 10 Traversing from Tail: 10 9 11 5 20 6 7 Deleted Node 7 Traversing from head: 6 20 5 11 9 10 Traversing from Tail: 10 9 11 5 20 6

Complexity of Doubly Linked List

Generally, time complexity is divided in three types. They are:

Best Case Average Case Worst Case

Time complexity in the best case for Doubly Linked List:

Insertion in head or tail will cost O(1). Because we don’t need to traverse inside the linked list. The head and the tail pointer can give us access to the head and tail node with O(1) time complexity. Deletion at the head or tail will cost O(1). Searching a node will have the time complexity of O(1). Because the target node can be the head node.

Time complexity in the average case for Doubly Linked List:

Insertion at the head or tail will have the time complexity of cost O(1). Deletion at the head or tail will have the time complexity of cost O(1). Searching a node will have the time complexity of O(n). Because the search item can reside anywhere between the linked list. Here, “n” is the total node present in the linked list.

The worst-case time complexity of the doubly linked list will be the same as the average case. Memory complexity of Doubly Linked List Memory complexity is O(n), where “n” is the total number of nodes. While implementing the linked list we must free the memory that we used. Otherwise, for a larger linked list, it will cause memory leakages.

Summary:

A linked list is a kind of linear data structure, a collection of data represented in a linear manner. A doubly linked list is a type of linked list where a node has links with both the previous and next node. Doubly linked list contains all the operations like adding a node, deleting a node, inserting a node after or before another node, and traversing the linked list from head to tail. Doubly Linked List has one data field and two links. One for the previous node and another for the next node. Complexity of Doubly Linked List Best Case, Average Case And Worst Case.