LRU Cache (Map-Backed)

An LRU (Least Recently Used) cache evicts the entry that has been untouched the longest when capacity overflows. The trick that makes both `get` and `put` O(1) is JavaScript's `Map` preserving insertion order. This snippet covers the Map-backed implementation, an explicit doubly-linked-list version that mirrors what other languages need, and a TTL-aware variant that evicts entries that are too old.

JavaScript

Medium

3 snippets

data-structures

lru-cache

code-template

hash-table

264 views

Map-backed LRU

Ask AI

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

const cache = new LRUCache(2);
cache.put('a', 1);
cache.put('b', 2);
cache.get('a');
cache.put('c', 3);           // should evict 'b' (least recently used)
console.log(cache.get('a')); // 1
console.log(cache.get('b')); // undefined
console.log(cache.get('c')); // 3

JavaScript's Map keeps keys in insertion order, and re-setting an existing key does NOT move it to the end (which means we have to delete and re-insert). On get, we delete-and-reinsert to mark the key as recently used. On put, we evict the oldest by reading data.keys().next().value. Both operations are O(1) on a Map, so the cache is O(1) for both get and put. This is the cleanest LRU implementation in modern JavaScript and the version most production code uses.

Doubly-linked list version

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

class LRUCacheList {
    constructor(capacity) {
        this.capacity = capacity;
        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;
    }
    #remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    #addToFront(node) {
        node.prev = this.head;
        node.next = this.head.next;
        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) {
        if (this.map.has(key)) {
            const existing = this.map.get(key);
            existing.value = value;
            this.#remove(existing);
            this.#addToFront(existing);
            return;
        }
        const node = new Node(key, value);
        this.map.set(key, node);
        this.#addToFront(node);
        if (this.map.size > this.capacity) {
            const lru = this.tail.prev;
            this.#remove(lru);
            this.map.delete(lru.key);
        }
    }
}

const c2 = new LRUCacheList(2);
c2.put(1, 'a');
c2.put(2, 'b');
c2.get(1);
c2.put(3, 'c');
console.log(c2.get(2)); // undefined (evicted)
console.log(c2.get(1)); // 'a'

The classic textbook LRU pairs a hash table (key -> node) with a doubly linked list (recency order). get finds the node via the map, then unlinks and re-inserts at the front in O(1). put either updates an existing node or inserts a new one at the front; when over capacity, the tail node is the LRU eviction. This is the implementation languages without insertion-ordered hashes (Java's HashMap, C++'s unordered_map) need to write by hand. In JavaScript the Map-backed version above is shorter and just as fast, but knowing this version is interview gold.

TTL-aware LRU

Back to Code Snippets