Data Structures & AlgorithmspythonIntermediate7 min read

How to Implement an O(1) LRU Cache Using a Doubly Linked List and Hash Map

Achieve strict O(1) get() and put() operations by combining a hash table with sentinel head/tail doubly linked nodes.

Direct Answer & Architectural Summary (TL;DR)

An O(1) Least Recently Used (LRU) cache pairs a hash map (mapping keys to node pointers for O(1) lookup) with a doubly linked list bounded by dummy head and tail sentinels (enabling O(1) node splice and insertion at the MRU front). On every get(key) or put(key, val), the accessed node is unlinked and moved immediately after head; when capacity is exceeded, head's opposite sentinel (tail.prev) is evicted in O(1).

Interactive Runnable CodeSandbox

Edit code live, run with custom stdin, or execute the assertion suite

python

LRUCache (Doubly Linked List + Dict)

main.py

Time: O(1) Space: O(C)

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key: int = 0, val: int = 0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: dict[int, Node] = {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

def _remove(self, node: Node) -> None:
        p, n = node.prev, node.next
        p.next, n.prev = n, p

def _insert_mru(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert_mru(node)
        return node.val

def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._insert_mru(node)
        if len(self.cache) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

# Benchmark execution
lru = LRUCache(2)
lru.put(1, 10)
lru.put(2, 20)
r1 = lru.get(1)       # returns 10, key 1 becomes MRU
lru.put(3, 30)        # evicts key 2
r2 = lru.get(2)       # returns -1 (evicted)
r3 = lru.get(3)       # returns 30
print([r1, r2, r3])

Custom Benchmark Input (stdin / args)

Included Verification Suite (3 Assertions)

Evicts Least Recently Used Key on Capacity Overflow

in: LRUCache(2): put(1,10), put(2,20), get(1), put(3,30), get(2) → [10, -1, 30]

Updating Existing Key Promotes to MRU Without Eviction

in: LRUCache(2): put(1,10), put(2,20), put(1,99), put(3,30), get(1) → 99

Capacity=1 Boundary Invariant

in: LRUCache(1): put(5,50), put(6,60), get(5), get(6) → [-1, 60]

Click Run Code or Verify Tests to execute this explainer in the sandbox.

Pointer Invariant & Amortized Operations

T_{\text{get}}(k) = O(1), \quad T_{\text{put}}(k, v) = O(1), \quad S(C) = \Theta(C)

Every cache access performs at most 6 pointer reassignments in the doubly linked list plus 1 hash table lookup.

Step-by-Step Implementation Breakdown

Eliminate Null-Pointer Branches with Dummy Sentinels

Initialize two permanent sentinel nodes (head and tail) connected to each other. Every real cache node lives strictly between head and tail, so _remove() and _insert_mru() never branch on None.

Store Key Inside Node for O(1) Reverse Eviction

When evicting tail.prev, we must also delete its entry from self.cache. Storing node.key on the doubly linked node avoids an O(N) scan of the dictionary.

Use slots in Python for 40% Lower Node Memory Overhead

Declaring __slots__ = ('key', 'val', 'prev', 'next') prevents CPython from allocating a per-instance __dict__ on every linked-list node.

Production Edge Cases & Interview Traps

Updating an existing key via put(k, new_val) must promote k to MRU and must NOT trigger an eviction of another key.
In multi-threaded environments, wrap _remove/_insert_mru with a shard lock (or use Segmented LRU to reduce lock contention).

Frequently Asked Questions

Why can't we use a singly linked list with a hash map for an O(1) LRU cache?

Deleting an arbitrary middle node from a singly linked list requires knowing its predecessor node, which takes O(N) traversal unless you maintain back-pointers (making it a doubly linked list).

How does Python's built-in collections.OrderedDict implement LRU?

OrderedDict is implemented in C using the exact same architecture: a dict hash table paired with a circular doubly linked list, exposing move_to_end(key, last=False) and popitem(last=True) in O(1).

How to Implement an O(1) LRU Cache Using a Doubly Linked List and Hash Map

Achieve strict O(1) get() and put() operations by combining a hash table with sentinel head/tail doubly linked nodes.

Direct Answer & Architectural Summary (TL;DR)

Interactive Runnable CodeSandbox

LRUCache (Doubly Linked List + Dict)

Pointer Invariant & Amortized Operations

Step-by-Step Implementation Breakdown

Eliminate Null-Pointer Branches with Dummy Sentinels

Store Key Inside Node for O(1) Reverse Eviction

Use __slots__ in Python for 40% Lower Node Memory Overhead

Production Edge Cases & Interview Traps

Frequently Asked Questions

Why can't we use a singly linked list with a hash map for an O(1) LRU cache?

How does Python's built-in collections.OrderedDict implement LRU?

Interactive Runnable CodeSandbox

LRUCache (Doubly Linked List + Dict)

Pointer Invariant & Amortized Operations

Step-by-Step Implementation Breakdown

Eliminate Null-Pointer Branches with Dummy Sentinels

Store Key Inside Node for O(1) Reverse Eviction

Use __slots__ in Python for 40% Lower Node Memory Overhead

Production Edge Cases & Interview Traps

Frequently Asked Questions

Why can't we use a singly linked list with a hash map for an O(1) LRU cache?

How does Python's built-in collections.OrderedDict implement LRU?

Use slots in Python for 40% Lower Node Memory Overhead

Use slots in Python for 40% Lower Node Memory Overhead