Building an LRU Cache from Scratch

The LRU cache is a classic interview question because it tests two data structures at once: a hash map for O(1) lookups and a doubly linked list for O(1) insertion and removal at either end. Together they give O(1) get and set with LRU eviction.

The hash map stores key → node references. The doubly linked list maintains access order: the head is the most recently used entry, the tail is the least recently used. On get, move the node to the head. On set, if at capacity, remove the tail node and delete its key from the map. JavaScript's Map preserves insertion order and supports delete + re-insert to simulate "move to end," which is why the simplified version in the previous lesson works — but the hash map + doubly linked list version is what interviewers and production libraries (like Python's functools.lru_cache) implement under the hood.

Before

Naive approach — scan all entries to find LRU

1// O(n) eviction — too slow at scale2function evictLRU(cache) {3  let oldest = null, oldestTime = Infinity;4  for (const [key, entry] of cache) {5    if (entry.lastAccessed < oldestTime) {6      oldestTime = entry.lastAccessed;7      oldest = key;8    }9  }10  cache.delete(oldest);11}

After

O(1) eviction — hash map + doubly linked list

1class LRUNode {2  constructor(key, value) {3    this.key = key;4    this.value = value;5    this.prev = null;6    this.next = null;7  }8}9 10class LRUCache {11  constructor(capacity) {12    this.capacity = capacity;13    this.map = new Map();14    this.head = new LRUNode(0, 0);15    this.tail = new LRUNode(0, 0);16    this.head.next = this.tail;17    this.tail.prev = this.head;18  }19 20  _remove(node) {21    node.prev.next = node.next;22    node.next.prev = node.prev;23  }24 25  _addToHead(node) {26    node.next = this.head.next;27    node.prev = this.head;28    this.head.next.prev = node;29    this.head.next = node;30  }31 32  get(key) {33    if (!this.map.has(key)) return -1;34    const node = this.map.get(key);35    this._remove(node);36    this._addToHead(node);37    return node.value;38  }39 40  set(key, value) {41    if (this.map.has(key)) {42      this._remove(this.map.get(key));43    } else if (this.map.size >= this.capacity) {44      const lru = this.tail.prev;45      this._remove(lru);46      this.map.delete(lru.key);47    }48    const node = new LRUNode(key, value);49    this._addToHead(node);50    this.map.set(key, node);51  }52}

Exercise

Implement get/set with O(1) average behavior using a Map (or hash map + doubly linked list). Cap capacity at N and prove eviction order with a short test script of accesses.