LRU Cache

time: O(1)
space: O(capacity)
tags: hash-tables · doubly-linked-list · design

in the wild Every database buffer pool, every CPU cache layer, browser cache, Redis (with `allkeys-lru`), and OS page cache — the LRU eviction policy is everywhere.

Problem

Design and implement a Least Recently Used (LRU) cache with O(1) get and put:

LRUCache(capacity) — fixed-capacity cache.
get(key) — return the value if the key exists (and mark it as most-recently-used), else return -1 / null.
put(key, value) — insert / update. If inserting would exceed capacity, evict the least-recently-used entry first.

Both operations must run in O(1).

Examples

cache = LRUCache(2)
put(1, 1)            cache: {1=1}                       — MRU side: 1
put(2, 2)            cache: {1=1, 2=2}                  — MRU side: 2
get(1)        → 1    cache: {2=2, 1=1}                  — 1 just used → moves to MRU
put(3, 3)     evict 2 → cache: {1=1, 3=3}               — MRU side: 3 (was at LRU end: 2)
get(2)        → -1   (evicted)
put(4, 4)     evict 1 → cache: {3=3, 4=4}
get(1)        → -1
get(3)        → 3    cache: {4=4, 3=3}
get(4)        → 4    cache: {3=3, 4=4}

Why this is the canonical "two data structures together" problem

A hash table alone gives O(1) lookup but no ordering — you can't ask "which key was used longest ago?"

A doubly-linked list alone preserves an order but O(n) lookup.

Combine them. A hash map from key → list-node lets you go from key to its place in the list in O(1); a doubly-linked list lets you splice that node to the head (most-recently-used) in O(1). Eviction is just "drop the tail" — also O(1).

This is the textbook example of why "data structures" isn't a memorized table but a toolkit you compose. Cracking LRU means you can also build LFU, ARC, 2Q, and every other cache eviction policy variant. It also shows up indirectly: ordered hash maps (OrderedDict in Python, LinkedHashMap in Java) are the LRU primitive — they bake in the linked-list-of-insertion-order.

Hints

Hint 1 — what does the hash table alone fail at?

A HashMap<Key, Value> gives O(1) read/write but no recency information. Could you augment each value with a last_used timestamp? What's wrong with that approach when capacity is exceeded and you need to evict?

Hint 2 — what does the linked list alone fail at?

A doubly-linked list of (key, value) ordered by recency lets you splice the just-used node to the head in O(1)… if you already have a pointer to it. How do you get from a key to its node?

Hint 3 — the combo

HashMap<Key, *Node> + doubly-linked list of (key, value) ordered MRU → LRU.

get(key): hash-lookup node, splice node to head, return value.
put(key, value): if key exists, update + splice. Otherwise allocate, prepend, hash-insert; if oversize, drop the tail node + remove its key from the hash.

Solution

# Python ships an OrderedDict (insertion-ordered hash map) that is *precisely*
# the hash-map + DLL combo described above. We use it directly for the cleanest
# presentation, then a from-scratch DLL version below to show the mechanics.
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.cap = capacity
        self.od: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.od:
            return -1
        self.od.move_to_end(key, last=True)         # mark MRU
        return self.od[key]

    def put(self, key: int, value: int) -> None:
        if key in self.od:
            self.od.move_to_end(key, last=True)
            self.od[key] = value
            return
        if len(self.od) == self.cap:
            self.od.popitem(last=False)              # drop LRU
        self.od[key] = value

# Trace through the example.
cache = LRUCache(2)
ops = [
    ("put", 1, 1, None),
    ("put", 2, 2, None),
    ("get", 1, None, 1),
    ("put", 3, 3, None),
    ("get", 2, None, -1),
    ("put", 4, 4, None),
    ("get", 1, None, -1),
    ("get", 3, None, 3),
    ("get", 4, None, 4),
]
for op in ops:
    if op[0] == "put":
        cache.put(op[1], op[2])
        print(f"   put({op[1]}, {op[2]})")
    else:
        got, exp = cache.get(op[1]), op[3]
        mark = "✓" if got == exp else "✗"
        print(f"{mark} get({op[1]}) = {got}  (expected {exp})")

