Visual walkthrough — Applications — frequency counting, two-sum problem, caching (LRU)

Before line one, three words we will keep saying — pinned here so you never meet them undefined:

---

Step 1 — The problem, as a physical box

WHAT. A cache is a box with a fixed number of slots — its capacity, written $C$. Here $C=2$. WHY start here. Every design choice below exists to answer one hard question this box forces on us: when the box is full and a new key arrives, which old key do we throw away? PICTURE. Two slots. Two rules pinned to the side: find fast, and evict the least recently used.

The eviction rule is the whole difficulty. To obey "throw out the least recently used", the box must somehow remember the order in which keys were touched. Hold that thought — it is the crack that a plain hash map falls into.

---

Step 2 — Attempt #1: a hash map alone (and why it breaks)

WHAT. Try the simplest tool: a hash map key → value. Looking up any key is $O(1)$. WHY it's tempting. get and put both just poke the map — instant. (Parent Mistake C.) WHY it breaks. A hash map is a bag: it has no order. Ask it "which key was touched longest ago?" and it must scan every entry to find out — that is $O(n)$, not $O(1)$. The parent's own cost analysis dies right here.

$\underset{\text{find a key: }O(1)✓}{\underbrace{\text{map[key]}}}\text{vs}\underset{\text{scan all }n\text{ keys: }O(n)\times }{\underbrace{\text{find the least-recent key}}}$

• The left term is the good news: locating a named key is instant.
• The right term is the killer: the map cannot rank keys by recency, so it must inspect all $n$ of them.

Conclusion of Step 2: we need a second structure whose entire job is to keep keys ordered by recency.

---

Step 3 — Attempt #2: order the keys in a line

WHAT. Lay the keys out in a line ordered by recency: front = most recent, back = least recent. WHY a line. A line has the order the map lacked. Two things become trivial by position:

• The victim to evict is always the back element — no search needed.
• "Just touched key $k$" means: move $k$ to the front.

$\underset{\text{least recent}=\text{evict here}}{\underbrace{\text{back}}}\cdots \underset{\text{most recent}=\text{insert / touch here}}{\underbrace{\text{front}}}$

But which kind of line? An ordinary array line is a trap: deleting a middle element and sliding everything over is $O(n)$. That's the next question.

---

Step 4 — Why a doubly linked list, not a singly one

WHAT. Store the line as a doubly linked list — every node holds a prev pointer (to the node before it) and a next pointer (to the node after it). WHY doubly. To touch a key we must unlink its node from the middle and re-stitch its two neighbours together. To stitch, we need to reach both neighbours from the node itself. next alone (singly linked) reaches the node after; to reach the node before you'd have to scan from the head — $O(n)$. Storing prev too makes unlink pure pointer surgery, $O(1)$.

$\underset{\text{neighbour-before now skips node}}{\underbrace{\text{node.prev.next}}}=\underset{\text{...straight to neighbour-after}}{\underbrace{\text{node.next}}},\underset{\text{neighbour-after looks back}}{\underbrace{\text{node.next.prev}}}=\underset{\text{...past node, to before}}{\underbrace{\text{node.prev}}}$

Read it as a sentence: "my previous neighbour's next now points to my next neighbour, and my next neighbour's prev now points to my previous neighbour." The node is spliced out — no scan, four pointer writes, $O(1)$.

---

Step 5 — Sentinels: killing the edge cases before they bite

WHAT. Add two fake nodes that hold no real data: a head sentinel (guards the front) and a tail sentinel (guards the back). Real keys always live strictly between them. WHY. Without sentinels, inserting into an empty list or removing the only node means node.prev or node.next is null — the surgery in Step 4 crashes. With sentinels, every real node is guaranteed to have a real prev and a real next. Every quadrant of cases — empty, one element, full — uses the same four-line splice. No if node is null anywhere.

$\text{head}\underset{\text{always valid}}{\underbrace{⟷}}(\text{real nodes})\underset{\text{always valid}}{\underbrace{⟷}}\text{tail}$

• The front = head.next (most recent real node, or tail itself if empty).
• The victim = tail.prev (least recent real node, or head itself if empty — which we simply never evict from).

