Why does an LRU cache need both a hash map and a doubly-linked list?

Each structure solves half the problem. The hash map gives O(1) lookup from a key to its node, so get/put never scan. The doubly-linked list maintains recency order — most-recently-used at the head, least-recently-used at the tail — and lets you unlink and re-insert any node in O(1) because each node knows its prev and next. Neither structure alone is enough: a hash map has no order, and a list alone needs O(n) to find a key.

How is an LRU cache O(1) for get and put?

get(key) hashes the key to find the node in O(1), then splices that node out of the list and re-inserts it at the head — also O(1) because the node carries prev/next pointers, so no traversal is needed. put(key) is the same lookup plus, on a miss at capacity, removing the tail node (the LRU) and deleting its key from the map, both O(1). No operation ever loops over the entries.

LRU vs LFU vs FIFO — what's the difference?

All three are cache eviction policies. FIFO evicts the oldest inserted item regardless of use. LRU evicts the item used least recently — recency of access, not insertion. LFU evicts the item used least frequently — it counts how often each key is touched, which needs an extra frequency map and is harder to keep O(1). LRU is the common default because it is cheap and matches real access patterns where recently-used data is likely to be used again.

How do you solve LeetCode 146 (LRU Cache)?

Back a hash map (key → node) with a doubly-linked list ordered MRU to LRU. Use dummy head and tail sentinel nodes to avoid null checks. get(key): if absent return -1; else move the node to the front and return its value. put(key, value): if the key exists, update the value and move to front; otherwise insert at front, and if size exceeds capacity, remove the tail node and delete its key from the map. Every operation is O(1).

The LRU Cache — Beyond Code & Karma

Chapter 01 — The Foundation

A cache must forget.
The only question is — what?

A cache stores a limited number of items so repeat lookups are fast. When it fills up it must drop something to make room — and the eviction policy decides what. An LRU cache evicts the item accessed least recently, betting that data you touched recently is data you'll touch again soon. Both get and put count as "using" a key, so each operation also refreshes that key's recency.

The Secret: the hard part of LeetCode 146 isn't the eviction rule — it's doing every operation in O(1). No scanning to find a key, no shifting to reorder. That demands two structures working as one.

The Cache

A fixed-capacity store of key→value pairs. Fast to read, but bounded — once full, every insert forces an eviction.

Recency

The ordering that matters. Every get and put marks a key as most-recently-used; the untouched drift toward the exit.

Hash Map

key → node, in O(1). This is what kills the linear scan — you jump straight to any node without walking anything.

Doubly-Linked List

The same nodes in recency order, MRU at the head, LRU at the tail. prev/next pointers let you relink any node in O(1).

The Cosmic Connection

Anitya — the cache as a study in impermanence

Hindu Philosophy Parallel

In Vedic thought, anitya — impermanence — is the nature of all things: what arises must pass. The mind keeps smriti (living memory) of what attention lately touched, and lets the long-untouched slip into vismriti (forgetting). A cache is exactly this discipline, made mechanical.

Smriti — the MRU head

Every access moves a key to the head — the living present, freshly remembered.

Vismriti — the LRU tail

Untouched keys drift to the tail — fading memory, the next to be released.

Samhara — eviction

Shiva's dissolution. The tail node is not deleted in anger — it is released so the present can be held.

"Hold the present lightly, hold nothing forever — and the structure stays clear, and O(1)."

Chapter 02 — Show Me The Code

Two ways to be O(1)

There's a slick JavaScript shortcut and there's the structure interviewers actually want to see. Know both.

The slick way — a Map remembers order

JavaScript's Map already iterates in insertion order. Delete-then-set moves a key to the "newest" end, and map.keys().next().value is always the oldest. That's a full LRU cache in ~15 lines:

lru-map.js

// The elegant JS trick: a Map already remembers insertion order.
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();   // key → value, O(1) lookup
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key);    // unlink…
    this.map.set(key, v);    // …re-insert → now most-recently-used
    return v;
  }

  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.cap)
      this.map.delete(this.map.keys().next().value); // evict LRU (oldest)
    this.map.set(key, value);
  }
}

Why it works: re-inserting a key makes it the most recent in iteration order; the first key returned by keys() is therefore the least-recently-used. Elegant — but it hides the machinery an interviewer wants you to explain.

The interview way — map + doubly-linked list

Under the hood, that Map trick is a hash map over a linked list. Build it explicitly and the O(1) story becomes visible — this is what the visualizer below animates:

lru-dll.js

// The interview-canonical structure: hash map + doubly-linked list.
class Node {
  constructor(key, val) {
    this.key = key; this.val = val;
    this.prev = this.next = null;
  }
}

// Two sentinel nodes remove every null-pointer edge case.
// head ⇄ [MRU] ⇄ … ⇄ [LRU] ⇄ tail

moveToFront(node) {   // O(1): just rewire 4 pointers
  remove(node);          // node.prev.next = node.next; …
  addAfterHead(node);    // splice back at the head
}

The four moves — every op is one of these

get — hit

Map finds the node in O(1). Splice it out of the list and re-insert at the head. Return its value. It's now the MRU.

get / put — miss

Key not in the map. get returns -1; put falls through to insertion. No list walk either way.

put — existing key

Update the node's value, then move it to the head. Same O(1) splice as a get-hit.

put — new key at capacity

Remove the tail node (the LRU), delete its key from the map, then insert the new node at the head. Two O(1) edits, no scan.

