Doubly Linked List: Bidirectional Navigation and Operations

Doubly Linked List

A doubly linked list extends the singly linked list by adding a prev pointer to each node, enabling traversal in both directions.

Node Structure

class Node:
    data: any
    prev: Node | null
    next: Node | null

Operations Comparison

Operation	Singly	Doubly
Insert at head	O(1)	O(1)
Insert at tail	O(n)*	O(1)
Delete given node	O(n)**	O(1)
Traverse forward	O(n)	O(n)
Traverse backward	N/A	O(n)

* O(1) with tail pointer ** O(n) because you need to find the previous node in a singly linked list

Deletion Advantage

The biggest advantage of a doubly linked list is O(1) deletion when you have a reference to the node:

// Singly: need to find prev by traversing
// Doubly: prev is right there
node.prev.next = node.next
node.next.prev = node.prev

Sentinel Nodes

Many implementations use sentinel (dummy) head and tail nodes to eliminate edge cases:

sentinel_head <-> node1 <-> node2 <-> sentinel_tail

With sentinels, you never need to check for null head or null tail. Every real node always has both a prev and next neighbor. This simplifies the code significantly.

LRU Cache Implementation

The most famous application of doubly linked lists is the Least Recently Used (LRU) cache:

1. A hash map provides O(1) lookup by key.
2. A doubly linked list maintains access order.
3. On access: move the node to the front (most recently used) in O(1).
4. On eviction: remove the node at the tail (least recently used) in O(1).

This combination gives O(1) for both get and put operations, which is why LRU caches are asked so frequently in interviews.

Memory Overhead

Each node stores two pointers instead of one. For small data values, the pointer overhead can be significant. For large data values, the overhead is negligible.