Building an LRU Cache From Scratch

An LRU (least-recently-used) cache keeps a fixed number of items and, when it's full and a new item needs to be added, evicts whichever item hasn't been touched in the longest time. It shows up everywhere — browser tab management, database buffer pools, functools.lru_cache in Python, in-memory API response caches — and it's also one of the more instructive data structures to build yourself, because the naive version is easy and the efficient version requires combining two structures in a specific way.

The naive version, and why it's not good enough

The obvious implementation is an array of { key, value } pairs: on every access, find the item, move it to the front, and if the cache is over capacity, drop the last item.

class NaiveLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.items = []; // most recently used at the front
  }

  get(key) {
    const index = this.items.findIndex((item) => item.key === key);
    if (index === -1) return undefined;
    const [item] = this.items.splice(index, 1);
    this.items.unshift(item);
    return item.value;
  }

  put(key, value) {
    const index = this.items.findIndex((item) => item.key === key);
    if (index !== -1) this.items.splice(index, 1);
    this.items.unshift({ key, value });
    if (this.items.length > this.capacity) this.items.pop();
  }
}

This works, but findIndex and splice are both O(n). For a cache with a few hundred entries that's not going to hurt you, but the whole point of an LRU cache is usually to sit in a hot path — an O(n) cache defeats a lot of its own purpose once n grows.

The O(1) version: hash map + doubly linked list

The efficient implementation combines two structures:

• A hash map from key to node, for O(1) lookup.
• A doubly linked list ordering nodes from most- to least-recently-used, for O(1) reordering and eviction.

The map gives you instant access to any node; the linked list lets you move that node to the front, or drop the tail, without shifting anything else. Neither structure alone gets you both properties — an array gives you ordering but not O(1) lookup-by-key, and a map alone gives you lookup but no ordering.

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key -> Node

    // Sentinel head/tail nodes remove the need for null-checks at the edges.
    this.head = new Node(null, null);
    this.tail = new Node(null, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  #remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  #addToFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.#remove(node);
    this.#addToFront(node);
    return node.value;
  }

  put(key, value) {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.#remove(existing);
      this.#addToFront(existing);
      return;
    }

    if (this.map.size >= this.capacity) {
      const lru = this.tail.prev;
      this.#remove(lru);
      this.map.delete(lru.key);
    }

    const node = new Node(key, value);
    this.map.set(key, node);
    this.#addToFront(node);
  }
}

Every operation — get, put, and eviction — is O(1). The sentinel head and tail nodes are a small trick worth calling out: without them, adding to an empty list or removing the only remaining node requires special-casing null checks everywhere. With them, head.next is always "the most recent real node or the tail," so the list is never actually empty from the code's point of view.

Trying it out

const cache = new LRUCache(3);

cache.put('a', 1);
cache.put('b', 2);
cache.put('c', 3);
cache.get('a');       // touches 'a' — order is now b, c, a
cache.put('d', 4);    // capacity exceeded — evicts 'b', the actual least-recently-used

cache.get('b'); // undefined — evicted
cache.get('a'); // 1 — still present
cache.get('d'); // 4 — still present

A JavaScript shortcut worth knowing

If you're in an environment where you don't need to hand-roll this, Map in JavaScript already preserves insertion order and lets you re-insert a key to move it to the end — which gets you most of the way to an LRU with far less code:

class SimpleLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value); // re-insert = move to the "most recent" end
    return value;
  }

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

This is also O(1) per operation, because Map's delete-and-reinsert is O(1) and iterating .keys().next() to find the oldest key is O(1) (it doesn't scan — it just returns the first entry in insertion order). For most real-world uses this is the version worth actually shipping; the linked-list version above is worth building once by hand so you understand what Map is doing for you under the hood.

Takeaway

The naive array-based LRU is fine until it isn't — the moment your cache is on a hot path with meaningful size, the O(n) lookup and reorder cost starts to show up in profiles. The hash-map-plus-linked-list combination is the standard fix, and it's a good example of a broader pattern: when one structure gives you fast lookup and another gives you fast ordering, and you need both, you don't pick one — you combine them and keep them in sync.