LRU Cache

Why One Data Structure Isn’t Enough

To build an LRU (Least Recently Used) Cache of capacity C (LeetCode 146), every get(key) and put(key, value) has to do three things in O(1) time:

1. Find whether key is already cached → requires a Hash Map (dict).
2. Promote a accessed or updated item to Most Recently Used (MRU) → requires splicing a node out of the middle of an sequence and appending it at the end in O(1) → requires a Doubly Linked List.
3. Evict the Least Recently Used (LRU) item when len == C → pop the node right after the LEFT boundary AND delete its key from the dictionary (which is why each Node must store node.key as well as node.value!).

The Hash Map stores direct memory references to the exact Node objects wired inside the Doubly Linked List.

Sentinel Boundary Nodes Make Pointer Surgery Effortless

Without sentinels, detaching the head or tail node requires four branches of if node.prev is not None bookkeeping. By wiring two permanent boundary nodes self.left ⇄ self.right on initialization, every real cache item always sits strictly between two non-null neighbors:

• Least Recently Used (evict next): self.left.next
• Most Recently Used (just touched): self.right.prev

Two tiny four-line helpers handle every get, put, update, and eviction:

from dataclasses import dataclass


@dataclass(eq=False)
class Node:
    key: str | None = None
    value: object = None
    prev: "Node | None" = None
    next: "Node | None" = None


class LRUCache:
    def __init__(self, capacity: int):
        if isinstance(capacity, bool) or not isinstance(capacity, int) or capacity < 0:
            raise ValueError("invalid cache capacity")
        self.capacity = capacity
        self.nodes: dict[str, Node] = {}
        self.left, self.right = Node(), Node()
        self.left.next = self.right
        self.right.prev = self.left

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

    def _append(self, node: Node) -> None:
        last = self.right.prev
        last.next = node
        node.prev = last
        node.next = self.right
        self.right.prev = node

    def get(self, key: str):
        node = self.nodes.get(key)
        if node is None:
            return None
        self._remove(node)
        self._append(node)
        return node.value

    def put(self, key: str, value: object) -> None:
        if self.capacity == 0:
            return
        if key in self.nodes:
            node = self.nodes[key]
            node.value = value
            self._remove(node)
            self._append(node)
            return
        if len(self.nodes) == self.capacity:
            oldest = self.left.next
            self._remove(oldest)
            del self.nodes[oldest.key]
        node = Node(key, value)
        self.nodes[key] = node
        self._append(node)

LRU vs FIFO vs LFU — and When LRU Misses Every Time

• FIFO (First-In, First-Out) evicts the earliest arrival even if users click that item every second. On our 8-request headphone comparison (P101, P202, P101, P303, P101, P202, P404, P101), FIFO evicts hot item P101 and suffers 5 database reads, whereas LRU keeps P101 warm and needs only 4.
• LFU (Least Frequently Used) tracks access counts, resisting one-off sequential scans that would flush an LRU cache — at the cost of extra frequency-bucket bookkeeping (LeetCode 460) and “frequency pollution” from formerly popular items.
• Cyclic Scan Thrashing: If a loop repeatedly scans C + 1 distinct items (P101 → P202 → P303 → P404 on a 3-slot cache), LRU evicts the exact item needed on the very next step — 0% hit rate! Increasing capacity by just 1 slot or switching policy resolves thrashing immediately.