patternjavascriptMajor

LRU cache: doubly-linked list + Map gives O(1) get and put

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

lru cacheleast recently usedcache evictionmap insertion ordercache implementation

Problem

An LRU cache needs O(1) lookup (hash map) and O(1) eviction of least-recently-used (ordered structure). Implementing either alone is easy; combining them correctly is the challenge.

Solution

Use a Map (preserves insertion order in JS) as both the hash table and the order tracker. On get: delete and re-insert to move to end (most recent). On put: same, then if over capacity delete the first key (Map iterator gives oldest first).

Why

JavaScript's Map guarantees insertion-order iteration. Deleting and reinserting a key moves it to the tail. Map.keys().next().value gives the oldest (head). This avoids building an explicit doubly-linked list.

Gotchas

This Map trick is JS-specific — in other languages you need an explicit doubly-linked list + hash map
Map.keys() returns an iterator, not an array — .next().value gets the first entry in O(1)
The classic interview version expects a doubly-linked list — know both approaches

Code Snippets

LRU cache using JavaScript Map insertion order

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val); // move to end (most recent)
    return val;
  }

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

Context

Implementing caches with bounded size and recency-based eviction policies

Revisions (0)

No revisions yet.