// JS Map preserves insertion order, so we can implement LRU on a Map alone.
// delete-then-set moves a key to the "newest" insertion-order slot.
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.m   = new Map();
  }
  get(key) {
    if (!this.m.has(key)) return -1;
    const v = this.m.get(key);
    this.m.delete(key); this.m.set(key, v);          // mark MRU
    return v;
  }
  put(key, value) {
    if (this.m.has(key)) { this.m.delete(key); }
    else if (this.m.size === this.cap) {
      // Oldest insertion = LRU. iterator's next() gives it.
      this.m.delete(this.m.keys().next().value);
    }
    this.m.set(key, value);
  }
}

const cache = new LRUCache(2);
const ops = [
  ["put", 1, 1, null],
  ["put", 2, 2, null],
  ["get", 1, null, 1],
  ["put", 3, 3, null],
  ["get", 2, null, -1],
  ["put", 4, 4, null],
  ["get", 1, null, -1],
  ["get", 3, null, 3],
  ["get", 4, null, 4],
];
for (const [op, a, b, exp] of ops) {
  if (op === "put") { cache.put(a, b); console.log(`   put(${a}, ${b})`); }
  else { const got = cache.get(a); console.log(`${got === exp ? "✓" : "✗"} get(${a}) = ${got}  (expected ${exp})`); }
}

// From-scratch in Rust: HashMap<key, list-index> + a Vec-backed doubly-linked
// list. Vec indices stand in for raw pointers so the borrow checker is happy.
use std::collections::HashMap;

struct DllNode { key: i32, val: i32, prev: usize, next: usize }
const NIL: usize = usize::MAX;

pub struct LRUCache {
    cap:    usize,
    nodes:  Vec<DllNode>,             // arena
    head:   usize,                     // MRU
    tail:   usize,                     // LRU
    index:  HashMap<i32, usize>,       // key → arena idx
    free:   Vec<usize>,                // freelist of reusable arena slots
}

impl LRUCache {
    pub fn new(capacity: usize) -> Self {
        Self {
            cap: capacity,
            nodes: Vec::with_capacity(capacity),
            head: NIL, tail: NIL,
            index: HashMap::with_capacity(capacity),
            free: Vec::new(),
        }
    }

    fn detach(&mut self, i: usize) {
        let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);
        if prev != NIL { self.nodes[prev].next = next; } else { self.head = next; }
        if next != NIL { self.nodes[next].prev = prev; } else { self.tail = prev; }
    }
    fn attach_head(&mut self, i: usize) {
        self.nodes[i].prev = NIL;
        self.nodes[i].next = self.head;
        if self.head != NIL { self.nodes[self.head].prev = i; }
        self.head = i;
        if self.tail == NIL { self.tail = i; }
    }
    fn alloc(&mut self, key: i32, val: i32) -> usize {
        if let Some(i) = self.free.pop() {
            self.nodes[i] = DllNode { key, val, prev: NIL, next: NIL };
            i
        } else {
            self.nodes.push(DllNode { key, val, prev: NIL, next: NIL });
            self.nodes.len() - 1
        }
    }

    pub fn get(&mut self, key: i32) -> i32 {
        let Some(&i) = self.index.get(&key) else { return -1; };
        self.detach(i);
        self.attach_head(i);
        self.nodes[i].val
    }

    pub fn put(&mut self, key: i32, val: i32) {
        if let Some(&i) = self.index.get(&key) {
            self.nodes[i].val = val;
            self.detach(i); self.attach_head(i);
            return;
        }
        if self.index.len() == self.cap {
            let evict = self.tail;
            let ek    = self.nodes[evict].key;
            self.detach(evict);
            self.index.remove(&ek);
            self.free.push(evict);
        }
        let i = self.alloc(key, val);
        self.attach_head(i);
        self.index.insert(key, i);
    }
}

