Designing an O(1) LRU Cache with Doubly Linked List

Problem Summary

We need to design an LRU (Least Recently Used) cache that supports two operations in O(1) average time. The cache has a fixed capacity and must evict the least recently used item when it becomes full. The operations are get(key) which returns the value for a key or -1 if it doesn’t exist, and put(key, value) which inserts or updates a key. Constraints are 1 <= capacity <= 3000, keys in [0, 10⁴], values in [0, 10⁵], and up to 2*10⁵ total operations.

My Approach

The best-known pattern for an LRU cache couples two structures that each excel at a separate part of the job.

• A hash map for O(1) lookup by key, mapping key to a node in the list.
• A doubly linked list to maintain recency order. The most recently used item lives near one end, and the least recently used near the other.

Why combine both. The map answers “do we have this key” in constant time. The list answers “what’s the oldest key” and can move nodes to the most-recently-used position in constant time. That movement is the soul of LRU. Every get and put that touches a key must mark it as most recently used.

There are two clean ways to maintain order. Either push most recent items to the head or to the tail. I prefer a tail-as-MRU layout because eviction becomes “remove from head->next,” which is easy to see. Two sentinel nodes (dummy head and dummy tail) eliminate edge cases like empty list or single element removals.

On get(key)

• If the key is not present, return -1.
• If present, move its node to the MRU position near the tail, then return the value.

On put(key, value)

• If the key already exists, update the value and move it to the MRU position.
• If it doesn’t exist and the cache is full, evict the LRU node at the head side and erase its key from the map. Then insert the new node at the tail side and record it in the map.

Each step is O(1) because the map lookup/erase/insert is O(1) on average, and the list operations are pointer manipulations with no traversal.

Why This Works

An LRU cache must always identify the least recently used key at eviction time and must update the recency of any accessed key. The doubly linked list maintains a strict total order from least recent to most recent, and the sentinel nodes give constant-time removal and insertion without special handling. The hash map guarantees we can locate a node by key in constant time and attach it to the list operations.

Correctness comes from maintaining these invariants throughout all operations.

• Every key present in the cache appears exactly once in the list and exactly once in the map.
• The list order reflects access recency, with the head side as least recent and tail side as most recent.
• On get and on updating put, we remove the node from its current position and reinsert it at the MRU position.
• On insertion when full, we evict the node at the LRU position and remove it from the map, keeping capacity exact.

With these invariants, the LRU property holds at all times, and return values are correct since the map directly references the stored node values.

Code Walkthrough

Below is a clean C++ implementation that follows the approach with an unordered_map and a custom doubly linked list with sentinel nodes. The operations are all O(1) on average.

C++
Copy
1
#include <unordered_map>
2
using namespace std;
3
4
class LRUCache {
5
    struct Node {
6
        int key;
7
        int value;
8
        Node* prev;
9
        Node* next;
10
        Node(int k, int v): key(k), value(v), prev(nullptr), next(nullptr) {}
11
    };
12
13
    int capacity_;
14
    unordered_map<int, Node*> index_;   // key -> node
15
    Node* head_;  // dummy head (LRU side)
16
    Node* tail_;  // dummy tail (MRU side)
17
18
    // Remove a node from the list in O(1)
19
    void detach(Node* node) {
20
        Node* p = node->prev;
21
        Node* n = node->next;
22
        p->next = n;
23
        n->prev = p;
24
    }
25
26
    // Insert a node right before tail_ (MRU position) in O(1)
27
    void attachToMRU(Node* node) {
28
        node->prev = tail_->prev;
29
        node->next = tail_;
30
        tail_->prev->next = node;
31
        tail_->prev = node;
32
    }
33
34
    // Move an existing node to the MRU position in O(1)
35
    void moveToMRU(Node* node) {
36
        detach(node);
37
        attachToMRU(node);
38
    }
39
40
    // Evict the least recently used node from head_ side in O(1)
41
    void evictLRU() {
42
        Node* lru = head_->next;
43
        detach(lru);
44
        index_.erase(lru->key);
45
        delete lru;
46
    }
47
48
public:
49
    LRUCache(int capacity): capacity_(capacity) {
50
        head_ = new Node(-1, -1);
51
        tail_ = new Node(-1, -1);
52
        head_->next = tail_;
53
        tail_->prev = head_;
54
    }
55
56
    int get(int key) {
57
        auto it = index_.find(key);
58
        if (it == index_.end()) return -1;
59
        Node* node = it->second;
60
        moveToMRU(node);
61
        return node->value;
62
    }
63
64
    void put(int key, int value) {
65
        auto it = index_.find(key);
66
        if (it != index_.end()) {
67
            Node* node = it->second;
68
            node->value = value;
69
            moveToMRU(node);
70
            return;
71
        }
72
73
        if ((int)index_.size() == capacity_) {
74
            evictLRU();
75
        }
76
77
        Node* node = new Node(key, value);
78
        attachToMRU(node);
79
        index_[key] = node;
80
    }
81
82
    ~LRUCache() {
83
        // Cleanup allocated nodes to prevent leaks
84
        Node* cur = head_;
85
        while (cur) {
86
            Node* nxt = cur->next;
87
            delete cur;
88
            cur = nxt;
89
        }
90
    }
91
};

