Design an LRU Cache

O(1) get/put with HashMap plus doubly-linked list.

Advanced16 min read

Read these first

Concurrency Toolkit for LLD

Why this matters

LRU cache is a data-structure favourite — tests HashMap + linked list coordination.
Appears in rate limiting, session stores, and CDN edge discussions.
Thread-safe variant separates staff-level candidates from senior.

HashMap

key → Node

Doubly-linked list

head (MRU)

...

tail (LRU)

Map gives O(1) lookup; list gives O(1) eviction order.

Requirements

Functional

get(key) returns value or absent
put(key, value) inserts or updates; evicts least-recently-used when at capacity
Both operations must be O(1) average time

Non-functional

Optional thread-safe variant for concurrent readers/writers
Capacity fixed at construction

Data structures

HashMap key → Node for O(1) lookup
Doubly-linked list from MRU (head) to LRU (tail) for O(1) promote and evict

On get: move node to head. On put: insert at head; if over capacity, remove tail and delete from map.

Java

public final class LruCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);

    public LruCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToHead(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> existing = map.get(key);
        if (existing != null) {
            existing.value = value;
            moveToHead(existing);
            return;
        }
        if (map.size() >= capacity) {
            Node<K, V> lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        Node<K, V> node = new Node<>(key, value);
        map.put(key, node);
        addToHead(node);
    }
    // moveToHead, remove, addToHead omitted for brevity
}

Thread safety

Wrap with ReentrantReadWriteLock if reads dominate, or use ConcurrentHashMap + synchronized list mutations. For interviews, state the trade-off: finer locking vs simplicity.

Quick recall

Everything you need if you only revisit this box.

HashMap for O(1) key lookup
Doubly-linked list for usage order
get/put both promote to MRU
Evict tail when size > capacity
Thread safety is a separate design decision

CampusOS extension

Distributed LRU uses Redis with TTL or a dedicated cache cluster — see System Design caching articles. The in-process version here is the building block inside one API node.

Test yourself

Answer these before moving on — recall is what makes it stick.