# Doubly Linked List Algorithm in Data Structures with Examples

06 Jun 2024
Beginner
14.4K Views
Learn via Video Course & by Doing Hands-on Labs

## 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 problem-solving 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:

1. a pointer *prev: address of the previous node
2. data: data item
3. a pointer *next: address of next node

### Representation of a Doubly Linked List in Data Structures

In the given figure,

We can see a doubly linked list that consists of nodes, where each node contains a
`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 to`NULL`to mark the start of the list. The `next` pointer of the last or the `tail` node points to`NULL`to mark the end of the list. It is also known as a two-way 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 Doubly-Linked 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
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

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 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;

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* 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;

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 pointer `next` stores the address of `two`, and `prev` stores `NULL`.
• For node `two`, the pointer `next` stores the address of `three`, and `prev` stores the address of `one`.
• For node `three`, `next` stores `NULL`, and `prev` stores the address of `two`.
• Here `one` is the `head` node and so its `prev` pointer points to `NULL` and three is a `tail` node so its `next` pointer points to `NULL`.

#### Output

``````1 2 3
``````

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

1. Data `Value`
2. The memory address of the next element.
3. The memory Address of the previous element.

• In the above image, `-1` represents `NULL`.
• Here `1060`, `1061`, `1062`, etc represent the addresses in the memory, and we traverse the Doubly Linked List until we find -1 in the `Next` of the Node. This memory representation shows that the `Values` need not be stored contiguously.
• You can see that the element `A` has `Prev` = -1 i.e. `NULL`, therefore it is the first Node in the Doubly Linked List.
• `A’s` `Next` points to memory address `1062`, where `B` is stored hence, `B` is to the next of `A`.
• Similarly, `B’s` `Next` has a memory address of `1069` where `C` is stored.
• Similarly, `D` has its `Next` as `-1`, 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:
1. Insertion at the beginning: Here, we insert the newly created node before the `head` node, and the `head` 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:

1. Create a new node
• allocate memory for new Node
• assign the `data` to the new Node.

2. Set `prev` and `next` pointers of the new node
• point `next` of new Node to the `first` node of the doubly linked list
• point `prev` to `NULL`

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

The above-given steps are implemented in the below program

#### 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

def __init__(self):

# 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

# Point prev to None
new_node.prev = None

# Point previous of the first node (now the first node is the second node) to newNode

# Function to print the elements of the doubly linked list
def print_list(self):
while current:
print(current.data, end=" ")
current = current.next
print()

# Creating a sample doubly linked list with nodes 1, 2, 3
second = Node(2)
third = Node(3)

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;
}
}

// 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

// Point prev to null
newNode.prev = null;

// Point previous of the first node (now the first node is the second node) to newNode

}

// Function to print the elements of the doubly linked list
void printList() {
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
Node second = new Node(2);
Node third = new Node(3);

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

// Point prev to NULL
newNode->prev = nullptr;

// Point previous of the first node (now the first node is the second node) to newNode

}

// Function to print the elements of the doubly linked list
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
``````
2. 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 the `next` pointer of `Node X`.
• Change the `prev` pointer of the node following the `Node X` to the new Node.
• Change the `next` pointer of `Node X` to the new Node.
• Change the `prev` pointer of the new Node to `Node X`.

Let us understand this with an illustration. Suppose we want to insert a node with value `6` after the second node with value `2` in the given doubly linked list. The following three steps to accomplish this operation:

1. Create a new node
• allocate memory for new Node.
• assign the `data` to new Node.

2. Set the `next` pointer of the new node and the previous node.
• assign the value of `next` from the previous node to the `next` of new Node.
• assign the address of the new Node to the `next` of the previous node.

3. Set the `prev` pointer of `new` node and the `next` node.
• assign the value of `prev` of next node to the `prev` of new Node.
• assign the address of the new Node to the `prev` of next node

The final doubly linked list after this insertion is:

#### 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

def __init__(self):

# 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):
while current is not None:
print(current.data, end=" ")
current = current.next
print()

# Creating a sample doubly linked list

second = Node(2)
third = Node(3)

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;
}
}

}

// 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() {
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

Node second = new Node(2);
Node third = new Node(3);

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) {}
};

public:

// 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() {
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};

int main() {
// Creating a sample doubly linked list

Node* second = new Node(2);
Node* third = new Node(3);

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   ``````
3. Insertion at the end: Here, we insert the newly created node at the end of the list or after the `tail` node, and the `tail` 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:

1. Create a new node
2. Set `prev` and `next` pointers of the new node and the previous node If the linked list is empty, make the new Node as the `head` node. Otherwise, traverse to the end of the doubly linked list.

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

def __init__(self):

# 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)

# If the linked list is empty, make the new_node as the head node
new_node.prev = None
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):
while current is not None:
print(current.data, end=" ")
current = current.next
print()

# Creating a sample doubly linked list with values 1, 2, 3
second = Node(2)
third = Node(3)

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;
}
}

// 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)

// If the linked list is empty, make the newNode as the head node
newNode.prev = null;
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() {
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
Node second = new Node(2);
Node third = new Node(3);

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)

// If the linked list is empty, make the newNode as the head node
newNode->prev = nullptr;
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
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:
1. Deletion at the beginning: Here, we will move the `head` to the `next` node to delete the node at the beginning and make the previous pointer of the current `head` point to `NULL`.

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:

1. Reset value node after the `del_node` (i.e. node two)
2. free the memory of `del_node`. And, the linked list will look like this:

The above-given steps are implemented in the below program

#### 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

def __init__(self):

# Function to delete a node from the doubly linked list
def delete_node(self, del_node):

# 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):
while current is not None:
print(current.data, end=" ")
current = current.next
print()

# Creating a sample doubly linked list with values 1, 2, 3
second = Node(2)
third = Node(3)

second.next = third
third.prev = second

print("Original list:", end=" ")
my_list.print_list()

# Deleting the head node (with data 1) from the list

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;
}
}

// Function to delete a node from the doubly linked list
void deleteNode(Node delNode) {

// 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() {
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
Node second = new Node(2);
Node third = new Node(3);

second.next = third;
third.prev = second;

System.out.print("Original list: ");
myList.printList();

// Deleting the head node (with data 1) from the list

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) {

// 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
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   ``````
2. 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` be `Node X` and the next node be `Node Y`. The steps to be followed are:
• Change the `next` pointer of `Node X` to `Node Y`.
• Change the `prev` pointer of `Node Y` to `Node X`.

