Doubly Linked List: C++, Python (Code 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 the other two are pointers to the next and the previous node. These two pointers help move forward or backward from a particular node.

Here is the basic structure of the 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 are 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, and other structures can be stored in the data field.

Here is the basic structure of a single node in the 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, deleting, inserting, and removing nodes, as well as traversing the list from top to bottom or bottom to top.

Here is the list of operations that can be implemented on a Doubly Linked List:

• Insertion in front
• Insertion at 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

The implementation and pseudo-code for each of these operations follow below.

Insertion in Front of Doubly Linked List

Insertion in front means creating a node in the linked list and placing it at the beginning of the list.

For example, there is a given node 15. It needs to be added as the head node.

Two important conditions apply while performing this operation:

1. The new node becomes the head node if the Doubly Linked List is empty.
2. If there is already a head node, the previous head is replaced by the new node.

Here is 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 at the End of Doubly Linked List

Insertion at the end means creating a node in the linked list and placing it at the tail.

Two methods perform this operation:

• Method 1: Start traversing from the head of the Doubly Linked List until next becomes null. Then link the new node with the next pointer.
• Method 2: Take the last node of the Doubly Linked List. Then, the next pointer of the last node points to the new node. The new node becomes the tail node.

Here is 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:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Insertion at the end of the linked list

Insertion After a Node

Consider an existing Doubly Linked List like the following:

The goal is to insert a given node that will be linked after the node with the value 12.

Step 1) Traverse from the head to the last node. Check which node has the value 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 is the pseudo-code for inserting a node after a node in a Doubly Linked List:

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

Insertion after a Node

Insertion Before a Node

This operation is similar to insertion after a node. A specific node value is searched, then a new node is created and inserted before the searched node.

To insert a given node 15 before the node 12, follow these steps:

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 12.

Step 3) Insert the new node as the next node of the current node.

Here is the pseudo-code for inserting a node before a node in a Doubly Linked List:

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

Inserting a Node Before a Node

Delete the Head of the Doubly Linked List

The head node in the Doubly Linked List does not have any previous node. So the next pointer becomes the new head node when the current head is removed. Freeing the memory occupied by a deleted node is also required.

Here are 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 pointer NULL. This disconnects the second node from the first node.

Step 3) Free the memory occupied by the previous head node.

Here is 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

Freeing allocated memory after any deletion is required. Otherwise, the memory for the deleted block remains occupied for the entire runtime of the program, and no other application can use that memory segment.

Delete the Tail of the Doubly Linked List

This operation is similar to deletion of the head. Instead of the head, the tail is removed. To identify a node as the tail, check whether the next pointer is null. After deleting the tail, the memory must be freed.

This operation is also known as deletion from the back.

Here are 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) Set the next pointer to NULL and free the memory of the tail node.

Here is the pseudo-code for deleting the tail node:

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

Search and Delete a Node from Doubly Linked List

This operation searches for a specific node value and deletes that node. A linear search is required because the linked list is a linear data structure. After deleting, the memory must be freed.

Here are 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 value equals the search item.

Step 2) Assign a variable deleteNode to the matched node.

Step 3) Link the previous node of the deleteNode to its next node, and set the next node’s prev pointer to the previous node.

Step 4) Free the memory of the deleteNode.

Here is the pseudo-code for searching and deleting a node from a linked list:

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

Search and delete operation

Traverse a Doubly Linked List From Forward

Traversing from the head node iterates over the next node until NULL is found. While traversing each node, the value can be printed. Here are the steps for traversing in the 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 data in each iteration.

Step 4) Return the head node.

Here is the pseudo-code for traversing a Doubly Linked List from the front:

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

The return is not mandatory. However, returning the head node after operations is good practice.

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 one small difference: reach the end node first, then walk backward to the head using the prev pointer.

Here are the steps for traversing a Doubly Linked List from the back:

Step 1) Traverse until the tail node is reached.

Step 2) From the tail node, traverse using prev until the previous node is NULL. The prev pointer is null for the head node.

Step 3) At each iteration, print the node data.

Here is the pseudo-code for traversing from back:

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

Difference Between Singly and Doubly Linked List

The main difference between a Singly Linked List and a Doubly Linked List is the number of links each node holds.

Here is the difference between the nodes of a Singly Linked List and a Doubly Linked List:

Doubly Linked List in C++

Below is a complete C++ implementation of a Doubly Linked List with insert, delete, search, and traverse operations.

#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);
    return;
  }
  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 = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\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 = (*listHead);
  while(head != 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;
}
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
Added 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 tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Doubly Linked List in Python

Below is a complete Python implementation of a Doubly Linked List using classes for nodes and the list itself.

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.head = newNode
      print("Added {} at the end".format(val))
      return
    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 is not None:
      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 != 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 != 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 is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == 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))
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

Time complexity is generally divided into three types: best case, average case, and worst case.

Time complexity in the best case for Doubly Linked List:

1. Insertion at the head or tail costs O(1) because no traversal inside the linked list is needed. The head and tail pointers give access to the head and tail nodes directly.
2. Deletion at the head or tail costs O(1).
3. Searching a node costs O(1) when the target node is the head node.

Time complexity in the average case for Doubly Linked List:

1. Insertion at the head or tail costs O(1).
2. Deletion at the head or tail costs O(1).
3. Searching a node costs O(n), because the target can reside anywhere in the list. Here, n is the total number of nodes.

The worst-case time complexity of the Doubly Linked List is 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, the memory must be freed. Otherwise, larger linked lists cause memory leaks.

Applications of Doubly Linked List

Doubly Linked Lists power several real-world data structures because bidirectional traversal simplifies many common operations.

• LRU cache: Least-Recently-Used caches use a Doubly Linked List with a hash map for O(1) move-to-front and eviction.
• Browser history: Back and forward navigation walks the linked list in either direction.
• Undo and redo stacks: Editors and IDEs track document versions with prev and next pointers.
• Deque: Double-ended queues push and pop from both ends in O(1) time.
• Music playlists: Previous and next track buttons rely on backward and forward pointers.

FAQs