Now the map from Step 2 and the doubly linked list from Steps 3–5 team up: map[key] points straight at the node inside the list. Find in $O(1)$ (map), reorder/evict in $O(1)$ (list).

---

Step 6 — get(key): touch, then promote to front

WHAT. get(1): use the map to jump to node 1 in $O(1)$, then remove it and re-add it at the front, because touching it makes it the most recent. WHY. Reading a key is a use — LRU must count it. Failing to promote is the classic bug: the touched key would drift to the back and get wrongly evicted.

$\underset{O(1)\text{ jump via map}}{\underbrace{n=\text{map[key]}}}\to \underset{\text{Step 4 splice}}{\underbrace{\text{\_remove(n)}}}\to \underset{\text{re-stitch behind head}}{\underbrace{\text{\_add\_front(n)}}}$

Every arrow is $O(1)$, so get is $O(1)$. Edge case — key absent: key not in map → return $-1$ immediately, no list touched. (Nothing to promote, nothing crashes.)

---

Step 7 — put(key, value): insert, then evict if overflowing

WHAT. put(3, C) when the box is full: add 3 at the front, then check len(map) > C. If so, the victim is tail.prev (least recent) — unlink it and delete it from the map. WHY delete from both. The node and its map entry are two views of one key. Drop only the node and the map keeps a dangling pointer; drop only the map entry and the list keeps a ghost. Both, every time.

$\underset{\text{overflow test}}{\underbrace{\text{len(map)}>C}}\Rightarrow \underset{\text{least-recent, }O(1)}{\underbrace{\text{lru = tail.prev}}}\to \underset{\text{evict from list AND map}}{\underbrace{\text{\_remove(lru)};\text{del map[lru.k]}}}$

Edge case — key already present: first _remove its old node, then re-add the new value at front. Its recency refreshes; the map size does not grow, so no eviction. Degenerate case — $C=0$: every put overflows and immediately evicts what it just inserted; the box stays empty and correct. Sentinels keep even this from crashing (we only ever evict a real node, never the head).

Trace the parent's example ($C=2$), now watchable in the pictures above:

---

The one-picture summary

The whole machine in one frame: the map (left) gives an $O(1)$ jump to any node by key; the doubly linked list (right) keeps every key ordered by recency, so the front is "most recent" and the back is the always-ready eviction victim. Because the map lands you on the node, and the node carries prev/next, both get and put reduce to a fixed number of pointer writes — $O(1)$, forever.

Recall Feynman: tell it to a 12-year-old

Imagine a two-slot shelf of your favourite toys. You want two powers at once: grab any toy instantly by name, and always know which toy you've ignored the longest so you can donate it when a new toy arrives.

One tool isn't enough. A name-index (the hash map) finds a toy by name in a blink — but it has no idea which toy is stalest. A line of toys ordered by "last played" knows the stalest one (it's at the back) — but finding a named toy in the line means walking the whole line.

So we use both, glued together. The name-index doesn't store the toy — it stores a finger pointing right at the toy's spot in the line. Now: look up by name (blink), and because each toy in the line holds hands with the toy on its left and right, you can yank it out and move it to the front instantly — no walking. When the shelf overflows, the toy at the back is the one nobody's played with longest, so out it goes.

Two fake bookend toys (the sentinels) sit at each end so the real toys always have a neighbour to hold hands with — no toy is ever left grabbing at empty air. That's an LRU cache: a phone book taped to a hand-holding conga line.

Recall Quick self-check

Why can't a hash map alone be an LRU cache? ::: It has no order, so finding the least-recently-used key costs $O(n)$ — a scan of every entry. Why doubly, not singly, linked? ::: Unlinking a middle node needs its predecessor; prev gives it in $O(1)$, versus an $O(n)$ search in a singly list. Where is the eviction victim always found? ::: At tail.prev — the real node just before the tail sentinel = least recently used. What do the two sentinels buy us? ::: Every real node always has a valid prev and next, so insert/remove use one branch-free splice — even when empty or full. On get(key), what two list operations follow the lookup? ::: _remove(node) then _add_front(node) — promoting the touched key to most-recent.

Related tools worth linking: Collision Resolution (Chaining vs Open Addressing) (what keeps the map itself $O(1)$), Caching Strategies (LRU's cousins), and the Sliding Window pattern (another "remember as you pass" trick).