Key sections explained.

• The Node struct stores key and value, and maintains prev and next pointers. Keeping the key on the node is useful for eviction when we need to erase the map entry.
• The list uses two sentinel nodes, head_ and tail_. The least recently used element is head_->next. The most recently used is tail_->prev. This avoids conditional checks for null when inserting or removing at ends.
• detach removes a node from the list in O(1) by rewiring neighbors. No traversal occurs.
• attachToMRU inserts a node just before tail_. That spot is reserved for the most recent element.
• moveToMRU composes those operations to reposition a node after access.
• evictLRU removes the LRU node at head_->next, erases its key from the map, and frees memory.
• get and put both call moveToMRU on successful access or update, which maintains recency.

About time and space.

• Average O(1) time per get and put. The constant-time operations are hash lookups and pointer rewiring. The unordered_map guarantees average constant time.
• Space is O(capacity), dominated by the list nodes and the hash map.

A note on the provided vector-index implementation. You might see alternate code that represents a doubly linked list using a vector of Node* and stores integer indices l and r for neighbors. While the idea is similar, using magic values like 1e9 as sentinels and mixing indices with pointers introduces fragility and can lead to undefined behavior. The pointer-based sentinel approach here is simpler to reason about and less error-prone in C++.

Alternative Approaches

All options trade implementation complexity for performance guarantees. When strict O(1) is required, the hash map plus doubly linked list wins.

• std::list plus unordered_map

  • Keep a std::list<pair<int,int>> for order and values, and an unordered_map<int, list<pair<int,int>>::iterator> for fast lookup.
  • On access, splice the node to the end. On insert, push_back and record the iterator. On full, pop_front and erase. It’s a standard and concise approach in C++.
  • Pick this when you want standard-library containers to manage pointers safely.

• Ordered dictionary in high-level languages

  • Python’s OrderedDict or Java’s LinkedHashMap maintain insertion order and allow moving keys to the end on access. Implementing LRU becomes very short.
  • Great for readability in those ecosystems. Time complexity remains O(1) average.

• Single-linked list plus extra map to previous nodes

  • Maintain a map from key to the previous node to allow O(1) removals from the middle. It’s workable but fussier than a doubly linked list.
  • Consider it only if memory is extremely tight and you want to save one pointer per node, though the additional map entry offsets that gain.

• Balanced BST or heap by timestamp

  • Assign a timestamp to each access and keep a min-heap or tree keyed by timestamp for eviction. This leads to O(log n) operations and complicates updates when timestamps change.
  • Only reasonable if O(log n) is acceptable or you must support extra queries like “k least recently used” efficiently.

• Array or deque with linear search

  • Store pairs in an array and move items on access. Finding items requires O(n) time or a secondary map, and deletions shift elements.
  • Not suitable for the required performance guarantees here.

Pitfalls and Edge Cases

• Forgetting to update recency on get

  • Access must move the node to MRU. Missing this step breaks eviction order.

• Not storing key on the node

  • During eviction, you need the key to erase from the map. If the node doesn’t carry the key, you’ll have to backtrack somehow.

• Handling capacity 1

  • Test sequences like put(1,1), put(2,2), get(1), put(2,3), get(2) to ensure repeated evictions behave as expected.

• Mismanaging pointers at the ends

  • Without sentinels, edge cases multiply. Sentinel head/tail simplify detach and insert. If you must go without them, double-check null handling.

• Re-inserting existing keys as new nodes

  • On put for an existing key, just update and move. Creating a duplicate node for the same key leaves stale entries in the map and violates invariants.

• Erasing the wrong key at eviction

  • Always erase using the key from the node you evict, not a guessed key or external variable.

• Over-reliance on magic numbers or index sentinels

  • Using integers like 1e9 as a sentinel can lead to out-of-bounds access if not handled carefully. Pointer-based sentinels are safer in C++.

• Assuming worst-case O(1) for unordered_map

  • The guarantee is average O(1). Adversarial inputs can degrade performance, but for this problem’s constraints it’s the right choice.

Further Thinking

• Design a Most Frequently Used (MFU) cache

  • Replace recency with frequency. Consider a structure similar to LFU.

• Implement an LFU (Least Frequently Used) cache with O(1) operations

  • Combine a key->node map with frequency buckets. Think of a doubly linked list of lists.

• Cache with TTL expiration

  • Each key has a time-to-live. Maintain a min-heap by expiry for O(log n) expirations plus an LRU list for recency.

• LRU with variable-sized items

  • Capacity is measured in bytes, not count. Evict repeatedly until total size fits. Track size per node.

• Thread-safe LRU cache

  • Introduce locks or lock striping. Keep map and list operations atomic relative to each other.

• Disk-backed LRU

  • On eviction, spill to disk. On miss, fetch from disk into memory. Think of OS page cache behaviors.

• Multi-queue caching

  • Maintain multiple recency queues to improve scan resistance. Items graduate between queues.

• LRU with admission control

  • Not every miss should be admitted. Use TinyLFU-like filters to decide whether to insert.