Chapter 03 — Live Visualization

Watch a key get evicted

A capacity-3 cache, auto-playing. Watch the doubly-linked list reorder on each access and the tail node dissolve when a new key arrives at capacity.

LRU Cache · capacity 3

⏸ Ready

Press Run to start…

Chapter 04 — Deep Dive

The nuances that senior devs know

This is where the 10,000 basic videos stop. Here's what actually matters at scale.

🐢 Why a plain array is O(n)

It's tempting to keep a single array ordered by recency. But "move this key to the front" then costs O(n): you must find the key (linear scan, unless you also keep a map) and then shift every element after it to fill the gap. Eviction from the end is cheap, but the move-to-front on every access dominates. The doubly-linked list removes both costs — the map finds the node, and the prev/next pointers relink it with no shifting.

⚖️ LRU vs LFU vs FIFO — pick your bet

All three are eviction policies that differ only in what they sacrifice:

Policy	Evicts	Cost
FIFO	Oldest inserted, ignoring use	Cheapest; ignores access patterns
LRU	Least recently accessed	O(1) with map + list; great default
LFU	Least frequently accessed	Needs a frequency map + buckets to stay O(1)

Rule of thumb: LRU wins when recent access predicts future access — which is most real workloads. LFU wins for skewed, stable popularity (a few keys hammered forever), at the cost of more machinery.

🛡️ Sentinel nodes — why dummy head & tail

Without sentinels, every splice has to special-case "is this the head?" and "is this the tail?" — a swamp of null checks where bugs breed. Two permanent dummy nodes (head and tail) that never hold data mean every real node always has a non-null prev and next. Insertion and removal become four unconditional pointer writes.

Pro tip: initialise with head.next = tail and tail.prev = head. Now "move to front" is always addAfter(head, node) and "evict LRU" is always remove(tail.prev) — no branches.

🧵 Is it thread-safe? (Spoiler: no)

The textbook LRU is single-threaded. Under concurrent access, two threads reordering the list at once will corrupt the pointers. In production you either guard the whole structure with a lock (simple, but the lock becomes the bottleneck) or reach for a sharded / lock-striped design, or a library like Caffeine (Java) that approximates LRU with lock-free ring buffers and a background eviction thread.

🌍 Where LRU actually runs

It's everywhere a fast store has a hard size limit:

System	What it caches
CPU / page cache	Hardware & OS approximate LRU to choose which cache lines or memory pages to evict.
Browser cache	Recently visited resources stay; stale ones drop first.
DB buffer pool	MySQL/InnoDB keep hot pages in memory using LRU-style lists.
Memoization	Python's `functools.lru_cache` caps memory by evicting least-recently-used results.

Chapter 05 — Dharma & The Cache

The Karma of eviction

The Karma Connection

Karma is the principle that every action has a consequence, deferred to the right time. In an LRU cache, the action is attention — every get and put is a touch that earns a key its place at the head.

karma.js

// Every access is an act of attention…
cache.get('mantra');   // touched → moves to MRU, the living present

// …and what attention forgets, the cache releases.
cache.put('new', value); // at capacity → the least-touched key dissolves

What you attend to is preserved; what you neglect drifts to the tail and is, in time, released. The cache holds no grudge and plays no favourites — it simply keeps what is alive in the present and lets the rest dissolve. Samhara is not destruction; it is the clearing that makes room for what comes next.

"Do not cling to the least-recently-used. Release it, and the structure stays clear." — the Gita, interpreted for systems engineers 🙏

Chapter 06 — Test Yourself

LRU Trivia

Three questions. No cheating. Your karma is watching.

Question 1

Capacity 2. You run: put(1,1), put(2,2), get(1), put(3,3). Which key gets evicted?

Correct! 🎉 get(1) bumps key 1 to the head, leaving key 2 at the tail. When put(3,3) needs room, the tail — key 2 — is evicted. FIFO would have dropped key 1 instead; that's the whole difference.

Question 2

Why can't a single hash map alone implement an O(1) LRU cache?

Correct! 🧠 Lookup is O(1), but a plain hash map has no notion of recency order. To find the least-recently-used key you'd scan every entry — O(n). The doubly-linked list is the order, kept in sync with the map. (JS's Map cheats by remembering insertion order internally — it's a map + list in disguise.)

Question 3 — 🌶️ Spicy

In the map + doubly-linked-list design, why doubly-linked and not singly-linked?

Correct! 🔥 When the map hands you a node to move or evict, you must unlink it in O(1). That means rewiring node.prev.next — which requires a prev pointer. A singly-linked list would force an O(n) walk to find the predecessor, breaking the whole guarantee.

The Enlightenment

The Six Truths of the LRU Cache

Map for Speed

The hash map exists for one reason: jump from a key to its node in O(1). Order is none of its business.

List for Order

The doubly-linked list is the recency order — MRU head, LRU tail. prev/next make every relink O(1).

Access = Refresh

Both get and put count as use. Every touch moves a key to the head; that's what "recently used" means.

Evict the Tail

At capacity, the tail node — the least-recently-used — is removed and its key deleted from the map. Two O(1) edits.

Sentinels Kill Branches

Dummy head and tail nodes erase every null-check. Insertion and removal become unconditional pointer writes.

Anitya — Let Go

A cache keeps only what attention lately touched. Eviction is not loss; it is non-attachment, and it keeps you O(1).

कर्म करो, फल की चिंता मत करो

The LRU Cache

A cache must forget.The only question is — what?