Building an LRU Cache: The Hash Map Plus Doubly Linked List Trick

Quick Answer

An LRU (least recently used) cache evicts the entry that has gone longest without being accessed once it hits capacity. To get O(1) reads and writes you combine two structures: a hash map from key to node for instant lookup, and a doubly linked list that keeps nodes in recency order so you can move a node to the front or drop the tail in constant time.

What an LRU cache does

A cache has a fixed size. When it is full and a new key arrives, something must go. LRU evicts the entry accessed least recently, betting that recently used data will be used again soon.

The interview version, behind LeetCode 146, asks for two operations, both in O(1):

• get(key) returns the value and marks the key most recently used.
• put(key, value) inserts or updates, marks it most recently used, and evicts the least recently used key when over capacity.

The O(1) requirement is the entire difficulty. One array or one object cannot do fast lookup and fast recency reordering at the same time. You need two structures cooperating.

The policy is everywhere in practice: CPU caches, a database buffer pool, a browser's in-memory image cache, CDN edge nodes, and application-level memoisation of expensive results. Anywhere storage is bounded and recency predicts reuse, LRU is a sensible default.

Why two structures

Look at what each operation needs.

• Find a key fast: a hash map gives O(1) lookup. But it has no order, so it cannot say which key is least recently used.
• Reorder by recency fast: a doubly linked list can unlink a node from the middle and splice it to the front in O(1), because each node knows its previous and next neighbours. But a list has O(n) lookup.

Combine them. The hash map stores key to node; the node lives in the linked list. Lookups go through the map, recency updates through the list. The front of the list is most recently used; the node just before the tail sentinel is the eviction candidate.

Reach for a plain array instead and every move-to-front becomes an O(n) shift, which breaks the O(1) contract before you start.

Some languages hand you this for free. Java's LinkedHashMap with access order enabled is exactly a hash map plus a linked list, and overriding removeEldestEntry adds eviction. Python's OrderedDict, or functools.lru_cache, does the same job.

The implementation

Sentinel head and tail nodes remove the null checks at the ends. Every real node sits between them.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();          // key to node
    this.head = new Node(null, null);
    this.tail = new Node(null, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._addFront(node);         // touch: move to front
    return node.val;
  }
  put(key, val) {
    if (this.map.size === this.capacity) {
      const lru = this.tail.prev;  // node before tail sentinel
      this._remove(lru);
      this.map.delete(lru.key);    // keep map and list in sync
    }
    const node = new Node(key, val);
    this.map.set(key, node);
    this._addFront(node);
  }
}

With capacity 2: put a, put b, get a (a is now most recent), then put c evicts b. Real output:

get a -> 1
get b -> -1   // b was evicted
get a -> 1
get c -> 3

The bug to watch: on eviction you must delete from both the list and the map. Remove it from only the list and the map keeps a stale reference forever, so the cache leaks memory and its size check drifts.

The JavaScript Map shortcut

JavaScript's Map iterates keys in insertion order, and that is a spec guarantee. You can lean on it and drop the linked list entirely.

get(key) {
  if (!this.map.has(key)) return -1;
  const val = this.map.get(key);
  this.map.delete(key);     // pull from current position
  this.map.set(key, val);   // re-insert at the end: most recent
  return val;
}
put(key, val) {
  if (this.map.has(key)) this.map.delete(key);
  else if (this.map.size === this.capacity) {
    const oldest = this.map.keys().next().value; // first key = LRU
    this.map.delete(oldest);
  }
  this.map.set(key, val);
}

Deleting a key and re-setting it moves it to the back of the iteration order, marking it most recently used. The least recently used key is whatever map.keys().next().value returns, the oldest surviving insertion. Same test, same result, plus the final order:

get a -> 1
get b -> -1
keys in order: [ 'a', 'c' ]

Shorter, and fast enough for most real use. The explicit linked-list version still earns its keep: it is what an interviewer wants, and what languages without ordered maps require.

Why not a plain object

It is tempting to use {} instead of Map. Do not. Plain objects do not preserve insertion order for keys that look like array indices. Integer-like keys come out first, in ascending numeric order, whatever order you added them:

const o = {};
o['2'] = 'two';
o['1'] = 'one';
o['10'] = 'ten';
o['b'] = 'bee';
o['a'] = 'aye';
Object.keys(o);
// [ '1', '2', '10', 'b', 'a' ]  -- not insertion order

Your least-recently-used lookup would return the numerically smallest key, not the oldest one, and the cache would evict the wrong entries without a single error.

There are smaller reasons too. Object keys are always coerced to strings, so 1 and '1' collide, while a Map key can be any value including an object. A fresh object also carries inherited keys from its prototype unless you build it with Object.create(null). For an LRU, the ordering bug alone is disqualifying; Map gives true insertion order for any key type, O(1) size, and no prototype collisions.

Frequently Asked Questions