09
NovDoubly Linked List in Data Structures with Examples
Doubly Linked Lists in Data Structures: An Overview
We saw that in a Singly Linked List, we could traverse only in one direction from head
to tail
. We can't
travel in reverse i.e. tail
to head
as each node contains the address of the next node and it doesn't have any record of its previous nodes. To overcome this limitation, we have a Doubly Linked List
with us. In this DSA tutorial, we will see the
doubly linked list
data structure in detail i.e. its features, working,
implementation, etc.
To further enhance your understanding and application of linked list concepts, consider enrolling in the Best Dsa Course, to gain comprehensive insights into effective data structure utilization for improved problemsolving and time management.
What is a Doubly Linked List in Data Structures?
A doubly linked list is an enhancement of a singly linked list in which each node consists of 3 components:
 a pointer *prev: address of the previous node
 data: data item
 a pointer *next: address of next node
Representation of a Doubly Linked List in Data Structures
value
and two pointers: prev
to the previous node, and next
to the next node. This allows for traversal in both directions.
The prev
pointer of the first or the head
node of the doubly linked list points toNULL
to mark the start of the list. The next
pointer of the last or the tail
node points toNULL
to mark the end of the list. It is also known as a twoway linked
list as there are two pointers.
Before moving forward, make sure that you are thorough with the concept of pointers
. If not refer to the Pointers in C++ tutorial and come back.
How to declare/create a DoublyLinked List in Data Structures?
Syntax to Declare a Doubly Linked List in Different Languages
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class Node {
Node previous;
int value;
Node next; }
struct node {
int data;
struct node *next;
struct node *prev;
}
Algorithm for the Creation of a Doubly Linked List
Step 1: Define a class or structure (if working with C/C++) Node with three properties:
i. data
ii. prev (pointer to the previous node)
iii. next (pointer to the next node).
Step 2: Initially, initialize all the nodes you want to create with NULL.
Step 3: Allocate memory by assigning values to the nodes.
Step 4: Now, all nodes need to be connected to form a linked list. For this,
i. Assign NULL to the prev pointer of the first node.
ii. Point the prev pointers of all the other nodes except the last one to the previous node in the series.
iii. Point the next pointers of all the nodes except the last one to the upcoming node in the series.
iv. Assign NULL to the next pointer of the last node.
Example of Creating a Doubly Linked List in Data Structures
class Node:
def __init__(self, val):
self.data = val
self.prev = None
self.next = None
# Initialize nodes
head = None
one = Node(1)
two = Node(2)
three = Node(3)
# Connect nodes
one.next = two
one.prev = None
two.next = three
two.prev = one
three.next = None
three.prev = two
# Save the address of the first node in head
head = one
# Print the linked list
current = head
while current:
print(current.data, end=" ")
current = current.next
print()
class Node {
int data;
Node prev;
Node next;
Node(int val) {
data = val;
prev = null;
next = null;
}
}
class Main {
public static void main(String[] args) {
// Initialize nodes
Node head = null;
Node one, two, three;
// Allocate memory
one = new Node(1);
two = new Node(2);
three = new Node(3);
// Connect nodes
one.next = two;
one.prev = null;
two.next = three;
two.prev = one;
three.next = null;
three.prev = two;
// Save the address of the first node in the head
head = one;
// Print the linked list
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
#include <iostream>
// Node structure
struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};
int main() {
// Initialize nodes
Node* head = nullptr;
Node* one = nullptr;
Node* two = nullptr;
Node* three = nullptr;
// Allocate memory
one = new Node(1);
two = new Node(2);
three = new Node(3);
// Connect nodes
one>next = two;
one>prev = nullptr;
two>next = three;
two>prev = one;
three>next = nullptr;
three>prev = two;
// Save the address of the first node in the head
head = one;
// Print the linked list
Node* current = head;
while (current != nullptr) {
std::cout << current>data << " ";
current = current>next;
}
std::cout << std::endl;
// Clean up memory
delete one;
delete two;
delete three;
return 0;
}
In the above code,
one
, two
, and three
are the
nodes with data items 1
, 2
, and 3
respectively.
 For node
one
, the pointernext
stores the address oftwo
, andprev
storesNULL
.  For node
two
, the pointernext
stores the address ofthree
, andprev
stores the address ofone
.  For node
three
,next
storesNULL
, andprev
stores the address oftwo
.  Here
one
is thehead
node and so itsprev
pointer points toNULL
and three is atail
node so itsnext
pointer points toNULL
.
Output
1 2 3
Read More  Data Structure Interview Questions and Answers
Memory Representation of a Doubly Linked List in Data Structures
A Doubly Linked List is represented using the linear Arrays in memory where each memory address stores three components:
 Data
Value
 The memory address of the next element.
 The memory Address of the previous element.
 In the above image,
1
representsNULL
.  Here
1060
,1061
,1062
, etc represent the addresses in the memory, and we traverse the Doubly Linked List until we find 1 in theNext
of the Node. This memory representation shows that theValues
need not be stored contiguously.  You can see that the element
A
hasPrev
= 1 i.e.NULL
, therefore it is the first Node in the Doubly Linked List. A’s
Next
points to memory address1062
, whereB
is stored hence,B
is to the next ofA
. Similarly,
B’s
Next
has a memory address of1069
whereC
is stored.  Similarly,
D
has itsNext
as1
, meaning it's the last Node of this Doubly Linked List.  So it forms the Doubly linked List like
1 ← A ⇆ B ⇆ C ⇆ D → 1
.
Standard Operations on Doubly Linked Lists in Data Structures
 Insertion
Adding a node
to a doubly linked list is similar to adding a node to a
linked
list. The only extra work is to handle the pointer to the previous node. It is faster than linked lists
because we just need to change the pointers of adjacent
elements of the element we are inserting.
Generalized Algorithm for Insertion in a Doubly Linked List
Step 1: Create a new node with the given data.
Step 2: If the doubly linked list is empty:
i. Set the head and tail pointers point to the new node.
ii. make the new node's prev and next pointers point to NULL.
Step 3: If the doubly linked list is not empty:
i. Perform the insertion as per your requirement, either in the beginning, end, or at a given position.
In the above given doubly linked list, Insertion can be done in three ways:
 Insertion at the beginning: Here, we insert the newly created node before the
head
node, and thehead
points to the new node.Let us understand this with an illustration. Suppose we want to insert a node with value
6
at the beginning of the given doubly linked list. The following three steps to accomplish this operation: Create a new node
 allocate memory for new Node
 assign the
data
to the new Node
.  Set
prev
andnext
pointers of the new node  point
next
of new Node to thefirst
node of the doubly linked list  point
prev
toNULL
 Make new node the
head
node  Point
prev
of the first node to new Node (now the previous head is the second node)  Point
head
to new Node
Example of Insertion at the Beginning of a Doubly Linked List
class Node: def __init__(self, data): self.data = data self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None # Function to insert a node at the front of the doubly linked list def insert_front(self, data): # Allocate memory for newNode new_node = Node(data) # Point next of newNode to the first node of the doubly linked list new_node.next = self.head # Point prev to None new_node.prev = None # Point previous of the first node (now the first node is the second node) to newNode if self.head is not None: self.head.prev = new_node # Head points to newNode self.head = new_node # Function to print the elements of the doubly linked list def print_list(self): current = self.head while current: print(current.data, end=" ") current = current.next print() # Creating a sample doubly linked list with nodes 1, 2, 3 my_list = DoublyLinkedList() my_list.head = Node(1) second = Node(2) third = Node(3) my_list.head.next = second second.prev = my_list.head second.next = third third.prev = second print("Original list:", end=" ") my_list.print_list() # Inserting node with data 6 at the front my_list.insert_front(6) print("List after inserting node with data 6 in the beginning:", end=" ") my_list.print_list()
class Node { int data; Node prev; Node next; Node(int val) { data = val; prev = null; next = null; } } class DoublyLinkedList { Node head; // Function to insert a node at the front of the doubly linked list void insertFront(int data) { // Allocate memory for newNode Node newNode = new Node(data); // Point next of newNode to the first node of the doubly linked list newNode.next = head; // Point prev to null newNode.prev = null; // Point previous of the first node (now the first node is the second node) to newNode if (head != null) head.prev = newNode; // Head points to newNode head = newNode; } // Function to print the elements of the doubly linked list void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { // Creating a sample doubly linked list with nodes 1, 2, 3 DoublyLinkedList myList = new DoublyLinkedList(); myList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); myList.head.next = second; second.prev = myList.head; second.next = third; third.prev = second; System.out.print("Original list: "); myList.printList(); // Inserting node with data 6 at the front myList.insertFront(6); System.out.print("List after inserting node with data 6 in the beginning: "); myList.printList(); } }
#include <iostream> struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; // Function to insert a node at the front of the doubly linked list void insertFront(Node** head, int data) { // Allocate memory for newNode Node* newNode = new Node(data); // Point next of newNode to the first node of the doubly linked list newNode>next = (*head); // Point prev to NULL newNode>prev = nullptr; // Point previous of the first node (now the first node is the second node) to newNode if ((*head) != nullptr) (*head)>prev = newNode; // Head points to newNode (*head) = newNode; } // Function to print the elements of the doubly linked list void printList(Node* head) { Node* current = head; while (current != nullptr) { std::cout << current>data << " "; current = current>next; } std::cout << std::endl; } int main() { // Creating a sample doubly linked list with nodes 1, 2, 3 Node* myList = new Node(1); Node* second = new Node(2); Node* third = new Node(3); myList>next = second; second>prev = myList; second>next = third; third>prev = second; std::cout << "Original list: "; printList(myList); // Inserting node with data 6 at the front insertFront(&myList, 6); std::cout << "List after inserting node with data 6 in the beginning: "; printList(myList); return 0; }
Output
Original list: 1 2 3 List after inserting node with data 6 in the beginning: 6 1 2 3
 Insertion at a specific position/in between the nodes: Suppose, we have to insert a node at the position of
let's say
Node X
. The steps to be followed are: Traverse the doubly linked list to the position of
Node X
.  Change the
next
pointer of the new Node to thenext
pointer ofNode X
.  Change the
prev
pointer of the node following theNode X
to the new Node.  Change the
next
pointer ofNode X
to the new Node.  Change the
prev
pointer of the new Node toNode X
.
Let us understand this with an illustration. Suppose we want to insert a node with value
6
after the second node with value2
in the given doubly linked list. The following three steps to accomplish this operation: Create a new node
 allocate memory for new Node.
 assign the
data
to new Node.  Set the
next
pointer of the new node and the previous node.  assign the value of
next
from the previous node to thenext
of new Node.  assign the address of the new Node to the
next
of the previous node.  Set the
prev
pointer ofnew
node and thenext
node.  assign the value of
prev
of next node to theprev
of new Node.  assign the address of the new Node to the
prev
of next node
Example of Insertion in Between or at a Given Position in a Doubly Linked List
class Node: def __init__(self, val): self.data = val self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None # Function to insert a node after a specific node def insert_after(self, prev_node, data): # Check if the previous node is None if prev_node is None: print("Previous node cannot be None") return # Allocate memory for newNode new_node = Node(data) # Set next of newNode to next of prev node new_node.next = prev_node.next # Set next of prev node to newNode prev_node.next = new_node # Set prev of newNode to the previous node new_node.prev = prev_node # Set prev of newNode's next to newNode if new_node.next is not None: new_node.next.prev = new_node # Function to print the elements of the doubly linked list def print_list(self): current = self.head while current is not None: print(current.data, end=" ") current = current.next print() # Creating a sample doubly linked list my_list = DoublyLinkedList() my_list.head = Node(1) second = Node(2) third = Node(3) my_list.head.next = second second.prev = my_list.head second.next = third third.prev = second print("Original list:", end=" ") my_list.print_list() # Inserting a node with data 6 after the second node (with data 2) my_list.insert_after(second, 6) print("List after inserting node with data 6 after node with data 2:", end=" ") my_list.print_list()
class Node { int data; Node prev; Node next; public Node(int val) { data = val; prev = null; next = null; } } class DoublyLinkedList { Node head; public DoublyLinkedList() { head = null; } // Function to insert a node after a specific node void insertAfter(Node prevNode, int data) { // Check if the previous node is null if (prevNode == null) { System.out.println("Previous node cannot be null"); return; } // Allocate memory for newNode Node newNode = new Node(data); // Set next of newNode to next of prev node newNode.next = prevNode.next; // Set next of prev node to newNode prevNode.next = newNode; // Set prev of newNode to the previous node newNode.prev = prevNode; // Set prev of newNode's next to newNode if (newNode.next != null) { newNode.next.prev = newNode; } } // Function to print the elements of the doubly linked list void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { // Creating a sample doubly linked list DoublyLinkedList myList = new DoublyLinkedList(); myList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); myList.head.next = second; second.prev = myList.head; second.next = third; third.prev = second; System.out.print("Original list: "); myList.printList(); // Inserting a node with data 6 after the second node (with data 2) myList.insertAfter(second, 6); System.out.print("List after inserting node with data 6 after node with data 2: "); myList.printList(); } }
#include <iostream> struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; class DoublyLinkedList { public: Node* head; DoublyLinkedList() : head(nullptr) {} // Function to insert a node after a specific node void insertAfter(Node* prev_node, int data) { // Check if the previous node is NULL if (prev_node == nullptr) { std::cout << "Previous node cannot be NULL" << std::endl; return; } // Allocate memory for newNode Node* newNode = new Node(data); // Set next of newNode to next of prev node newNode>next = prev_node>next; // Set next of prev node to newNode prev_node>next = newNode; // Set prev of newNode to the previous node newNode>prev = prev_node; // Set prev of newNode's next to newNode if (newNode>next != nullptr) newNode>next>prev = newNode; } // Function to print the elements of the doubly linked list void printList() { Node* current = head; while (current != nullptr) { std::cout << current>data << " "; current = current>next; } std::cout << std::endl; } }; int main() { // Creating a sample doubly linked list DoublyLinkedList myList; myList.head = new Node(1); Node* second = new Node(2); Node* third = new Node(3); myList.head>next = second; second>prev = myList.head; second>next = third; third>prev = second; std::cout << "Original list: "; myList.printList(); // Inserting a node with data 6 after the second node (with data 2) myList.insertAfter(second, 6); std::cout << "List after inserting node with data 6 after node with data 2: "; myList.printList(); return 0; }
Output
Original list: 1 2 3 List after inserting node with data 6 after node with data 2: 1 2 6 3
 Traverse the doubly linked list to the position of
 Insertion at the end: Here, we insert the newly created node at the end of the list or after the
tail
node, and thetail
points to the new node.Let us understand this with an illustration. Suppose we want to insert a node with value
6
at the end of the given doubly linked list. The following two steps to accomplish this operation: Create a new node
 Set
prev
andnext
pointers of the new node and the previous node If the linked list is empty, make the new Node as thehead
node. Otherwise, traverse to the end of the doubly linked list.
The final doubly linked list after this insertion is:
Example of Insertion at the End of a Doubly Linked List
class Node: def __init__(self, val): self.data = val self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None # Function to insert a new node at the end of the list def insert_end(self, data): # Allocate memory for node new_node = Node(data) # Assign NULL to next of new_node new_node.next = None # Store the head node temporarily (for later use) temp = self.head # If the linked list is empty, make the new_node as the head node if self.head is None: new_node.prev = None self.head = new_node return # If the linked list is not empty, traverse to the end of the linked list while temp.next is not None: temp = temp.next # Now, the last node of the linked list is temp # Point the next of the last node (temp) to new_node. temp.next = new_node # Assign prev of new_node to temp new_node.prev = temp # Function to print the elements of the doubly linked list def print_list(self): current = self.head while current is not None: print(current.data, end=" ") current = current.next print() # Creating a sample doubly linked list with values 1, 2, 3 my_list = DoublyLinkedList() my_list.head = Node(1) second = Node(2) third = Node(3) my_list.head.next = second second.prev = my_list.head second.next = third third.prev = second print("Original list:", end=" ") my_list.print_list() # Inserting node with value 6 my_list.insert_end(6) # Printing the updated list print("List after inserting node 6 at the end:", end=" ") my_list.print_list()
class Node { int data; Node prev; Node next; public Node(int val) { data = val; prev = null; next = null; } } class DoublyLinkedList { Node head; // Function to insert a new node at the end of the list void insertEnd(int data) { // Allocate memory for node Node newNode = new Node(data); // Assign NULL to next of newNode newNode.next = null; // Store the head node temporarily (for later use) Node temp = head; // If the linked list is empty, make the newNode as the head node if (head == null) { newNode.prev = null; head = newNode; return; } // If the linked list is not empty, traverse to the end of the linked list while (temp.next != null) temp = temp.next; // Now, the last node of the linked list is temp // Point the next of the last node (temp) to newNode. temp.next = newNode; // Assign prev of newNode to temp newNode.prev = temp; } // Function to print the elements of the doubly linked list void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { // Creating a sample doubly linked list with values 1, 2, 3 DoublyLinkedList myList = new DoublyLinkedList(); myList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); myList.head.next = second; second.prev = myList.head; second.next = third; third.prev = second; System.out.print("Original list: "); myList.printList(); // Inserting node with value 6 myList.insertEnd(6); // Printing the updated list System.out.print("List after inserting node 6 at the end: "); myList.printList(); } }
#include <iostream> struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; // Function to insert a new node at the end of the list void insertEnd(Node** head, int data) { // Allocate memory for node Node* newNode = new Node(data); // Assign NULL to next of newNode newNode>next = nullptr; // Store the head node temporarily (for later use) Node* temp = *head; // If the linked list is empty, make the newNode as the head node if (*head == nullptr) { newNode>prev = nullptr; *head = newNode; return; } // If the linked list is not empty, traverse to the end of the linked list while (temp>next != nullptr) temp = temp>next; // Now, the last node of the linked list is temp // Point the next of the last node (temp) to newNode. temp>next = newNode; // Assign prev of newNode to temp newNode>prev = temp; } // Function to print the elements of the doubly linked list void printList(Node* head) { Node* current = head; while (current != nullptr) { std::cout << current>data << " "; current = current>next; } std::cout << std::endl; } int main() { // Creating a sample doubly linked list with values 1, 2, 3 Node* myList = new Node(1); Node* second = new Node(2); Node* third = new Node(3); myList>next = second; second>prev = myList; second>next = third; third>prev = second; std::cout << "Original list: "; printList(myList); // Inserting node with value 6 insertEnd(&myList, 6); // Printing the updated list std::cout << "List after inserting node 6 at the end: "; printList(myList); return 0; }
Output
Original list: 1 2 3 List after inserting node 6 at the end: 1 2 3 6
 Deletion
Similar to Insertion, deletion in a Doubly Linked List is also fast. It can be done by just changing the pointers
of its adjacent Nodes.
In the above given doubly linked list, deletion can also be done in three ways:
 Deletion at the beginning: Here, we will move the
head
to thenext
node to delete the node at the beginning and make the previous pointer of the currenthead
point toNULL
.Let us understand this with an illustration. Suppose we want to delete the first node with the value 1 at the beginning of the given doubly linked list. The following two steps to accomplish this operation:
 Reset value node after the
del_node
(i.e. node two)  free the memory of
del_node
. And, the linked list will look like this:
Example of Deletion of the First Node of a Doubly Linked List
class Node: def __init__(self, val): self.data = val self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None # Function to delete a node from the doubly linked list def delete_node(self, del_node): # Check if del_node is the head of the linked list if self.head == del_node: self.head = del_node.next # Update the next pointer of the previous node (if del_node is not the head) if del_node.prev is not None: del_node.prev.next = del_node.next # Update the prev pointer of the next node (if del_node is not the last node) if del_node.next is not None: del_node.next.prev = del_node.prev # Free the memory allocated for del_node (Python automatically handles memory) # Function to print the elements of the doubly linked list def print_list(self): current = self.head while current is not None: print(current.data, end=" ") current = current.next print() # Creating a sample doubly linked list with values 1, 2, 3 my_list = DoublyLinkedList() my_list.head = Node(1) second = Node(2) third = Node(3) my_list.head.next = second second.prev = my_list.head second.next = third third.prev = second print("Original list:", end=" ") my_list.print_list() # Deleting the head node (with data 1) from the list my_list.delete_node(my_list.head) print("List after deleting the head node with data 1:", end=" ") my_list.print_list()
class Node { int data; Node prev; Node next; public Node(int val) { data = val; prev = null; next = null; } } class DoublyLinkedList { Node head; // Function to delete a node from the doubly linked list void deleteNode(Node delNode) { // Check if delNode is the head of the linked list if (head == delNode) head = delNode.next; // Update the next pointer of the previous node (if delNode is not the head) if (delNode.prev != null) delNode.prev.next = delNode.next; // Update the prev pointer of the next node (if delNode is not the last node) if (delNode.next != null) delNode.next.prev = delNode.prev; // Free the memory allocated for delNode (Java automatically handles memory) } // Function to print the elements of the doubly linked list void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { // Creating a sample doubly linked list with values 1, 2, 3 DoublyLinkedList myList = new DoublyLinkedList(); myList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); myList.head.next = second; second.prev = myList.head; second.next = third; third.prev = second; System.out.print("Original list: "); myList.printList(); // Deleting the head node (with data 1) from the list myList.deleteNode(myList.head); System.out.print("List after deleting the head node with data 1: "); myList.printList(); } }
#include <iostream> struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; // Function to delete a node from the doubly linked list void deleteNode(Node** head, Node* del_node) { // Check if del_node is the head of the linked list if (*head == del_node) *head = del_node>next; // Update the next pointer of the previous node (if del_node is not the head) if (del_node>prev != nullptr) del_node>prev>next = del_node>next; // Update the prev pointer of the next node (if del_node is not the last node) if (del_node>next != nullptr) del_node>next>prev = del_node>prev; // Free the memory allocated for del_node delete del_node; } // Function to print the elements of the doubly linked list void printList(Node* head) { Node* current = head; while (current != nullptr) { std::cout << current>data << " "; current = current>next; } std::cout << std::endl; } int main() { // Creating a sample doubly linked list with values 1, 2, 3 Node* myList = new Node(1); Node* second = new Node(2); Node* third = new Node(3); myList>next = second; second>prev = myList; second>next = third; third>prev = second; std::cout << "Original list: "; printList(myList); // Deleting the head node (with data 1) from the list deleteNode(&myList, myList); std::cout << "List after deleting the head node with data 1: "; printList(myList); return 0; }
Output
Original list: 1 2 3 List after deleting head node with data 1: 2 3
 Reset value node after the
 Deletion at a specific position: To remove a node from a specific position in the list, you need to
traverse the list until you reach the desired position. Let the previous node of the Node be deleted at position
pos
beNode X
and the next node beNode Y
. The steps to be followed are: Change the
next
pointer ofNode X
toNode Y
.  Change the
prev
pointer ofNode Y
toNode X
.
Let us understand this with an illustration. Suppose we want to delete the
second node
with value2
after thefirst node
with value1
in the given doubly linked list. The following three steps to accomplish this operation: For the node before the
del_node
(i.e. first node) Assign the value of the
next
ofdel_node
to thenext
of the first node.
 Assign the value of the
 For the node after the
del_node
(i.e. third node) Assign the value of
prev
ofdel_node
to theprev
of the third node.
 Assign the value of
 Finally, we will free the memory of
del_node
. And, the final doubly linked list looks like this.
Example of Deletion of an Inner Node in Between the Doubly Linked List
class Node: def __init__(self, val): self.data = val self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None # Function to remove a node from the doubly linked list def remove_node(self, del_node): if del_node.next is not None: del_node.next.prev = del_node.prev if del_node.prev is not None: del_node.prev.next = del_node.next # Optionally free the memory of the deleted node del_node = None # Function to print the elements of the doubly linked list def print_list(self): current = self.head while current is not None: print(current.data, end=" ") current = current.next print() # Creating a sample doubly linked list my_list = DoublyLinkedList() my_list.head = Node(1) second = Node(2) third = Node(3) my_list.head.next = second second.prev = my_list.head second.next = third third.prev = second print("Original list:", end=" ") my_list.print_list() # Removing the second node (with data 2) from the list my_list.remove_node(second) print("List after removing node with data 2:", end=" ") my_list.print_list()
class Node { int data; Node prev; Node next; public Node(int val) { data = val; prev = null; next = null; } } class DoublyLinkedList { Node head; public DoublyLinkedList() { head = null; } // Function to remove a node from the doubly linked list void removeNode(Node delNode) { if (delNode.next != null) delNode.next.prev = delNode.prev; if (delNode.prev != null) delNode.prev.next = delNode.next; // Optionally free the memory of the deleted node delNode = null; } // Function to print the elements of the doubly linked list void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { // Creating a sample doubly linked list DoublyLinkedList myList = new DoublyLinkedList(); myList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); myList.head.next = second; second.prev = myList.head; second.next = third; third.prev = second; System.out.print("Original list: "); myList.printList(); // Removing the second node (with data 2) from the list myList.removeNode(second); System.out.print("List after removing node with data 2: "); myList.printList(); } }
#include <iostream> struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; class DoublyLinkedList { public: Node* head; DoublyLinkedList() : head(nullptr) {} // Function to remove a node from the doubly linked list void removeNode(Node* del_node) { if (del_node>next != nullptr) del_node>next>prev = del_node>prev; if (del_node>prev != nullptr) del_node>prev>next = del_node>next; // Optionally free the memory of the deleted node delete del_node; } // Function to print the elements of the doubly linked list void printList() { Node* current = head; while (current != nullptr) { std::cout << current>data << " "; current = current>next; } std::cout << std::endl; } }; int main() { // Creating a sample doubly linked list DoublyLinkedList myList; myList.head = new Node(1); Node* second = new Node(2); Node* third = new Node(3); myList.head>next = second; second>prev = myList.head; second>next = third; third>prev = second; std::cout << "Original list: "; myList.printList(); // Removing the second node (with data 2) from the list myList.removeNode(second); std::cout << "List after removing node with data 2: "; myList.printList(); return 0; }
Output
Original list: 1 2 3 List after removing node with data 2: 1 3
 Change the
 Deletion at the end: Here we will move the
tail
to the previous node to delete the node at the end and make thenext
pointer of thetail
node point toNULL
.Let us understand this with an illustration. Suppose we want to delete the last node with the value 3 at the end of the given doubly linked list.
 delete the
del_node
and make thenext
of node beforedel_node
point toNULL
.  The final doubly linked list looks like this.
Example of Deletion of the Last Node of Doubly Linked List
class Node: def __init__(self, val): self.data = val self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None # Function to delete the last node from the doubly linked list def delete_last_node(self): # Check if the linked list is empty if self.head is None: print("List is empty. Cannot delete last node.") return # Traverse to the last node temp = self.head while temp.next is not None: temp = temp.next # Check if the list has only one node if temp.prev is None: self.head = None # Set head to None as the list is now empty else: # Update the next pointer of the previous node to None temp.prev.next = None # Function to print the elements of the doubly linked list def print_list(self): current = self.head while current is not None: print(current.data, end=" ") current = current.next print() # Creating a sample doubly linked list with values 1, 2, 3 my_list = DoublyLinkedList() my_list.head = Node(1) second = Node(2) third = Node(3) my_list.head.next = second second.prev = my_list.head second.next = third third.prev = second print("Original list:", end=" ") my_list.print_list() # Deleting the last node from the list my_list.delete_last_node() print("List after deleting the last node:", end=" ") my_list.print_list()
class Node { int data; Node prev; Node next; public Node(int val) { data = val; prev = null; next = null; } } class DoublyLinkedList { Node head; // Function to delete the last node from the doubly linked list void deleteLastNode() { // Check if the linked list is empty if (head == null) { System.out.println("List is empty. Cannot delete last node."); return; } // Traverse to the last node Node temp = head; while (temp.next != null) temp = temp.next; // Check if the list has only one node if (temp.prev == null) { head = null; // Set head to null as the list is now empty } else { // Update the next pointer of the previous node to null temp.prev.next = null; } } // Function to print the elements of the doubly linked list void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { // Creating a sample doubly linked list with values 1, 2, 3 DoublyLinkedList myList = new DoublyLinkedList(); myList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); myList.head.next = second; second.prev = myList.head; second.next = third; third.prev = second; System.out.print("Original list: "); myList.printList(); // Deleting the last node from the list myList.deleteLastNode(); System.out.print("List after deleting the last node: "); myList.printList(); } }
#include <iostream> struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; // Function to delete the last node from the doubly linked list void deleteLastNode(Node** head) { // Check if the linked list is empty if (*head == nullptr) { std::cout << "List is empty. Cannot delete last node." << std::endl; return; } // Traverse to the last node Node* temp = *head; while (temp>next != nullptr) temp = temp>next; // Check if the list has only one node if (temp>prev == nullptr) { delete temp; *head = nullptr; // Set head to null as the list is now empty } else { // Update the next pointer of the previous node to null temp>prev>next = nullptr; delete temp; } } // Function to print the elements of the doubly linked list void printList(Node* head) { Node* current = head; while (current != nullptr) { std::cout << current>data << " "; current = current>next; } std::cout << std::endl; } int main() { // Creating a sample doubly linked list with values 1, 2, 3 Node* myList = new Node(1); Node* second = new Node(2); Node* third = new Node(3); myList>next = second; second>prev = myList; second>next = third; third>prev = second; std::cout << "Original list: "; printList(myList); // Deleting the last node from the list deleteLastNode(&myList); std::cout << "List after deleting the last node: "; printList(myList); return 0; }
Output
Original list: 1 2 3 List after deleting the last node: 1 2
 delete the
 Traversal
You can traverse the doubly linked list in both directions. We can go to the previous node by following the
previous pointers and similarly go to the next nodes by following the next
pointers to perform some specific operations like searching, sorting,
display, etc.
Algorithm for Traversing a Doubly Linked List
Step 1. Set a pointer current to the head of the doubly linked list.
Step 2. If the doubly linked list is empty (i.e., current is null), then the traversal is complete.
Step 3. While the current pointer is not null:
a. Process the data of the current node.
b. Move the current pointer to the next node (current = current>next).
or
b. Move the 'current' pointer to the previous node (current = current>prev)
Step 4. The traversal is complete when the 'current' pointer becomes null.
Example of Traversing a Doubly Linked List
class Node:
def __init__(self, val):
self.value = val
self.previous = None
self.next = None
class DoublyLinkedList:
def traverse_forward(self, start):
current = start
# Checks whether the list is empty
if start is None:
print("Node to start from is NULL")
return
while current is not None:
print("Node:", current.value)
current = current.next
def traverse_backward(self, start):
current = start
# Checks whether the list is empty
if start is None:
print("Node to start from is NULL")
return
while current is not None:
print("Node:", current.value)
current = current.previous
# Creating a sample doubly linked list
first = Node(1)
second = Node(2)
third = Node(3)
first.next = second
second.previous = first
second.next = third
third.previous = second
my_list = DoublyLinkedList()
print("Traversing forward:")
my_list.traverse_forward(first)
print("Traversing backward:")
my_list.traverse_backward(third)
class Node {
int value;
Node previous;
Node next;
public Node(int val) {
value = val;
previous = null;
next = null;
}
}
class DoublyLinkedList {
void traverseForward(Node start) {
Node current = start;
// Checks whether the list is empty
if (start == null) {
System.out.println("Node to start from is NULL");
return;
}
while (current != null) {
System.out.println("Node: " + current.value);
current = current.next;
}
}
void traverseBackward(Node start) {
Node current = start;
// Checks whether the list is empty
if (start == null) {
System.out.println("Node to start from is NULL");
return;
}
while (current != null) {
System.out.println("Node: " + current.value);
current = current.previous;
}
}
}
class Main {
public static void main(String[] args) {
// Creating a sample doubly linked list
Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
first.next = second;
second.previous = first;
second.next = third;
third.previous = second;
DoublyLinkedList myList = new DoublyLinkedList();
System.out.println("Traversing forward:");
myList.traverseForward(first);
System.out.println("Traversing backward:");
myList.traverseBackward(third);
}
}
#include <iostream>
class Node {
public:
int value;
Node* previous;
Node* next;
Node(int val) : value(val), previous(nullptr), next(nullptr) {}
};
class DoublyLinkedList {
public:
void traverseForward(Node* start) {
Node* current = start;
// Checks whether the list is empty
if (start == nullptr) {
std::cout << "Node to start from is NULL" << std::endl;
return;
}
while (current != nullptr) {
std::cout << "Node: " << current>value << std::endl;
current = current>next;
}
}
void traverseBackward(Node* start) {
Node* current = start;
// Checks whether the list is empty
if (start == nullptr) {
std::cout << "Node to start from is NULL" << std::endl;
return;
}
while (current != nullptr) {
std::cout << "Node: " << current>value << std::endl;
current = current>previous;
}
}
};
int main() {
// Creating a sample doubly linked list
Node* first = new Node(1);
Node* second = new Node(2);
Node* third = new Node(3);
first>next = second;
second>previous = first;
second>next = third;
third>previous = second;
DoublyLinkedList myList;
std::cout << "Traversing forward:" << std::endl;
myList.traverseForward(first);
std::cout << "Traversing backward:" << std::endl;
myList.traverseBackward(third);
// Clean up memory (delete nodes)
delete third;
delete second;
delete first;
return 0;
}
Output
Traversing forward:
Node: 1
Node: 2
Node: 3
Traversing backward:
Node: 3
Node: 2
Node: 1
 Search
To search in the given doubly linked list, we need to traverse the entire doubly linked list from the first node and
keep moving to the next nodes using the next
pointer. We can compare
each transversed element against the one we are searching for.
Step 1. Start with a pointer current at the head of the doubly linked list.
Step 2. If the doubly linked list is empty (i.e., current is null), the value is not found.
Step 3. While the current pointer is not null:
a. Check if the data in the current node is equal to the target value.
 If yes, the value is found, and you can return the node or its position.
b. Move the current pointer to the next node (current = current>next).
Step 4. If the current pointer becomes null and the value is not found, then the value is not present in the list.
Example of Searching in a Doubly Linked List
class Node:
def __init__(self, val):
self.value = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def search_node(self, value):
i = 1
# Node current will point to head
current = self.head
# Checks whether the list is empty
if self.head is None:
print("List is empty")
return
# Traversing the List.
while current is not None:
# Compare value to be searched with each node in the list
if current.value == value:
print(f"Node {value} is present in the list at the position: {i}")
return
current = current.next
i += 1
print(f"Node {value} is not present in the list")
# Creating a sample linked list
my_list = LinkedList()
my_list.head = Node(7)
my_list.head.next = Node(8)
my_list.head.next.next = Node(9)
my_list.head.next.next.next = Node(4)
# Searching for a node in the linked list
my_list.search_node(8)
my_list.search_node(6)
class Node {
int value;
Node next;
Node(int val) {
value = val;
next = null;
}
}
class LinkedList {
Node head;
void searchNode(int value) {
int i = 1;
// Node current will point to head
Node current = head;
// Checks whether the list is empty
if (head == null) {
System.out.println("List is empty");
return;
}
// Traversing the List.
while (current != null) {
// Compare value to be searched with each node in the list
if (current.value == value) {
System.out.println("Node " + value + " is present in the list at the position: " + i);
return;
}
current = current.next;
i++;
}
System.out.println("Node " + value + " is not present in the list");
}
public static void main(String[] args) {
// Creating a sample linked list
LinkedList myList = new LinkedList();
myList.head = new Node(7);
myList.head.next = new Node(8);
myList.head.next.next = new Node(9);
myList.head.next.next.next = new Node(4);
// Searching for a node in the linked list
myList.searchNode(8);
myList.searchNode(6);
}
}
#include <iostream>
class Node {
public:
int value;
Node* next;
Node(int val) : value(val), next(nullptr) {}
};
class LinkedList {
public:
Node* head;
void searchNode(int value) {
int i = 1;
// Node current will point to head
Node* current = head;
// Checks whether the list is empty
if (head == nullptr) {
std::cout << "List is empty" << std::endl;
return;
}
// Traversing the List.
while (current != nullptr) {
// Compare value to be searched with each node in the list
if (current>value == value) {
std::cout << "Node " << value << " is present in the list at the position: " << i << std::endl;
return;
}
current = current>next;
i++;
}
std::cout << "Node " << value << " is not present in the list" << std::endl;
}
};
int main() {
// Creating a sample linked list
LinkedList myList;
myList.head = new Node(7);
myList.head>next = new Node(8);
myList.head>next>next = new Node(9);
myList.head>next>next>next = new Node(4);
// Searching for a node in the linked list
myList.searchNode(8);
myList.searchNode(6);
return 0;
}
Output
Node 8 is present in the list at the position: 2
Node 6 is not present in the list
Complexity Analysis of Doubly Linked List Operations
Operations  Time Complexity  Space Complexity 
Insertion at the beginning 


Insertion at a specific position 


Insertion at the end 


Deletion at the beginning 


Deletion at a specific position 


Deletion at the end 


Traversal 


Search 


Singly Linked List Vs Doubly Linked List
Singly linked list (SLL)  Doubly Linked List (DLL) 
SLL nodes contain 2 fields the data field and the next link field.  DLL nodes contain 3 fields  the data field, a previous link field, and a next link field. 
In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only.  In DLL, the traversal can be done using the previous nodelink or the next node link. Thus traversal is possible in both directions (forward and backward). 
The SLL occupies less memory than DLL as it has only 2 fields.  The DLL occupies more memory than SLL as it has 3 fields. 
The complexity of insertion and deletion at a given position is O(n).  The complexity of insertion and deletion at a given position is O(n / 2) = O(n) because traversal can be made from the start or the end. 
Complexity of deletion with a given node is O(n), because the previous node needs to be known, and traversal takes O(n)  Complexity of deletion with a given node is O(1) because the previous node can be accessed easily 
We mostly prefer to use singly linked list for the execution of stacks.  We can use a doubly linked list to execute heaps, stacks, binary trees, etc. 
When we do not need to perform any searching operation and we want to save memory, we prefer a singly linked list.  In case of better implementation, while searching, we prefer to use a doubly linked list. 
A singly linked list consumes less memory as compared to a doubly linked list.  The doubly linked list consumes more memory as compared to the singly linked list. 
It is less efficient as compared to a doublylinked list.  It is more efficient. 
Applications of Doubly Linked List
 Browser History:A doubly linked list is an ideal data structure for implementing a browser history because it allows users to navigate forward and backward through the pages they have visited.
 Music and Video Player: Doubly linked lists can be used to implement a music or video player's playlist. The links between the nodes allow users to navigate through the playlist in both the forward and backward directions.
 Text Editor: Text editors use doubly linked lists to implement the undo and redo features. Each node in the list represents the state of the document, and the links between the nodes allow users to navigate through the document's history.
 Cache: A cache is a temporary storage area used to speed up data access. Doubly linked lists can be used to implement a cache, with the most recently accessed data at the head of the list and the least recently accessed data at the tail.
 Operating System: Doubly linked lists are used in many operating systems for various purposes, such as managing processes, allocating memory, and handling input/output operations.
 File System: File systems use doubly linked lists to implement file directories. Each node in the list represents a file or a directory, and the links between the nodes allow users to navigate through the file system's directory structure
Advantages of Doubly Linked List
 Efficient insertion and deletion: Unlike arrays, which require shifting of elements to insert or delete an element, doubly linked lists only require changing the pointers of the adjacent nodes.
 Bidirectional traversal: The two pointers in each node allow for bidirectional traversal of the linked list, meaning the developer can traverse the list forward and backward. This is particularly useful in situations where the a need to search for elements or perform operations from both ends of the list.
 Flexibility: Because nodes in a doubly linked list have pointers to both the previous and next nodes, they can be easily removed from the list or inserted into the list without affecting the rest of the nodes. This makes doubly linked lists very flexible and adaptable to different situations.
 Memory efficiency: The doubly linked list can be used to manage memory efficiently, as nodes can be easily added or removed as needed.
 Implementing other data structures:It can be used to implement different tree data structures.
Disadvantages of Doubly Linked List
 Memory usage: Doubly linked lists require more memory than singlylinked lists, as they need to store a pointer to the previous node in addition to the next node.
 Slower access and search times: Access and search operations have
O(n)
time complexity, wheren
is the number of elements in the list. This can result in slower performance than other data structures like arrays or trees, especially for large lists.  Traversal: Traversing a doubly linked list can also be slower than traversing an array or singly linked list, as it requires following both the previous and next pointers.
 Complexity: The use of doubly linked lists can add complexity to the code and increase the risk of bugs, as there are more pointers to manage and more edge cases to consider.
 Not suitable for some algorithms: Some algorithms may require random access to elements in a list, which is not efficient with doubly linked lists.
 Extra work for maintaining the list: In a doubly linked list, the user needs to handle the cases for both the next and previous node while inserting and deleting the node, it increases the complexity and there is a chance for error
Summary
So, here we saw every aspect of a doubly linked list in data structures. You might have got at least some idea regarding doubly linked lists and their applications. I know it's quite difficult and tricky to understand the whole topic in a single go. There are a lot of concepts and logic to be understood in this. Therefore, refer to it again and again till you get thorough with the linked list in data structures. To test your knowledge of linked lists, enroll in our Dsa Course Online.
FAQs
 Data Value
 The memory address of the next element.
 The memory Address of the previous element.