Build Your Own LRU Cache

You write a function that hits a slow database query. The result won't change for 10 minutes, so you memoize it. Fine. But you have 500 distinct input combinations — after an hour of traffic, your in-memory cache has ballooned to 500 entries, most of them for queries that fired once and will never fire again. You're holding stale data in memory with no way to shed it.

What you actually want: a cache that keeps the most recently used entries and automatically evicts the oldest ones when it fills up. That's an LRU cache. You've seen the acronym in Redis config (maxmemory-policy allkeys-lru), in browser page histories, in CDN cache eviction policies. Here's exactly how it works.

What We're Building

• LRUCache(capacity) — bounded cache, max capacity entries
• .get(key) — O(1) lookup; marks the entry as most-recently-used; returns undefined if missing
• .put(key, value) — O(1) insert; evicts the least-recently-used entry when at capacity
• .delete(key) — O(1) removal
• A bounded memoize wrapper built on top

The O(1) requirement on both get and put is the constraint that makes the data structure interesting. A naive solution — keep an array sorted by access time — needs O(n) to find and remove the LRU entry on every operation.

The HashMap gives O(1) lookup by key. The doubly linked list tracks access order — MRU at the front, LRU at the back. HEAD and TAIL are sentinel nodes: they hold no real data, never get evicted, and act as stable anchors so insert/remove at both ends never needs null checks.

Step 1: The Node

// lru-cache.js
 
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

Each node stores both key and value. The key on the node looks redundant — you already have it in the Map. But when you evict the LRU node from the tail of the list, you need that key to also remove it from the Map. Without it, you'd need a reverse lookup, which costs O(n).

Step 2: The Cache Skeleton

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.size = 0;
    this.map = new Map(); // key → Node
 
    // Sentinels — never hold real data, never removed
    this.head = new Node(null, null); // MRU side
    this.tail = new Node(null, null); // LRU side
 
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
}

Empty cache: HEAD and TAIL point to each other. First real entry goes between them. When the cache drains to empty, they reconnect. The sentinels mean every real node always has a non-null prev and next — you never need to special-case an empty list or an operation at either end.

Step 3: The Two Core Helpers

Every operation reduces to: move a node to the front, or remove a node from wherever it sits.

class LRUCache {
  // ... constructor above
 
  addToFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }
 
  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
}

Both are O(1) — a fixed number of pointer assignments regardless of list size.

addToFront inserts node between HEAD and whatever is currently first. Reading the four lines in order: set node.prev to HEAD, set node.next to whatever HEAD currently points at, update that former-first node's prev to point back at node, then update HEAD's next to point at node.

removeNode stitches the surrounding nodes together over the top of node. After this, node still has its old prev and next pointers set — but nothing in the list points to it, so it's effectively detached.

Step 4: get and put

class LRUCache {
  // ... constructor, addToFront, removeNode
 
  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
 
    // This access makes it MRU
    this.removeNode(node);
    this.addToFront(node);
 
    return node.value;
  }
 
  put(key, value) {
    const existing = this.map.get(key);
 
    if (existing) {
      existing.value = value;
      this.removeNode(existing);
      this.addToFront(existing);
      return;
    }
 
    const node = new Node(key, value);
    this.map.set(key, node);
    this.addToFront(node);
    this.size++;
 
    if (this.size > this.capacity) {
      // tail.prev is always the LRU entry
      const lru = this.tail.prev;
      this.removeNode(lru);
      this.map.delete(lru.key);
      this.size--;
    }
  }
 
  delete(key) {
    const node = this.map.get(key);
    if (!node) return false;
    this.removeNode(node);
    this.map.delete(key);
    this.size--;
    return true;
  }
}
 
module.exports = { LRUCache };

get is one Map lookup plus two pointer operations. Fast.

put has three cases: key already exists (update value, promote to front), new key under capacity (add to front), new key at capacity (add to front, then evict the node right before TAIL). The eviction uses lru.key to remove the entry from the Map — this is the moment where storing the key on the node pays off.

One thing to get right: this.map.delete(lru.key) must happen alongside removeNode. If you only unlink the node from the list and forget the Map, you have a stale Map entry pointing at an orphaned node. The next get for that key returns a value that was supposed to be gone. Classic silent stale-data bug.

Updating an existing key doesn't increase this.size. That's intentional — you're replacing a value, not adding an entry. Without this guard, put('x', 1); put('x', 2); put('x', 3) would push you three slots into capacity for what should be one entry.

Step 5: Bounded Memoize

const { LRUCache } = require('./lru-cache');
 
function memoize(fn, capacity = 100) {
  const cache = new LRUCache(capacity);
 
  return function memoized(...args) {
    const key = JSON.stringify(args);
 
    // Box the result. A bare `if (cached !== undefined)` would treat a cached
    // `undefined` as a miss and call fn() again, every single time.
    const hit = cache.get(key);
    if (hit) return hit.value;
 
    const result = fn.apply(this, args);
    cache.put(key, { value: result });
    return result;
  };
}

The box around the value is not ceremony. get returns undefined for a missing key, so a function that legitimately returns undefined — a lookup that found nothing, a void side-effecting call — is indistinguishable from a cache miss. Store { value: result } and the truthiness test is asking the right question: did I get a node back, not was the value falsy. The same bug bites 0, '' and null if you compare against those instead.

JSON.stringify(args) as the cache key works for strings, numbers, booleans, and plain objects. It breaks for functions, Date instances, undefined, and circular structures — those need a custom serializer. For the typical memoize use case (pure computations, API responses keyed by numeric IDs), it's good enough.

const slugify = memoize((str) => {
  return str.toLowerCase().replace(/[^a-z0-9]+/g, '-').replace(/^-|-$/g, '');
}, 200);
 
