Doubly Linked List: C++, Python Example

What is a doubly linked list?

In a doubly linked list, each node has links to both the previous and next node. Each node consists of three elements: one holds the data, and another two are the next and the previous node’s pointers. These two pointers help us to go forward or backward from a particular node.

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

What is a doubly linked list?
Structure of a 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:

What is a doubly linked list?

Structure of a node in a 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:

  1. The new node will be the head node if there’s no node in the Doubly Linked List.
  2. 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 in front node
Insertion in front node

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 at the end of the linked list

Insertion at the end of the linked list

Insertion after a node

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

Insertion after a node

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 after a node

Insertion after a node

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

Inserting a node before a node

Inserting a node before a node

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

Deleting the head node

Deleting the head node

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

Delete the tail of the doubly linked

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

Search and delete operation

Search and delete operation

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.

Difference between Singly and Doubly linked list

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

Field Singly Linked List Doubly Linked List
Structure Singly Linked List has one data field and one link to the next node. Doubly Linked List has one data field and two links. One for the previous node and another for the next node.
Traversal It can only traverse from head to tail. It can traverse both forward and backward.
Memory Occupies less memory. It occupies more memory than a singly linked list.
Accessibility Singly Linked Lists are less efficient as they use only one link to the next node. There’s no link for the previous node. Doubly Linked Lists are more efficient than the Singly Linked Lists.

Doubly Linked List in C++

#include<iostream>
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:

  1. Best Case
  2. Average Case
  3. Worst Case

Time complexity in the best case for Doubly Linked List:

  1. 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.
  2. Deletion at the head or tail will cost O(1).
  3. 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:

  1. Insertion at the head or tail will have the time complexity of cost O(1).
  2. Deletion at the head or tail will have the time complexity of cost O(1).
  3. 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.