Doubly Linked List

data-structures

Definition

Doubly Linked List

A doubly linked list is a linear data structure consisting of a sequence of nodes, where each node contains:

• Value: The data stored in the node.
• Next: A pointer to the subsequent node.
• Prev: A pointer to the preceding node.

This bidirectional linkage allows for traversal in both forward and backward directions.

Visual Representation

Complexity

Compared to a singly linked list, the doubly linked list improves the complexity of deletions at the tail:

Operation	Complexity	Description
Access	$O(n)$	Linear traversal required.
Search	$O(n)$	Linear scan.
Insertion	$O(1)$	Constant time if the position is known.
Deletion	$O(1)$	Constant time if the node is known (no need to find predecessor).

Comparison

The primary advantages of a doubly linked list over a singly linked list include:

• Bidirectional Traversal: Can be traversed from both head to tail and tail to head.
• Efficient Deletion: A node can be removed in $O(1)$ time if its pointer is given, as the predecessor is directly accessible via the prev pointer.
• Reversed Iteration: Simplifies algorithms that require reverse processing.

The trade-off is an increased memory overhead due to the storage of an additional pointer per node.