Back to Study Material Data Structures and Algorithms

Doubly Linked List

A doubly linked list extends the singly linked list by giving each node two pointers: next, pointing to the following node, and prev, pointing to the prece...

Doubly Linked List

Bidirectional Traversal with Previous and Next Pointers

A doubly linked list extends the singly linked list by giving each node two pointers: next, pointing to the following node, and prev, pointing to the preceding node. The list maintains both a head pointer to the first node and typically a tail pointer to the last node. This bidirectional structure enables traversal in both directions and simplifies certain operations that are awkward in a singly linked list.

The key advantage over singly linked lists is the ability to delete a node given only a pointer to that node, without needing to find its predecessor first. In a singly linked list, deletion requires the predecessor so you can set predecessor.next to the node being deleted's next. In a doubly linked list, the node itself holds a prev pointer, so deletion is: node.prev.next equals node.next and node.next.prev equals node.prev, both O(1).

Insertion before a given node is also O(1) with a doubly linked list. Given a pointer to node X, insert a new node Y before X: set Y.next to X, Y.prev to X.prev, X.prev.next to Y, and X.prev to Y. Four pointer assignments and you are done.

Backwards traversal is another advantage. Starting from the tail and following prev pointers allows you to scan the list in reverse in O(n) without needing to reverse the list first. This is essential for implementing bidirectional iterators, such as those in C++'s std::list.

The cost of these advantages is memory: each node stores an extra pointer, adding eight bytes per node on 64-bit systems compared to a singly linked list. For very large lists with small data values, this overhead is significant.

The LRU (Least Recently Used) cache is a canonical application of doubly linked lists. An LRU cache stores the most recently accessed items and evicts the least recently used when capacity is reached. A doubly linked list combined with a hash map achieves O(1) for both get and put: the hash map provides O(1) access to any node, and the doubly linked list allows O(1) movement of a node to the front (most recently used) or removal from the back (least recently used).

Worked example: implement a browser history that supports navigating forward and backward. Each visited URL is a node in a doubly linked list. Clicking back follows prev; clicking forward follows next. Navigating to a new URL from a non-tail position truncates the forward history by nullifying the current node's next pointer.

Interview tip: when asked to implement an LRU cache, immediately describe the doubly linked list plus hash map combination. This is the canonical solution and demonstrates knowledge of how system-level data structures are designed.