LRU Cache Visualizer — Free HTML CSS JS Snippet

Most "LRU cache" demos on the web fake the algorithm with an array and indexOf/splice, which is O(n) per operation and quietly teaches the wrong lesson about why real LRU caches are fast. This snippet implements the actual textbook data structure — a doubly linked list ordered by recency plus a hash map from key to list node — so every get and put genuinely runs in O(1), and the animation you see on screen is a direct visualization of real pointer surgery, not a reshuffled array pretending to be one.

Why a linked list instead of an array

An array-based "LRU" typically does arr.findIndex(k) (O(n) scan) followed by arr.splice() (O(n) shift) on every single access, which defeats the entire purpose of caching — a lookup that costs O(n) is barely better than not caching at all once the array grows. A doubly linked list solves this because moving a node to the front only requires rewriting four pointers (the moved node's neighbors' next/prev, and the moved node's own next/prev), regardless of how many items are in the list. Combined with a hash map that gives instant node lookup by key, both operations become genuinely O(1): this.map.get(key) finds the node instantly, and _remove/_insertFront relink it instantly, with no scanning of any kind.

The two sentinel nodes that remove every edge case

this.head and this.tail are permanent dummy nodes that are never evicted and never returned to the caller — head.next is always the current most-recently-used real node, and tail.prev is always the current least-recently-used real node. This sentinel-node pattern is the detail that most hand-rolled LRU implementations get wrong: without it, _remove() and _insertFront() need special-case branches for "the list is empty," "removing the only node," or "inserting into an empty list," because there is no real neighbor to relink against. With sentinels, this.head.next = this.tail on construction means _remove and _insertFront are four-line functions with zero conditionals — they always have a real .prev and .next object to write to, even in an empty cache.

get(key): unlink and re-insert, not "find and swap"

get(key) first checks this.map.has(key); a miss returns immediately with no list mutation at all. On a hit, the node is unlinked from its current position with _remove(node) and immediately relinked at the front with _insertFront(node) — the same node object, just re-pointed. On screen this plays out as the accessed box's left CSS value animating across to the leftmost (MRU) slot while every box that used to sit ahead of it shifts one slot to the right, all driven by transition: left 0.38s rather than a JavaScript animation loop, since a single property tween is all a slot reorder needs.

put(key, value): three distinct paths, three distinct animations

put() branches into exactly the three cases a real LRU cache has to handle. If the key already exists, its value is overwritten and the existing node is moved to the front exactly like a get hit — visualized identically, plus a brief green pulse to distinguish "value changed" from "just accessed." If the key is new and the cache has spare capacity, a fresh node is linked in at the front and its box animates in from a scaled-down, transparent state. If the key is new and the cache is already at capacity, the code reads this.tail.prev — the LRU node — evicts it with _remove plus a map.delete, and only then inserts the new node at the front; the evicted box animates out (a red fade-and-shrink) before the remaining boxes shift to make room, so eviction is never silent or instantaneous.

Why eviction is a pointer read, not a search

Because the list is kept sorted by recency at all times (every access moves its node to the front), the least-recently-used item is always sitting at this.tail.prev — no scan is ever needed to find "the oldest one." This is the second half of why the whole structure is O(1): insertion and lookup are fast because of the hash map, and eviction is fast because the linked list's own ordering invariant means the eviction candidate is always exactly one pointer dereference away.

Layout by index, not full FLIP, for a simpler correct animation

Rather than a general FLIP (First-Last-Invert-Play) animation library, this snippet keeps positioning simple and honest: layout() walks the linked list front-to-back after every mutation and sets each existing box's left to index * SLOT_WIDTH. Because the CSS transition is declared on left itself, the browser animates the change automatically — the JavaScript never computes a transform matrix or an intermediate frame, it just asks "where does each node belong now" and lets the browser's own compositor interpolate the movement.