fn main() {
    let mut cache = LRUCache::new(2);
    cache.put(1, 1); println!("   put(1, 1)");
    cache.put(2, 2); println!("   put(2, 2)");
    println!("{} get(1) = {}", if cache.get(1) == 1 { "✓" } else { "✗" }, cache.get(1));
    cache.put(3, 3); println!("   put(3, 3)");
    println!("{} get(2) = {}", if cache.get(2) == -1 { "✓" } else { "✗" }, cache.get(2));
    cache.put(4, 4); println!("   put(4, 4)");
    println!("{} get(1) = {}", if cache.get(1) == -1 { "✓" } else { "✗" }, cache.get(1));
    println!("{} get(3) = {}", if cache.get(3) == 3  { "✓" } else { "✗" }, cache.get(3));
    println!("{} get(4) = {}", if cache.get(4) == 4  { "✓" } else { "✗" }, cache.get(4));
}

#include <iostream>
#include <list>
#include <unordered_map>

// std::list is a doubly-linked list. Splicing a single node is O(1) and
// doesn't invalidate the iterator, which is exactly what we need.
class LRUCache {
    using KV   = std::pair<int, int>;
    int cap_;
    std::list<KV> dll_;
    std::unordered_map<int, std::list<KV>::iterator> index_;
public:
    LRUCache(int capacity) : cap_(capacity) {}

    int get(int key) {
        auto it = index_.find(key);
        if (it == index_.end()) return -1;
        dll_.splice(dll_.begin(), dll_, it->second);   // O(1) move-to-front
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = index_.find(key);
        if (it != index_.end()) {
            it->second->second = value;
            dll_.splice(dll_.begin(), dll_, it->second);
            return;
        }
        if ((int)index_.size() == cap_) {
            index_.erase(dll_.back().first);
            dll_.pop_back();
        }
        dll_.push_front({key, value});
        index_[key] = dll_.begin();
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);                                  std::cout << "   put(1, 1)\n";
    cache.put(2, 2);                                  std::cout << "   put(2, 2)\n";
    std::cout << (cache.get(1) == 1  ? "✓" : "✗") << " get(1) = " << cache.get(1) << "\n";
    cache.put(3, 3);                                  std::cout << "   put(3, 3)\n";
    std::cout << (cache.get(2) == -1 ? "✓" : "✗") << " get(2) = " << cache.get(2) << "\n";
    cache.put(4, 4);                                  std::cout << "   put(4, 4)\n";
    std::cout << (cache.get(1) == -1 ? "✓" : "✗") << " get(1) = " << cache.get(1) << "\n";
    std::cout << (cache.get(3) == 3  ? "✓" : "✗") << " get(3) = " << cache.get(3) << "\n";
    std::cout << (cache.get(4) == 4  ? "✓" : "✗") << " get(4) = " << cache.get(4) << "\n";
}

// Doubly-linked list + open-address hash table. Capacity baked in for the
// demo; production would parameterize and grow as needed.
#include <stdio.h>
#include <stdlib.h>

#define CAP    2
#define HCAP  16

typedef struct Node {
    int          key, val;
    struct Node *prev, *next;
} Node;

static Node  pool[CAP];                  // arena
static int   pool_used = 0;
static Node *head = NULL, *tail = NULL;

static struct { int key; Node* node; int used; } htab[HCAP];

static unsigned hidx(int key) { return ((unsigned)key * 2654435761u) % HCAP; }

static Node* hget(int key) {
    unsigned h = hidx(key);
    while (htab[h].used) {
        if (htab[h].key == key) return htab[h].node;
        h = (h + 1) % HCAP;
    }
    return NULL;
}
static void hset(int key, Node* n) {
    unsigned h = hidx(key);
    while (htab[h].used && htab[h].key != key) h = (h + 1) % HCAP;
    htab[h].used = 1; htab[h].key = key; htab[h].node = n;
}
static void hdel(int key) {
    unsigned h = hidx(key);
    while (htab[h].used && htab[h].key != key) h = (h + 1) % HCAP;
    if (!htab[h].used) return;
    htab[h].used = 0;
    // Rehash subsequent run to repair the open-addressing chain.
    unsigned j = (h + 1) % HCAP;
    while (htab[j].used) {
        int k = htab[j].key; Node* n = htab[j].node;
        htab[j].used = 0;
        hset(k, n);
        j = (j + 1) % HCAP;
    }
}

