dsa · coding · system-design

LRU Cache, Hash Map + Doubly Linked List

O(1) get/put cache with bounded capacity by combining a hash map (key → node) with a doubly linked list (recency). One of the most-asked LC mediums across Mag7.

medium2hgeneraljavapythonsystem-designtypescript
Ask GPTConfidence

Theory

Explanation

Intuition first, formal definition second. Skim the bullets if you already know this; read the prose if you don't.

You need two superpowers: find the node for a key in O(1), and re-order recency in O(1). A hash map gives the first; a doubly linked list gives the second. Wire them so the map points into the list and you can pop-and-push any node by reference, never scanning.

Maintain a doubly linked list with sentinel head/tail. Most-recently-used is next to head; least-recently-used is prev of tail. The hash map stores key → list node. On get(k): O(1) lookup, then unlink node and move to head. On put(k, v): if key exists, update + move to head; else insert at head, and if size > capacity evict the node prev of tail (also remove its key from map).

When to use

Fixed-capacity recency-based eviction. Web session caches, query result caches, page caches, CDN edge caches. Anywhere the access distribution is locality-biased.

When not to

Workloads with no temporal locality (random scan), LRU pessimal under one-shot scans. Frequency-skewed workloads (LFU better). Workloads where some entries must never evict (use pinning / SLRU).

Time: O(1) get + put (amortized) · Space: O(capacity)

head <-> [a]<-> [b] <-> [c] <-> tail
map: {a: &node_a, b: &node_b, c: &node_c}

get(b): unlink b, splice next to head
  head <-> [b] <-> [a] <-> [c] <-> tail

put(d) when full: evict prev-of-tail (=c), insert d at head
  head <-> [d] <-> [b] <-> [a] <-> tail

Key insights

  • Sentinel head/tail nodes remove all edge-case branching on empty/single-node lists.
  • Update the map when you evict, forgetting this is the #1 bug interviewers watch for.
  • Encapsulate moveToHead(node) and removeNode(node) helpers; the public methods compose them.
  • Doubly linked is required, singly linked makes unlink O(n) since you cannot find prev.
  • For thread-safety, a single mutex around the whole structure is correct but contended; production caches use sharded locks or lock-free variants.