DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on • Originally published at github.com

I built an LRU cache visualizer: watch recency reorder entries and evict the least-recently-used (LeetCode 146)

#algorithms #javascript #computerscience #datastructures

"Implement an LRU cache" (LeetCode #146) is one of the most-asked interview questions, and the part people fumble isn't the API — it's that recency of use, not insertion order, decides who gets evicted. So I built one you can watch: get and put keys and see entries slide around by recency, and the least-recently-used one drop off the end when the cache fills.

▶ Live demo: https://dev48v.github.io/lru-cache/
Source: https://github.com/dev48v/lru-cache

The rule, in one line

A fixed-capacity cache. Every get or put marks that entry most-recently-used and moves it to the front. When a put overflows the capacity, evict the entry at the back — the least-recently-used.

The demo lays entries out MRU on the left, LRU on the right, so you literally watch the eviction candidate drift toward the edge.

The classic gotcha

At capacity 4, do this:

put A, put B, put C, put D     // cache full: [D C B A]  (A is LRU)
get A                          // A used! → [A D C B]    (B is now LRU)
put E                          // overflow → evict B, not A → [E A D C]
get B                          // MISS — B is gone
Enter fullscreen mode Exit fullscreen mode

If you evicted by insertion order, you'd have thrown out A. LRU keeps A because it was just touched. That get(A) in the middle is the whole point of the data structure, and the reason a plain queue isn't enough — you need to be able to pull an item out of the middle and move it to the front.

Why it's O(1) — the two-structure trick

The naive version is O(n): to move an item to the front or find the least-recently-used, you scan. The real one combines two structures:

  • a hash map key → node, for O(1) lookup, and
  • a doubly-linked list ordered by recency, so you can move a node to the front and evict the tail in O(1) — just pointer swaps, no shifting.

get looks the node up in the map, unlinks it from wherever it is, and splices it to the front. put on overflow drops the tail node and deletes its key from the map. Both operations touch a constant number of pointers.

get(key):
  node = map[key]           // O(1)
  if !node: return MISS
  moveToFront(node)         // O(1) unlink + relink
  return node.value

put(key, value):
  if key in map: update + moveToFront
  else:
    node = addToFront(key, value); map[key] = node
    if size > capacity:
      lru = tail.prev; removeNode(lru); delete map[lru.key]   // O(1)
Enter fullscreen mode Exit fullscreen mode

A shortcut in JavaScript

JS Map iterates in insertion order, which you can exploit: treat the last-inserted entry as most-recently-used, and on access delete then set the key to move it to the end. map.keys().next().value gives you the oldest key to evict. It's not a linked list under the hood, but it gives the exact LRU behavior with almost no code — which is what the demo uses so the logic stays readable. In an interview, mention this trick and the linked-list version (they usually want the O(1) linked list).

Run the built-in sequence and watch get(B) miss after B is evicted, or drive it yourself. If it made LRU click, a star helps others find it: https://github.com/dev48v/lru-cache

Top comments (0)