LRU Cache — Hash Map + Doubly Linked List

Intermediate 11 min read

What you'll learn

✓Why an LRU cache needs O(1) on both get and put
✓How a doubly linked list enables O(1) eviction
✓How a hash map gives O(1) lookup of nodes
✓How to implement the two data structures together cleanly
✓How to discuss tradeoffs versus OrderedDict in interviews

Prerequisites

•Read [Linked Lists Common Operations](/blog/linked-lists-common-operations) for node splicing
•Read [Hashing and Hash Maps](/blog/hashing-and-hash-maps) for O(1) lookup intuition

This is a classic systems-flavored interview question. It tests whether you can combine two data structures to achieve constant-time operations and whether you can implement a doubly linked list without bugs.

The Problem

Design a data structure that supports two operations in O(1) average time:

get(key): return the value if the key exists, otherwise return -1. A successful get marks the key as most recently used.
put(key, value): insert or overwrite the value. If the cache exceeds its capacity, evict the least recently used key before inserting.

Example:

LRUCache cache = LRUCache(2)
cache.put(1, 1)         # cache: {1=1}
cache.put(2, 2)         # cache: {1=1, 2=2}
cache.get(1)            # returns 1, cache: {2=2, 1=1}
cache.put(3, 3)         # evicts key 2
cache.get(2)            # returns -1

Intuition

The naive design uses a dict plus a list of keys for ordering. list.remove is O(n), so both get and put become O(n).

The optimal design combines a hash map keyed by cache key, mapping to nodes in a doubly linked list ordered by recency. The hash map gives O(1) lookup of the node by key. The doubly linked list gives O(1) splicing — remove a node from anywhere and re-insert at the front. The head sentinel marks the most recently used end; the tail sentinel marks the least recently used end. Sentinel nodes eliminate the special cases of inserting into or removing from an empty list.

Every successful get moves a node to the front. Every put either updates an existing node (moved to front) or inserts a new one and evicts from the back if size exceeds capacity.

Explanation with Example

Capacity 2. Start with an empty list: head <-> tail.

put(1, 1): insert node 1 at front. List: head <-> 1 <-> tail.

put(2, 2): insert node 2 at front. List: head <-> 2 <-> 1 <-> tail.

get(1) returns 1. Move node 1 to the front. List: head <-> 1 <-> 2 <-> tail.

put(3, 3): insert node 3 at front. List: head <-> 3 <-> 1 <-> 2 <-> tail. Size exceeds capacity, so evict tail.prev (node 2). List: head <-> 3 <-> 1 <-> tail.

get(2) returns -1 because key 2 is no longer in the map.

after put(1,1):   head <-> [1] <-> tail
after put(2,2):   head <-> [2] <-> [1] <-> tail
after get(1):     head <-> [1] <-> [2] <-> tail
                        MRU             LRU
after put(3,3):   head <-> [3] <-> [1] <-> tail
                (evicted [2] from tail end)

Doubly linked list with MRU near head, LRU near tail

Code

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0,0), tail = new Node(0,0);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }
    private void remove(Node n) {
        n.prev.next = n.next; n.next.prev = n.prev;
    }
    private void addFront(Node n) {
        n.next = head.next; n.prev = head;
        head.next.prev = n; head.next = n;
    }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node n = map.get(key);
        remove(n); addFront(n);
        return n.value;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) remove(map.get(key));
        Node n = new Node(key, value);
        map.put(key, n);
        addFront(n);
        if (map.size() > capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
    }
}

class LRUCache {
    struct Node {
        int key, value;
        Node *prev, *next;
        Node(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    int capacity;
    unordered_map<int, Node*> map;
    Node *head, *tail;

    void removeNode(Node* n) {
        n->prev->next = n->next; n->next->prev = n->prev;
    }
    void addFront(Node* n) {
        n->next = head->next; n->prev = head;
        head->next->prev = n; head->next = n;
    }
public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(); tail = new Node();
        head->next = tail; tail->prev = head;
    }
    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        Node* n = it->second;
        removeNode(n); addFront(n);
        return n->value;
    }
    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) removeNode(it->second);
        Node* n = new Node(key, value);
        map[key] = n;
        addFront(n);
        if ((int)map.size() > capacity) {
            Node* lru = tail->prev;
            removeNode(lru);
            map.erase(lru->key);
            delete lru;
        }
    }
};

Edge Cases

Capacity of 1: every put evicts the previous key.
Repeated puts on the same key: detect, remove the old node, insert at front.
Get on a missing key: do not mutate the list, just return -1.
Capacity 0: usually disallowed, but you can short-circuit and store nothing.

Complexity Analysis

get: O(1) average due to hash map lookup plus constant-time list splicing.
put: O(1) average. Insertion, optional removal, and eviction are constant time.
Space: O(capacity) for both the map and the list.

How to Explain It in an Interview

State the goal: O(1) on both operations. Hash maps give O(1) lookup but no order. Doubly linked lists give O(1) insertion and removal at arbitrary positions if you have a pointer. Combine them by storing the node in the map.

Walk through the invariant: head-adjacent is MRU, tail-adjacent is LRU. Every successful get moves a node to the front. Every put updates or inserts at the front, evicting from the back if full.

If asked about Python’s OrderedDict: it works and is acceptable, but the manual implementation demonstrates you understand the underlying data structures.

LFU Cache, which adds frequency tracking.
All O`one Data Structure for ordered key buckets.
Design Browser History, which uses linked-list-like state.
Design HashMap. See also Hashing and Hash Maps.

Wrap up

Practice writing the doubly linked list helpers first until splicing is automatic, then layer the hash map. Revisit Linked Lists Common Operations if pointer juggling is uncomfortable.