Let us understand this with an illustration. Suppose we want to delete the `second node` with value `2` after the `first node` with value `1` in the given doubly linked list. The following three steps to accomplish this operation:

1. For the node before the `del_node` (i.e. first node)
• Assign the value of the `next` of `del_node` to the `next` of the first node.
2. For the node after the `del_node` (i.e. third node)
• Assign the value of `prev` of `del_node` to the `prev` of the third node.

3. Finally, we will free the memory of `del_node`. And, the final doubly linked list looks like this.

The above-given steps are implemented in the below program

#### 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

def __init__(self):

# 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):
while current is not None:
print(current.data, end=" ")
current = current.next
print()

# Creating a sample doubly linked list

second = Node(2)
third = Node(3)

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;
}
}

}

// 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() {
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

Node second = new Node(2);
Node third = new Node(3);

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) {}
};

public:

// 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() {
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};

int main() {
// Creating a sample doubly linked list

Node* second = new Node(2);
Node* third = new Node(3);

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
``````
3. Deletion at the end: Here we will move the `tail` to the previous node to delete the node at the end and make the `next` pointer of the `tail` node point to `NULL`.

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.

1. delete the `del_node` and make the `next` of node before `del_node` point to `NULL`.

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

def __init__(self):

# Function to delete the last node from the doubly linked list
def delete_last_node(self):
# Check if the linked list is empty
print("List is empty. Cannot delete last node.")
return

# Traverse to the last node
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):
while current is not None:
print(current.data, end=" ")
current = current.next
print()

# Creating a sample doubly linked list with values 1, 2, 3
second = Node(2)
third = Node(3)

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;
}
}

// Function to delete the last node from the doubly linked list
void deleteLastNode() {
// Check if the linked list is empty
System.out.println("List is empty. Cannot delete last node.");
return;
}

// Traverse to the last node
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() {
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
Node second = new Node(2);
Node third = new Node(3);

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
// Check if the linked list is empty
std::cout << "List is empty. Cannot delete last node." << std::endl;
return;
}

// Traverse to the last node
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
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  ``````

### 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

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

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;
}
}

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;

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) {}
};

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;

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

def __init__(self):

def search_node(self, value):
i = 1
# Node current will point to head

# Checks whether the list is empty
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

# 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;
}
}

void searchNode(int value) {
int i = 1;
// Node current will point to head

// Checks whether the list is empty
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

// 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) {}
};

public:

void searchNode(int value) {
int i = 1;
// Node current will point to head

// Checks whether the list is empty
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

// 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 ```O(1) ``` ```O(1) ``` Insertion at a specific position ```O(n) ``` ```O(1) ``` Insertion at the end ```O(1) ``` ```O(1) ``` Deletion at the beginning ```O(1) ``` ```O(1) ``` Deletion at a specific position ```O(n) ``` ```O(1) ``` Deletion at the end ```O(1) ``` ```O(1) ``` Traversal ```O(n) ``` ```O(1) ``` Search `O(n) ` `O(1)`

 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 node-link 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 doubly-linked list. It is more efficient.

## Applications of Doubly Linked List

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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

1. 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.
2. 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.
3. 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.
4. Memory efficiency: The doubly linked list can be used to manage memory efficiently, as nodes can be easily added or removed as needed.
5. Implementing other data structures:It can be used to implement different tree data structures.

1. Memory usage: Doubly linked lists require more memory than singly-linked lists, as they need to store a pointer to the previous node in addition to the next node.
2. Slower access and search times: Access and search operations have `O(n)` time complexity, where `n` 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.
3. 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.
4. 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.
5. Not suitable for some algorithms: Some algorithms may require random access to elements in a list, which is not efficient with doubly linked lists.
6. 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

### Q1. How many pointers does a Doubly Linked List have?

A Doubly Linked List has two pointers: prev to the previous node, and next to the next.

### Q2. How a Doubly Linked List is represented in memory?

A Doubly Linked List is represented using the linear Arrays in memory where each memory address stores three components:
1. Data Value
2. The memory address of the next element.
3. The memory Address of the previous element.

### Q3. Where are doubly linked lists used?

We can use a doubly linked list to execute heaps, stacks, binary trees, etc.
Share Article

### Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 Generative AI For Software Developers Jul 20 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Jul 20 SAT, SUN Filling Fast 06:00PM to 08:00PM (IST) Azure Master Class Jul 20 SAT, SUN Filling Fast 03:00PM to 05:00PM (IST) ASP.NET Core Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Software Architecture and Design Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) .NET Solution Architect Certification Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) Azure Developer Certification Training Jul 28 SAT, SUN Filling Fast 10:00AM to 12:00PM (IST) Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Data Structures and Algorithms Training with C# Jul 28 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Aug 11 SAT, SUN Filling Fast 09:30AM to 11:30AM (IST) ASP.NET Core Project Aug 24 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST)

Can't find convenient schedule? Let us know

Similar Articles