jsschools

LRU Cache

A fixed-capacity cache that evicts the Least Recently Used item when full, implemented with a hash map and a doubly linked list for O(1) get and put.

Spec ↗

Syntax

class LRUCache {
  constructor(capacity) { ... }
  get(key)       { ... }  // O(1)
  put(key, value){ ... }  // O(1)
}

Parameters

NameTypeRequiredDescription
capacity number Yes Maximum number of key-value pairs the cache holds before eviction.

Returns

LRUCache — A new LRU Cache with the given capacity.

Examples

class LRUCache {
  #cap; #map; #head; #tail;
  constructor(cap) {
    this.#cap  = cap;
    this.#map  = new Map();
    // sentinel nodes
    this.#head = { key: 0, val: 0, prev: null, next: null };
    this.#tail = { key: 0, val: 0, prev: null, next: null };
    this.#head.next = this.#tail;
    this.#tail.prev = this.#head;
  }
  #remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  #insertFront(node) {
    node.next = this.#head.next;
    node.prev = this.#head;
    this.#head.next.prev = node;
    this.#head.next = node;
  }
  get(key) {
    if (!this.#map.has(key)) return -1;
    const node = this.#map.get(key);
    this.#remove(node); this.#insertFront(node);
    return node.val;
  }
  put(key, val) {
    if (this.#map.has(key)) this.#remove(this.#map.get(key));
    const node = { key, val, prev: null, next: null };
    this.#insertFront(node);
    this.#map.set(key, node);
    if (this.#map.size > this.#cap) {
      const lru = this.#tail.prev;
      this.#remove(lru);
      this.#map.delete(lru.key);
    }
  }
}

const cache = new LRUCache(2);
cache.put(1, 10); cache.put(2, 20);
console.log(cache.get(1));  // 10 — moves 1 to front
cache.put(3, 30);           // evicts key 2 (LRU)
console.log(cache.get(2));  // -1 (evicted)
console.log(cache.get(3));  // 30
Output 
10
-1
30

// Shortcut: JS Map preserves insertion order, so the oldest key
// is always the first entry (Map.keys().next().value).
class LRUSimple {
  #cap; #map = new Map();
  constructor(cap) { this.#cap = cap; }
  get(key) {
    if (!this.#map.has(key)) return -1;
    const val = this.#map.get(key);
    this.#map.delete(key); this.#map.set(key, val); // refresh order
    return val;
  }
  put(key, val) {
    if (this.#map.has(key)) this.#map.delete(key);
    this.#map.set(key, val);
    if (this.#map.size > this.#cap) this.#map.delete(this.#map.keys().next().value);
  }
}
const lru = new LRUSimple(2);
lru.put('a', 1); lru.put('b', 2);
lru.get('a');     // refresh a
lru.put('c', 3); // evicts b
console.log(lru.get('b'), lru.get('a'));
Output 
-1 1

Notes

| Operation | Time | Space | |----------|------|-------| | get | O(1) | O(1) | | put | O(1) | O(capacity) | The classic O(1) implementation combines: - A `Map<key, DLL-node>` for O(1) lookup by key. - A doubly linked list for O(1) move-to-front and O(1) remove-LRU. The JavaScript Map short-cut (using insertion order) is elegant but relies on internal V8 behaviour — the DLL version is portable.

See also