static void detach(Node* n) {
    if (n->prev) n->prev->next = n->next; else head = n->next;
    if (n->next) n->next->prev = n->prev; else tail = n->prev;
}
static void attach_head(Node* n) {
    n->prev = NULL;
    n->next = head;
    if (head) head->prev = n;
    head = n;
    if (!tail) tail = n;
}

int get_(int key) {
    Node* n = hget(key);
    if (!n) return -1;
    detach(n); attach_head(n);
    return n->val;
}

void put_(int key, int val) {
    Node* n = hget(key);
    if (n) { n->val = val; detach(n); attach_head(n); return; }
    if (pool_used == CAP) {
        hdel(tail->key);
        Node* evict = tail;
        detach(evict);
        *evict = (Node){0};                           // recycle in place
        attach_head(evict);
        evict->key = key; evict->val = val;
        hset(key, evict);
        return;
    }
    Node* slot = &pool[pool_used++];
    slot->key = key; slot->val = val; slot->prev = slot->next = NULL;
    attach_head(slot);
    hset(key, slot);
}

int main(void) {
    put_(1, 1);                printf("   put(1, 1)\n");
    put_(2, 2);                printf("   put(2, 2)\n");
    printf("%s get(1) = %d\n", get_(1) == 1  ? "✓" : "✗", get_(1));
    put_(3, 3);                printf("   put(3, 3)\n");
    printf("%s get(2) = %d\n", get_(2) == -1 ? "✓" : "✗", get_(2));
    put_(4, 4);                printf("   put(4, 4)\n");
    printf("%s get(1) = %d\n", get_(1) == -1 ? "✓" : "✗", get_(1));
    printf("%s get(3) = %d\n", get_(3) == 3  ? "✓" : "✗", get_(3));
    printf("%s get(4) = %d\n", get_(4) == 4  ? "✓" : "✗", get_(4));
    return 0;
}

idle

Python and JS get a free ride because their built-in maps already preserve insertion order — the LRU primitive is baked into the language. Rust and C have to build the doubly-linked-list arena themselves; C++ leans on std::list::splice (which is exactly the O(1) splice operation this problem needs).

Complexity

get / put: O(1) — hash lookup is O(1) amortized; splicing a node in a doubly-linked list is O(1).
Space: O(capacity) — never grows beyond the configured cap.
Without the linked list (timestamp + min-scan): Each eviction would scan all entries for the oldest timestamp — O(n) per put. The DLL is what makes it O(1).

In the wild

Database buffer pools. Postgres, MySQL/InnoDB, Oracle — all use LRU (or LRU-K) on their disk-page caches.
Browser HTTP cache. Pages, images, JS — evicted by LRU policy when storage runs low.
Operating system page cache. Linux's LRU active/inactive lists are a refinement of this exact structure.
Redis with allkeys-lru eviction. The most popular Redis maxmemory policy.
Microservice client caches. Nginx, Varnish, Envoy — all ship LRU as their default in-memory policy.

Variations

LFU (Least Frequently Used). Track per-key access counts, plus a frequency-bucket DLL — O(1) but harder to implement.
LRU-K. Track the K-th-most-recent access timestamp per key; evict by oldest K-th access. Heuristically beats LRU for "scan resistance".
2Q / ARC / TinyLFU. All refinements that better handle scan workloads (e.g. one-pass full-table scans don't blow away your hot set).
Concurrent LRU. Sharded hash + per-shard locks, or fully lock-free with hazard pointers. See Java's Caffeine library for the state of the art.