Splice

An LRU cache with capacity k, fed a stream of get and put operations one at a time. The row across the middle is the doubly linked list — HEAD and TAIL sentinels at the ends, the most recently used entry beside HEAD, the next one to be evicted beside TAIL. Under it sits the hash map, one bucket per key the stream ever mentions, and every occupied bucket draws a line up to the node it points at. The whole point of the piece is that those are two structures, not one: the map answers “where is key 3?” in O(1) and knows nothing about order; the list answers “what goes next?” in O(1) and cannot find anything. LC 146 is the exercise of keeping them in agreement.

Each operation plays out in phases rather than as a before/after cut, because the phases are what a whiteboard trace has to get right:

• lookup — the map bucket lights up (or doesn’t). On a miss for get that is the whole operation: return −1, touch nothing.
• unlink — the node lifts out of the row and the gap it leaves closes behind it: node.prev.next = node.next, node.next.prev = node.prev. Its own dashed pointers still hang down to the neighbours it just left, which is why the second of those two writes is possible at all — the node knows its predecessor. That one pointer is the entire argument for doubly linked.
• evict — the same unlink applied to TAIL.prev, plus map.delete, drawn in red. Forget the map deletion and nothing looks wrong until a later get hands back a node that is not in the list.
• insert — four writes after HEAD, the same four whether the list was empty or full. That is what the sentinels buy: no null checks, no special case for one element.

get is the operation to watch. It is a read, and it still goes through unlink and insert, because reading an entry is what makes it recent. The tape at the top records every operation’s outcome — green hit, amber miss, blue insert, red eviction — so a run’s shape is visible at a glance.

The streams

• LC 146 example is the statement’s own sequence at capacity 2, where get(1) promoting key 1 is exactly what dooms key 2 on the next put.
• Random, with locality draws most keys from a small hot set, so promotions are frequent and the hit counter climbs.
• Scan cycles k + 1 keys through a k-slot cache, reading each and writing it back. After the first lap every get misses and every put evicts: the key you are about to need is always the one that just left. That is the case against LRU, and the reason “when isn’t LRU the right policy?” is a follow-up worth pre-loading. The Belady piece in this catalog picks up from there.
• Custom takes p<key>:<val> and g<key> tokens in the text box.

Reuse

src/splice.js is a framework-free ES module with no canvas and no timers:

• LRUCache — the plain solution: Map + sentinel-terminated doubly linked list, get / put / order().
• simulate(ops, capacity) — one frame per operation, each with its phases: the list as it stands between pointer writes, the lifted node and its role (promote / evict / new), the map’s keys, and the assignments that phase performs, as strings.
• CLASSIC, CLASSIC_CAPACITY, randomOps, scanOps, parseOps, formatOps, rng(seed).

Same trace-per-tick shape as belady, collapse, rho, sift and window: the module produces frames, the demo draws them.

Gotchas

• A get on the entry already at HEAD.next still runs unlink and insert. The six writes put it back where it was; the demo says so in the caption rather than skipping the phase, because “it’s already at the front” is a micro-optimization, not a correctness fix, and treating it as one is how the special-casing creeps back in.
• The map buckets are keyed by the stream’s keys, not by a hash — the piece is about the map’s role, and drawing a real hash table would say nothing about LRU.
• The demo bundles its own copy of splice.js (self-contained by contract); re-copy after editing src/.