// First call: runs the replace logic
slugify('Hello World'); // 'hello-world'
 
// Second call: cache hit, zero work
slugify('Hello World'); // 'hello-world' — from cache

With an unbounded memoize, 500 unique inputs means 500 results held forever. With capacity: 200, only the 200 most recently requested values are retained. Call 201 evicts whichever of those 200 hasn't been used in the longest time.

Full Implementation

// lru-cache.js
 
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.size = 0;
    this.map = new Map();
 
    this.head = new Node(null, null);
    this.tail = new Node(null, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  addToFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }
 
  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
 
  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.removeNode(node);
    this.addToFront(node);
    return node.value;
  }
 
  put(key, value) {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.removeNode(existing);
      this.addToFront(existing);
      return;
    }
    const node = new Node(key, value);
    this.map.set(key, node);
    this.addToFront(node);
    this.size++;
    if (this.size > this.capacity) {
      const lru = this.tail.prev;
      this.removeNode(lru);
      this.map.delete(lru.key);
      this.size--;
    }
  }
 
  delete(key) {
    const node = this.map.get(key);
    if (!node) return false;
    this.removeNode(node);
    this.map.delete(key);
    this.size--;
    return true;
  }
}
 
module.exports = { LRUCache };

Testing

// test.js — run with: node test.js
 
const { LRUCache } = require('./lru-cache');
 
function assert(condition, message) {
  if (!condition) throw new Error(`FAIL: ${message}`);
  console.log(`PASS: ${message}`);
}
 
// Basic get and put
const cache = new LRUCache(3);
cache.put('a', 1);
cache.put('b', 2);
cache.put('c', 3);
assert(cache.get('a') === 1, 'get returns existing value');
assert(cache.get('z') === undefined, 'get missing key returns undefined');
 
// Eviction: after put(a,b,c) then get(a), order is a(MRU) -> c -> b(LRU)
// put(d) evicts b
cache.put('d', 4);
assert(cache.get('b') === undefined, 'LRU entry evicted on overflow');
assert(cache.get('d') === 4, 'new entry accessible');
assert(cache.get('a') === 1, 'non-evicted MRU entry still accessible');
assert(cache.size === 3, 'size stays at capacity');
 
// Update: should not increase size, should promote to MRU
const c2 = new LRUCache(2);
c2.put('x', 10);
c2.put('y', 20);
c2.put('x', 99); // update — should not evict 'y'
assert(c2.get('y') === 20, 'update does not evict other entries');
assert(c2.get('x') === 99, 'updated value is stored');
assert(c2.size === 2, 'size unchanged after update');
 
// Delete
c2.delete('x');
assert(c2.get('x') === undefined, 'deleted key is gone');
assert(c2.size === 1, 'size decremented after delete');
 
// Capacity 1 edge case
const c3 = new LRUCache(1);
c3.put('a', 1);
c3.put('b', 2);
assert(c3.get('a') === undefined, 'capacity-1: first entry evicted by second');
assert(c3.get('b') === 2, 'capacity-1: second entry is accessible');
 
console.log('\nAll tests passed.');

The eviction trace is worth tracing through manually once. After put('a'), put('b'), put('c'): the list is HEAD ↔ c ↔ b ↔ a ↔ TAIL — last inserted is MRU. After get('a'), a moves to front: HEAD ↔ a ↔ c ↔ b ↔ TAIL. When put('d') pushes size to 4, the node before TAIL (b) is the one evicted.

What We Skipped

Pure Map shortcut: JavaScript's Map preserves insertion order, so you can implement a simplified LRU without a linked list. On get, delete and re-insert the key to promote it; on overflow, evict via map.keys().next().value (the oldest key):

class LRUCache {
  constructor(cap) { this.cap = cap; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return undefined;
    const val = this.map.get(key);
    this.map.delete(key); this.map.set(key, val);
    return val;
  }
  put(key, value) {
    this.map.delete(key); this.map.set(key, value);
    if (this.map.size > this.cap) this.map.delete(this.map.keys().next().value);
  }
}

The tradeoff: every get does two Map operations (delete + re-insert) instead of one. At high call rates the extra churn is measurable. For most applications it doesn't matter — pick whichever version you find easier to reason about.

TTL (time-to-live): Production caches expire entries by age, not just by recency. Add an expiresAt timestamp to each node and check it on get — stale entries are treated as misses and removed from both the list and Map. Lazy expiration (check on access) is simpler than eager expiration (a setInterval sweep) and good enough unless access patterns are very sparse.

Thundering herd on cache miss: Multiple concurrent callers requesting the same missing key all get a miss, all kick off the expensive work, all try to write the same result back. The fix: store a Promise in the Map as a placeholder on the first miss. Subsequent callers pick up the same Promise and await it instead of starting duplicate work. This turns the cache from a read-through store into a coalescing gate.

Weight-based capacity: new LRUCache(1000) means 1000 entries regardless of their size. Real caches measure capacity in bytes — a 4KB JSON blob and a 3-character string both count as "1 entry" under count-based sizing, which is misleading. Add a weight function (defaults to () => 1, swap in (k, v) => JSON.stringify(v).length for byte sizing) and track totalWeight instead of this.size. Eviction then loops until totalWeight <= maxWeight.

The doubly linked list + hashmap combination is one of the few data structures where knowing the internals changes how you use it. Two things follow directly from the code once you've written it. Reads are writes: every get mutates the list, so a read-heavy workload is doing pointer surgery on a shared structure, and an LRU is not thread-safe or concurrent-friendly for free. And recency is not freshness — a hot key survives eviction forever regardless of how stale its value is, which is why real caches pair LRU with a TTL rather than treating it as one.