Doubly Linked List

A Doubly Linked List enhances the standard Linked List by allowing bidirectional navigation. Each node points to both the next and the previous node, enabling efficient forward and backward traversal. This structure contrasts with Single Linked Lists, where movement is restricted to one direction, making it challenging to access previous elements without iterating from the start.

What is Doubly Linked List?

Doubly Linked List is a Data Structure, which is a variation of the Linked List, in which the transversal is easily possible in both directions, forward and backwards, as compared to the Singly Linked List, or simply called a Linked List.
You might be aware of the tabs on Windows/Mac. You can loop over all the opened applications and switch between them in both directions.
This can be thought of as all these applications being linked via a Doubly Linked List data structure, and you can switch to the applications on both sides of the current application.

So if a Linked List ⇒ A → B → C
Then a Doubly Linked List ⇒ A ⇆ B ⇆ C

Representation of Doubly Linked List in Data Structure

The Doubly Linked List has 3 parts: Value, Next pointer, and the Previous pointer.

The Previous pointer is the fundamental difference between the Doubly Linked List and the Linked List, which enables one to transverse back also in the Doubly Linked List.

As per the above illustration, following are the important points to be considered.

• Each Doubly Linked List Element contains pointers to next and Previous Elements and the data field.
• The First Element will have its Previous pointer as Null, to mark the start of the List.
• The Last Element will have its Next pointer as Null, to mark the end of the List.

The memory representation in a Doubly Linked List is not necessarily contiguous, as illustrated below:

In this diagram, -1 represents the NULL value, indicating the start or end of the list. For example, the first node (A) has its previous address as -1, and the last node (D) has its next address as -1, forming the structure -1 ← A ⇆ B ⇆ C ⇆ D → -1.

Insertion Operation In Doubly Linked List

Insertion at the Beginning

1. Start with the initial doubly linked list: A ⇆ B ⇆ C.
2. Insert X to become the first element: X ⇆ A ⇆ B ⇆ C.
3. Change X.previous to NULL and X.next to point to the original head (A).
4. Set A.previous to X to link A back to the new head.
5. Update Head to point to X, making X the new first element of the list.

Code

Insertion in Between Nodes

Insert After a Node

1. Start with the current doubly linked list: B ⇆ C ⇆ D ⇆ E.
2. To insert X after C, change the list to: B ⇆ C ⇆ X ⇆ D ⇆ E.
3. Adjust C.next to point to X.
4. Change D.prev to point to X.
5. Set X.prev to C and X.next to D, linking X correctly between C and D.

Code

Insert Before a Node

1. Starting point: B ⇆ C ⇆ D ⇆ E.
2. Goal: Insert X before C to get B ⇆ X ⇆ C ⇆ D ⇆ E.
3. Change C.prev (previously pointing to B) to point to X.
4. If C was the first node (no B), update Head to point to X.
5. Configure X's pointers: X.prev points to B, and X.next points to C.

Code

Insertion at the End

1. Initial state: A ⇆ B ⇆ C.
2. Insert X at the end: A ⇆ B ⇆ C ⇆ X.
3. Update C.next from Null to X.
4. Set X.prev to C and X.next to Null.

Code:

Deletion Operation In Doubly Linked List

Deletion at the Beginning

1. Start with the doubly linked list A ⇆ B ⇆ C.
2. Identify the node to delete, which is the head node A.
3. Update the head to point to A.next, making B the new head.
4. Adjust B.previous to point to Null, disconnecting A from the list.
5. The deletion of A is confirmed with the head now pointing to B, and B having no previous node.

Deletion of the Inner Node

1. Start with the doubly linked list A ⇆ B ⇆ C.
2. Identify the inner node to delete, for example, B.
3. Update A.next to point to C, skipping over B.
4. Change C.previous to point to A, disconnecting B from C.
5. By updating these pointers, B is effectively removed from the list, resulting in A ⇆ C.

Deletion at the End

1. Begin with a doubly linked list, for instance, A ⇆ B ⇆ C.
2. Identify the node at the end to delete, which is C.
3. Change B.next, which previously pointed to C, to Null, indicating the end of the list.
4. Since C is the last node, there's no C.next to update.
5. With B.next now pointing to Null, C is effectively removed from the list, leaving A ⇆ B as the updated list.

Code

Doubly Linked List Code Implementation

Doubly Linked List Complexity Analysis

For Insertion operations in a doubly linked list, the complexities are as follows:

• Time Complexity: O(1) or O(n)
• Auxiliary Space: O(1)

For Deletion operations in a doubly linked list, the complexities are as follows:

• Time Complexity: O(1)
• Auxiliary Space: O(1)

Advantages of Doubly Linked List Compared to Singly Linked List

• Doubly linked lists allow bidirectional traversal, making operations like reverse traversal more efficient.
• Deletion of a node in a doubly linked list is more efficient as it does not require traversal from the head to find the previous node.
• It's easier to insert or delete nodes from both ends of the list, as both head and tail pointers are maintained.
• Doubly linked lists facilitate the implementation of more complex data structures like linked lists with parent pointers, which are useful in hierarchical structures such as trees.
• They provide better flexibility for certain algorithms and operations, such as those needing to frequently access previous and next elements.

Disadvantages of Doubly Linked List Compared to Singly Linked List

• Doubly linked lists consume more memory per node as they require an extra pointer to store the address of the previous node.
• Operations like insertion and deletion involve updating more pointers, increasing the complexity and potential for errors.
• The extra pointer in each node can lead to higher overhead in terms of memory management and allocation, especially in systems with limited memory resources.
• Traversing and modifying a doubly linked list can be slightly slower due to the additional pointer operations involved.
• The increased complexity in managing two pointers per node can make the code more complex and harder to understand, especially for beginners.

Applications of Doubly Linked List

• Navigation systems that require forward and backward traversal, such as web browser history or a music playlist.
• Implementing complex data structures like linked lists, stacks, queues, and their variations.
• Creating a base for advanced data structures like Fibonacci heaps, or for algorithms requiring quick insertion and deletion from both ends, like the LRU cache.
• Facilitating undo functionality in applications by allowing backward traversal to previous states.
• Managing windows in software applications where users can easily switch between currently open windows or tabs.

See Also:

1. Doubly Linked List in C
2. Doubly Linked List in C++