Doubly Linked List Tutorial

A doubly linked list is a more complex data structure than a singly linked list, but it offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer to the previous node and a pointer to the next node. This allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions.

What is a Doubly Linked List?

A doubly linked list is a data structure that consists of a set of nodes, each of which contains a value and two pointers , one pointing to the previous node in the list and one pointing to the next node in the list. This allows for efficient traversal of the list in both directions , making it suitable for applications where frequent insertions and deletions are required.

Insertion-at-the-End-in-Doubly-Linked-List-copy

Doubly Linked List

Representation of Doubly Linked List in Data Structure

In a data structure, a doubly linked list is represented using nodes that have three fields:

Data
A pointer to the next node ( next )
A pointer to the previous node ( prev )

Node-Structure-of-Doubly-Linked-List

Node Structure of Doubly Linked List

Node Definition

Here is how a node in a Doubly Linked List is typically represented:

                                   Java

                        Python

                                 JavaScript

Each node in a Doubly Linked List contains the data it holds, a pointer to the next node in the list, and a pointer to the previous node in the list. By linking these nodes together through the next and prev pointers, we can traverse the list in both directions (forward and backward), which is a key feature of a Doubly Linked List.

Operations on Doubly Linked List

Traversal in Doubly Linked List
Searching in Doubly Linked List
Finding Length of Doubly Linked List

Insertion in Doubly Linked List :

Insertion at the beginning of Doubly Linked List
Insertion at the end of the Doubly Linked List
Insertion at a specific position in Doubly Linked List

Deletion of a node at the beginning of Doubly Linked List
Deletion of a node at the end of Doubly Linked List
Deletion of a node at a specific position in Doubly Linked List

Let’s go through each of the operations mentioned above, one by one.

Traversal in Doubly Linked List

To Traverse the doubly list, we can use the following steps:

a. Forward Traversal:

Initialize a pointer to the head of the linked list.

While the pointer is not null:

Visit the data at the current node.
Move the pointer to the next node.

b. Backward Traversal:

Initialize a pointer to the tail of the linked list.

While the pointer is not null:

Visit the data at the current node.
Move the pointer to the previous node.

Below are the implementation of the above approach:

                                                                                                                                                 Java

                                                                                                                                        Python

                                                                                                                                       JavaScript

Output

Forward Traversal: 1 2 3 Backward Traversal: 3 2 1

Finding Length of Doubly Linked List

To find the length of doubly list, we can use the following steps:

Start at the head of the list.
Traverse through the list, counting each node visited.
Return the total count of nodes as the length of the list.

Below are the implementation of the above approach:

                                                                                                    Java

                                                                                           Python

                                                                                                              JavaScript

Output

Length of the doubly linked list: 3

Insertion at the Beginning in Doubly Linked List

Insertion-at-the-Beginning-in-Doubly-Linked-List

Insertion at the Beginning in Doubly Linked List

To insert a new node at the beginning of the doubly list, we can use the following steps:

Create a new node, say new_node with the given data and set its previous pointer to null, new_node->prev =NULL .
Set the next pointer of new_node to current head, new_node->next = head.
If the linked list is not empty, update the previous pointer of the current head to new_node, head->prev = new_node .
Return new_node as the head of the updated linked list.

Below are the implementation of the above approach:

                                                                                        hardcoded linked list:                                               C

                                                                                                                               Java

                                                                                                                    Python

C#

                                                                                                                                      JavaScript

Output

Original Linked List: 2 3 4 After inserting Node 1 at the front: 1 2 3 4

Insertion at the End of Doubly Linked List

Insertion-at-the-End-in-Doubly-Linked-List

Insertion at the End in the Doubly Linked List

To insert a new node at the end of the doubly linked list, we can use the following steps:

Allocate memory for a new node and assign the provided value to its data field.
Initialize the next pointer of the new node to nullptr.

If the list is empty:

Set the previous pointer of the new node to nullptr.
Update the head pointer to point to the new node.

Traverse the list starting from the head to reach the last node.
Set the next pointer of the last node to point to the new node.
Set the previous pointer of the new node to point to the last node.

Below are the implementation of the above approach:

                                     <span If the linked list is empty, set the new                                                                                                           C

                                               <span If the linked list is empty, set the                                                                                              Java

                   <span If the linked list is empty, set the new node as                                                                                                            Python

      span If the linked list is empty, set the new node         C#

                                                 <span If the linked list is empty, set the                                                                                                              JavaScript

Output

Original Linked List: 1 2 3 Inserting Node with data 4 at the end: 1 2 3 4

Insertion at a Specific Position in Doubly Linked List

To insert a node at a specific Position in doubly linked list, we can use the following steps:

Insertion-at-a-Specific-Position-in-Doubly-Linked-List

Insertion at a Specific Position in Doubly Linked List

To insert a new node at a specific position,

If position = 1, create a new node and make it the head of the linked list and return it.
Otherwise, traverse the list to reach the node at position – 1, say curr .
If the position is valid, create a new node with given data, say new_node .
Update the next pointer of new node to the next of current node and prev pointer of new node to current node, new_node->next = curr->next and new_node->prev = curr.
Similarly, update next pointer of current node to the new node, curr->next = new_node .
If the new node is not the last node, update prev pointer of new node’s next to the new node, new_node->next->prev = new_node.

Below is the implementation of the above approach:

                                              <span If the linked list is not empty, set the prev                                          <span If the position is out of bounds                            <span If the new node is not the last node, update prev                                                                                     C

                                                                        <span If the linked list is not empty, set the                                                  <span If the position is out of bounds                               <span If the new node is not the last node, update                                                                                                             Java

                           <span If the linked list is not empty, set                                               <span If the position is out of bounds                      <span If the new node is not the last node, update                                                                                          Python

    span If the linked list is not empty, set the     span If the position is out of bounds    span If the new node is not the last node, update       C#

                                                                                                 <span If the position is out of bounds                      <span If the new node is not the last node, update                                                                            JavaScript

Output

Original Linked List: 1 2 4 Inserting Node with data 3 at position 3: 1 2 3 4

Deletion at the Beginning of Doubly Linked List

Deletion-at-the-Beginning-of-Doubly-Linked-List

Deletion at the Beginning of Doubly Linked List

To delete a node at the beginning in doubly linked list, we can use the following steps:

Check if the list is empty, there is nothing to delete. Return.
Store the head pointer in a variable, say temp .
Update the head of linked list to the node next to the current head, head = head->next .
If the new head is not NULL, update the previous pointer of new head to NULL, head->prev = NULL .

Below is the implementation of the above approach:

                                                                                                                           Java

                                                                                                      Python

C#

                                                                                                                          JavaScript

Output

Original Linked List: 1 2 3 After Deletion at the beginning: 2 3

Deletion at the End of Doubly Linked List

Deletion-at-the-End-in-Doubly-Linked-List

Deletion at the End in Doubly Linked List

To delete a node at the end in doubly linked list, we can use the following steps:

Check if the doubly linked list is empty. If it is empty, then there is nothing to delete.
If the list is not empty, then move to the last node of the doubly linked list, say curr .
Update the second-to-last node’s next pointer to NULL, curr->prev->next = NULL .
Free the memory allocated for the node that was deleted.

Below is the implementation of the above approach:

                                                                                                                                     Java

                                                                                                                      Python

C#

                                                                                                                                             JavaScript

Output

Original Linked List: 1 2 3 After Deletion at the end: 1 2

Deletion at a Specific Position in Doubly Linked List

Deletion-at-a-Specific-Position-in-Doubly-Linked-List

Deletion at a Specific Position in Doubly Linked List

To delete a node at a specific position in doubly linked list, we can use the following steps:

Traverse to the node at the specified position, say curr .

If the position is valid, adjust the pointers to skip the node to be deleted.

If curr is not the head of the linked list, update the next pointer of the node before curr to point to the node after curr, curr->prev->next = curr-next .
If curr is not the last node of the linked list, update the previous pointer of the node after curr to the node before curr, curr->next->prev = curr->prev .

Below is the implementation of the above approach:

                                    <span If the list is empty                             <span If the position is out of range                                 <span If the node to be deleted is the head node                                                                                                      C

                                                           <span If the list is empty                                <span If the position is out of range                                   <span If the node to be deleted is the head node                                                                                               Java

 specific position in Doubly Linked List           <span If the list is empty                                <span If the position is out of range                             <span If the node to be deleted is the head node                                                                           Python

     span If the list is empty  span If the position is out of range   span If the node to be deleted is the head node     C#

                                        <span If the list is empty                              <span If the position is out of range                       <span If the node to be deleted is the head node                                                                        JavaScript

Output

Original Linked List: 1 2 3 After Deletion at the position 2: 1 3

Advantages of Doubly Linked List

Efficient traversal in both directions: Doubly linked lists allow for efficient traversal of the list in both directions, making it suitable for applications where frequent insertions and deletions are required.
Easy insertion and deletion of nodes: The presence of pointers to both the previous and next nodes makes it easy to insert or delete nodes from the list, without having to traverse the entire list.
Can be used to implement a stack or queue: Doubly linked lists can be used to implement both stacks and queues, which are common data structures used in programming.

Disadvantages of Doubly Linked List

More complex than singly linked lists: Doubly linked lists are more complex than singly linked lists, as they require additional pointers for each node.
More memory overhead: Doubly linked lists require more memory overhead than singly linked lists, as each node stores two pointers instead of one.

Applications of Doubly Linked List

Implementation of undo and redo functionality in text editors.
Cache implementation where quick insertion and deletion of elements are required.
Browser history management to navigate back and forth between visited pages.
Music player applications to manage playlists and navigate through songs efficiently.
Implementing data structures like Deque (double-ended queue) for efficient insertion and deletion at both ends.