AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content
LLD notes

Low-Level Design · Note 4 of 9

Design an LRU Cache

Intermediate · 7 min read · updated 14 November 2026

Quick answer

How do you design an LRU cache with O(1) get and put?

Combine a hash map with a doubly linked list. The list keeps entries in order of use, most recent after a head sentinel and least recent before a tail sentinel; the map takes a key straight to its list node. A get moves the node to the front, a put adds at the front, and a full cache evicts the node before the tail, all in O(1).

On this page
  1. Requirements
  2. Hash map + doubly linked list
  3. Watch it run
  4. Moving a node in O(1)
  5. put on a full cache
  6. Code
  7. Extensions
  8. Interview questions
  9. Common questions

A cache of fixed capacity that, when full, throws out the least recently used entry. It is the most common machine-coding question because it tests data-structure choice and clean classes in under an hour.

Requirements

  • get(key): the value, or a miss. A hit counts as a use.
  • put(key, value): insert or update. An update counts as a use.
  • Fixed capacity; when full, a new key evicts the least recently used one.
  • Both operations O(1). This one line decides the design.
  • Clarify: value type, behaviour on capacity 0, single-threaded or not.

Hash map + doubly linked list

  • Hash map key → node: finds any entry in O(1), but has no order.
  • Doubly linked list: keeps order of use; moving or removing a known node is O(1).
  • Together: the map finds the node, the list reorders it.
  • Sentinels head and tail remove every null check at the ends.
LRU cache classes: a map of nodes plus a doubly linked list

LRUCache is the class callers see: get and put, a fixed capacity, and two members that between them make both operations O(1).

0:01 / 0:12Step 1 of 4
Transcript · 4 steps
OperationMapList
get hitlookupmove node to front
put newinsertadd at front
put when fulldelete evicted keyremove node before tail
put existinglookupupdate value, move to front

Watch it run

Capacity 3, the same ten operations as the code below.

An LRU cache of capacity 3, running ten operations
put 1, 2, 3 · get 1 · put 4 · get 2 · get 3 · put 1 · put 5 · get 4

put(1, A): a new node is linked in right after head and its key goes in the map. 1 of 3 slots used; order 1.

0:01 / 0:31Step 1 of 10
Transcript · 10 steps

Moving a node in O(1)

  • get unlinks the node (2 pointer writes) and adds it after head (4 writes).
  • No walk through the list, whatever its length.
Moving a node to the front in O(1)
order 4, 1, 3; then get(3)

Before get(3) the order is 4, 1, 3, so key 3 is the least recently used. The map hands us node 3 directly: no search through the list.

0:01 / 0:12Step 1 of 4
Transcript · 4 steps

put on a full cache

put(4, D) on a full cache, call by call
capacity 3, order 1, 3, 2

The client calls put(4, D) on a cache holding 1, 3, 2 in that order, with all three slots used.

0:01 / 0:20Step 1 of 8
Transcript · 8 steps
  • Evict before inserting, so the size never exceeds capacity.
  • The evicted node carries its key, which is how the map entry is found.

Code

C++JavaPythonJavaScript
Copy
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

struct Node {
    int key;
    string value;
    Node* prev = nullptr;
    Node* next = nullptr;
    Node(int k, string v) : key(k), value(v) {}
};

class LRUCache {
    int capacity;
    unordered_map<int, Node*> map;
    Node* head = new Node(0, "");  // sentinels: no null checks at the ends
    Node* tail = new Node(0, "");

    void unlink(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; }
    void addFirst(Node* n) {
        n->prev = head; n->next = head->next;
        head->next->prev = n; head->next = n;
    }

public:
    explicit LRUCache(int cap) : capacity(cap) { head->next = tail; tail->prev = head; }

    // Returns false on a miss.
    bool get(int key, string& out) {
        auto it = map.find(key);
        if (it == map.end()) return false;
        unlink(it->second); addFirst(it->second);
        out = it->second->value;
        return true;
    }

    // Returns the evicted key, or -1.
    int put(int key, const string& value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->value = value;
            unlink(it->second); addFirst(it->second);
            return -1;
        }
        int evicted = -1;
        if ((int)map.size() == capacity) {
            Node* last = tail->prev;
            unlink(last); map.erase(last->key);
            evicted = last->key;
            delete last;
        }
        Node* n = new Node(key, value);
        addFirst(n); map[key] = n;
        return evicted;
    }

    void printOrder() {
        cout << "order (most to least recent):";
        for (Node* n = head->next; n != tail; n = n->next) cout << " " << n->key;
        cout << "\n";
    }
};

int main() {
    LRUCache cache(3);
    auto put = [&](int k, string v) {
        int e = cache.put(k, v);
        cout << "put(" << k << ", " << v << ")";
        if (e != -1) cout << " evicts " << e;
        cout << "\n";
    };
    auto get = [&](int k) {
        string v;
        cout << "get(" << k << ") = " << (cache.get(k, v) ? v : "miss") << "\n";
    };
    put(1, "A"); put(2, "B"); put(3, "C"); get(1); put(4, "D");
    get(2); get(3); put(1, "Z"); put(5, "E"); get(4);
    cache.printOrder();
}

Output

put(1, A)
put(2, B)
put(3, C)
get(1) = A
put(4, D) evicts 2
get(2) = miss
get(3) = C
put(1, Z)
put(5, E) evicts 4
get(4) = miss
order (most to least recent): 5 1 3

Extensions

  • Thread safety: even get writes (it reorders), so a read-write lock does not help; use one mutex around both, or shard keys across several locked LRUs.
  • TTL: store an expiry time in each node; get treats an expired node as a miss and removes it. Lazy expiry costs nothing extra; a background sweep frees memory sooner.
  • Eviction policy as a Strategy: put LRU behind an EvictionPolicy interface so LFU or FIFO is a new class (design patterns).
  • Library shortcut: LinkedHashMap (Java) and OrderedDict (Python) already do this; mention them, then build it.

Interview questions

  • Why not a heap of timestamps? Updating a node's position is O(log n), not O(1).
  • Why sentinels? Insert and unlink never meet a null, so there are no edge cases.
  • What breaks with a singly linked list? Unlinking needs the previous node, which costs a walk.
  • How do you test it? Capacity 1, updating an existing key, a miss, and evicting right after a get.

Practise it: LRU Cache.

Next: Design a Parking Lot · Before this: Design Patterns in LLD

Common questions

Why does an LRU cache need a doubly linked list rather than a singly linked one?

Moving or removing a node needs its predecessor. With a prev pointer the node found through the map unlinks itself in O(1); a singly linked list would have to walk from the head to find the predecessor, which makes every get O(n).

Why does each node store the key as well as the value?

On eviction the cache takes the last node off the list and must also delete that entry from the map. The node is all it has at that moment, so the node has to carry its key.

What are sentinel nodes in an LRU cache?

Head and tail are dummy nodes that are never removed. Every real node always has a non-null prev and next, so insert and unlink need no special cases for an empty list or for the first and last entry.

Can I use LinkedHashMap or OrderedDict instead?

In real code, yes: Java's LinkedHashMap with access order and removeEldestEntry, or Python's OrderedDict with move_to_end and popitem(last=False), give an LRU cache in a few lines. In an interview, say so, then build the map and list yourself, because that is what is being tested.

How do you make an LRU cache thread-safe?

The simplest correct answer is one lock around get and put, since even get changes the list. Higher-throughput caches split keys into shards, each with its own lock and its own LRU list, at the cost of eviction being least recent per shard rather than globally.

What is the difference between LRU and LFU?

LRU evicts the entry used longest ago; LFU evicts the entry used least often. LRU adapts quickly when the working set shifts, while LFU protects entries that are popular over time but needs counters and more bookkeeping to stay O(1).

AI InterviewGet started

Design an LRU Cache: LLD With Code in 4 Languages

Design an LRU cache with O(1) get and put: hash map plus doubly linked list, the class diagram, eviction animated, thread safety, TTL and full code.

  • Subject: Low-Level Design
  • Level: Intermediate
  • Reading time: 7 min
  • Updated: 2026-11-14

How do you design an LRU cache with O(1) get and put?

Combine a hash map with a doubly linked list. The list keeps entries in order of use, most recent after a head sentinel and least recent before a tail sentinel; the map takes a key straight to its list node. A get moves the node to the front, a put adds at the front, and a full cache evicts the node before the tail, all in O(1).

A cache of fixed capacity that, when full, throws out the least recently used entry. It is the most common machine-coding question because it tests data-structure choice and clean classes in under an hour.

Requirements

  • get(key): the value, or a miss. A hit counts as a use.
  • put(key, value): insert or update. An update counts as a use.
  • Fixed capacity; when full, a new key evicts the least recently used one.
  • Both operations O(1). This one line decides the design.
  • Clarify: value type, behaviour on capacity 0, single-threaded or not.

Hash map + doubly linked list

  • Hash map key → node: finds any entry in O(1), but has no order.
  • Doubly linked list: keeps order of use; moving or removing a known node is O(1).
  • Together: the map finds the node, the list reorders it.
  • Sentinels head and tail remove every null check at the ends.
LRUCache- capacity: int- map: Map<int, Node>- list: DoublyLinkedList+ get(key): V?+ put(key, value)DoublyLinkedList- head: Node- tail: Node+ addFirst(n)+ remove(n)+ removeLast(): Node1Node+ key: int+ value: V+ prev: Node+ next: Node0..*map valuesprev, next
LRU cache classes: a map of nodes plus a doubly linked list.
  1. LRUCache is the class callers see: get and put, a fixed capacity, and two members that between them make both operations O(1).
  2. The cache owns a DoublyLinkedList that keeps entries in recency order: most recent after head, least recent before tail.
  3. The list is made of Nodes, and the map's values are those same Node objects, so a key lookup lands directly on its place in the list.
  4. Each Node points both ways. With prev and next, a node found through the map unlinks itself in O(1), with no walk from the head.
OperationMapList
get hitlookupmove node to front
put newinsertadd at front
put when fulldelete evicted keyremove node before tail
put existinglookupupdate value, move to front

Watch it run

Capacity 3, the same ten operations as the code below.

get(4) = missmost recent → least recenthead5:E1:Z3:Ctailmap135
An LRU cache of capacity 3, running ten operations. Example: put 1, 2, 3 · get 1 · put 4 · get 2 · get 3 · put 1 · put 5 · get 4
  1. put(1, A): a new node is linked in right after head and its key goes in the map. 1 of 3 slots used; order 1.
  2. put(2, B): a new node is linked in right after head and its key goes in the map. 2 of 3 slots used; order 2, 1.
  3. put(3, C): a new node is linked in right after head and its key goes in the map. 3 of 3 slots used; order 3, 2, 1.
  4. get(1) = A: the map finds node 1 in O(1), and the node is moved to the front because it was just used. Order: 1, 3, 2.
  5. put(4, D) evicts 2: the cache was full, so the node just before tail, key 2, was unlinked and its key removed from the map. Key 4 goes in at the front; order is now 4, 1, 3.
  6. get(2) = miss: key 2 is not in the map, so get returns a miss in O(1) and the order stays 4, 1, 3. A miss never reorders anything.
  7. get(3) = C: the map finds node 3 in O(1), and the node is moved to the front because it was just used. Order: 3, 4, 1.
  8. put(1, Z): key 1 is already cached, so its value is replaced and its node moves to the front. No eviction; order 1, 3, 4.
  9. put(5, E) evicts 4: the cache was full, so the node just before tail, key 4, was unlinked and its key removed from the map. Key 5 goes in at the front; order is now 5, 1, 3.
  10. get(4) = miss: key 4 is not in the map, so get returns a miss in O(1) and the order stays 5, 1, 3. A miss never reorders anything.

Moving a node in O(1)

  • get unlinks the node (2 pointer writes) and adds it after head (4 writes).
  • No walk through the list, whatever its length.
get(3) = Chead3:C4:D1:Atail
Moving a node to the front in O(1). Example: order 4, 1, 3; then get(3)
  1. Before get(3) the order is 4, 1, 3, so key 3 is the least recently used. The map hands us node 3 directly: no search through the list.
  2. Unlink: 1:A.next now points at tail and tail.prev back at 1:A. Two pointer writes, and node 3 is out of the list.
  3. Insert after head: node 3 points to head and 4:D, then head.next and 4:D.prev point at node 3. Four pointer writes.
  4. Done: the order is 3, 4, 1 and get returns C. Six pointer writes in all, the same count for any list length, which is why get is O(1).

put on a full cache

Clientcache: LRUCachemap: HashMaplist: DLLput(4, D)get(4)nullremoveLast()node 2remove(2)addFirst(node 4)put(4, node)
put(4, D) on a full cache, call by call. Example: capacity 3, order 1, 3, 2
  1. The client calls put(4, D) on a cache holding 1, 3, 2 in that order, with all three slots used.
  2. The cache first asks the map whether key 4 is already present, since a present key is updated in place.
  3. The map answers null: 4 is a new key, and the cache is full, so something must be evicted first.
  4. The cache asks the list for its least recently used node, the one just before the tail sentinel.
  5. The list unlinks node 2 and hands it back. The node carries its key, which is why a Node stores key as well as value.
  6. With the key from the node, the cache deletes 2 from the map. Map and list now agree again.
  7. A new node for 4 is linked in right after head, the most recently used position.
  8. Last, the map records key 4 against its node. Every step was O(1), so put is O(1).
  • Evict before inserting, so the size never exceeds capacity.
  • The evicted node carries its key, which is how the map entry is found.

Code

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

struct Node {
    int key;
    string value;
    Node* prev = nullptr;
    Node* next = nullptr;
    Node(int k, string v) : key(k), value(v) {}
};

class LRUCache {
    int capacity;
    unordered_map<int, Node*> map;
    Node* head = new Node(0, "");  // sentinels: no null checks at the ends
    Node* tail = new Node(0, "");

    void unlink(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; }
    void addFirst(Node* n) {
        n->prev = head; n->next = head->next;
        head->next->prev = n; head->next = n;
    }

public:
    explicit LRUCache(int cap) : capacity(cap) { head->next = tail; tail->prev = head; }

    // Returns false on a miss.
    bool get(int key, string& out) {
        auto it = map.find(key);
        if (it == map.end()) return false;
        unlink(it->second); addFirst(it->second);
        out = it->second->value;
        return true;
    }

    // Returns the evicted key, or -1.
    int put(int key, const string& value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->value = value;
            unlink(it->second); addFirst(it->second);
            return -1;
        }
        int evicted = -1;
        if ((int)map.size() == capacity) {
            Node* last = tail->prev;
            unlink(last); map.erase(last->key);
            evicted = last->key;
            delete last;
        }
        Node* n = new Node(key, value);
        addFirst(n); map[key] = n;
        return evicted;
    }

    void printOrder() {
        cout << "order (most to least recent):";
        for (Node* n = head->next; n != tail; n = n->next) cout << " " << n->key;
        cout << "\n";
    }
};

int main() {
    LRUCache cache(3);
    auto put = [&](int k, string v) {
        int e = cache.put(k, v);
        cout << "put(" << k << ", " << v << ")";
        if (e != -1) cout << " evicts " << e;
        cout << "\n";
    };
    auto get = [&](int k) {
        string v;
        cout << "get(" << k << ") = " << (cache.get(k, v) ? v : "miss") << "\n";
    };
    put(1, "A"); put(2, "B"); put(3, "C"); get(1); put(4, "D");
    get(2); get(3); put(1, "Z"); put(5, "E"); get(4);
    cache.printOrder();
}
import java.util.HashMap;
import java.util.Map;

public class Main {
    static class Node {
        int key;
        String value;
        Node prev, next;
        Node(int key, String value) { this.key = key; this.value = value; }
    }
    static class LRUCache {
        private final int capacity;
        private final Map<Integer, Node> map = new HashMap<>();
        private final Node head = new Node(0, null), tail = new Node(0, null); // sentinels

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

        private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }

        private void addFirst(Node n) {
            n.prev = head; n.next = head.next;
            head.next.prev = n; head.next = n;
        }

        /** Returns null on a miss. */
        String get(int key) {
            Node n = map.get(key);
            if (n == null) return null;
            unlink(n); addFirst(n);
            return n.value;
        }

        /** Returns the evicted key, or null. */
        Integer put(int key, String value) {
            Node n = map.get(key);
            if (n != null) {
                n.value = value;
                unlink(n); addFirst(n);
                return null;
            }
            Integer evicted = null;
            if (map.size() == capacity) {
                Node last = tail.prev;
                unlink(last); map.remove(last.key);
                evicted = last.key;
            }
            n = new Node(key, value);
            addFirst(n); map.put(key, n);
            return evicted;
        }

        String order() {
            StringBuilder sb = new StringBuilder("order (most to least recent):");
            for (Node n = head.next; n != tail; n = n.next) sb.append(" ").append(n.key);
            return sb.toString();
        }
    }

    static LRUCache cache = new LRUCache(3);

    static void put(int k, String v) {
        Integer e = cache.put(k, v);
        System.out.println("put(" + k + ", " + v + ")" + (e != null ? " evicts " + e : ""));
    }

    static void get(int k) {
        String v = cache.get(k);
        System.out.println("get(" + k + ") = " + (v != null ? v : "miss"));
    }

    public static void main(String[] args) {
        put(1, "A"); put(2, "B"); put(3, "C"); get(1); put(4, "D");
        get(2); get(3); put(1, "Z"); put(5, "E"); get(4);
        System.out.println(cache.order());
    }
}
class Node:
    def __init__(self, key, value):
        self.key, self.value = key, value
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(0, None), Node(0, None)  # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, n):
        n.prev.next, n.next.prev = n.next, n.prev

    def _add_first(self, n):
        n.prev, n.next = self.head, self.head.next
        self.head.next.prev = n
        self.head.next = n

    def get(self, key):
        """Returns None on a miss."""
        n = self.map.get(key)
        if n is None:
            return None
        self._unlink(n)
        self._add_first(n)
        return n.value

    def put(self, key, value):
        """Returns the evicted key, or None."""
        n = self.map.get(key)
        if n is not None:
            n.value = value
            self._unlink(n)
            self._add_first(n)
            return None
        evicted = None
        if len(self.map) == self.capacity:
            last = self.tail.prev
            self._unlink(last)
            del self.map[last.key]
            evicted = last.key
        n = Node(key, value)
        self._add_first(n)
        self.map[key] = n
        return evicted

    def order(self):
        keys, n = [], self.head.next
        while n is not self.tail:
            keys.append(str(n.key))
            n = n.next
        return "order (most to least recent): " + " ".join(keys)


cache = LRUCache(3)


def put(k, v):
    e = cache.put(k, v)
    print(f"put({k}, {v})" + (f" evicts {e}" if e is not None else ""))


def get(k):
    v = cache.get(k)
    print(f"get({k}) = {v if v is not None else 'miss'}")


put(1, "A"); put(2, "B"); put(3, "C"); get(1); put(4, "D")
get(2); get(3); put(1, "Z"); put(5, "E"); get(4)
print(cache.order())
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new Node(0, null); // sentinels
    this.tail = new Node(0, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  unlink(n) {
    n.prev.next = n.next; n.next.prev = n.prev;
  }

  addFirst(n) {
    n.prev = this.head;
    n.next = this.head.next;
    this.head.next.prev = n;
    this.head.next = n;
  }

  /** Returns null on a miss. */
  get(key) {
    const n = this.map.get(key);
    if (!n) return null;
    this.unlink(n);
    this.addFirst(n);
    return n.value;
  }

  /** Returns the evicted key, or null. */
  put(key, value) {
    let n = this.map.get(key);
    if (n) {
      n.value = value;
      this.unlink(n);
      this.addFirst(n);
      return null;
    }
    let evicted = null;
    if (this.map.size === this.capacity) {
      const last = this.tail.prev;
      this.unlink(last);
      this.map.delete(last.key);
      evicted = last.key;
    }
    n = new Node(key, value);
    this.addFirst(n);
    this.map.set(key, n);
    return evicted;
  }

  order() {
    const keys = [];
    for (let n = this.head.next; n !== this.tail; n = n.next) keys.push(n.key);
    return "order (most to least recent): " + keys.join(" ");
  }
}

const cache = new LRUCache(3);
const put = (k, v) => {
  const e = cache.put(k, v);
  console.log(`put(${k}, ${v})` + (e !== null ? ` evicts ${e}` : ""));
};
const get = (k) => {
  const v = cache.get(k);
  console.log(`get(${k}) = ${v !== null ? v : "miss"}`);
};

put(1, "A"); put(2, "B"); put(3, "C"); get(1); put(4, "D");
get(2); get(3); put(1, "Z"); put(5, "E"); get(4);
console.log(cache.order());
put(1, A)
put(2, B)
put(3, C)
get(1) = A
put(4, D) evicts 2
get(2) = miss
get(3) = C
put(1, Z)
put(5, E) evicts 4
get(4) = miss
order (most to least recent): 5 1 3

Extensions

  • Thread safety: even get writes (it reorders), so a read-write lock does not help; use one mutex around both, or shard keys across several locked LRUs.
  • TTL: store an expiry time in each node; get treats an expired node as a miss and removes it. Lazy expiry costs nothing extra; a background sweep frees memory sooner.
  • Eviction policy as a Strategy: put LRU behind an EvictionPolicy interface so LFU or FIFO is a new class (design patterns).
  • Library shortcut: LinkedHashMap (Java) and OrderedDict (Python) already do this; mention them, then build it.

Interview questions

  • Why not a heap of timestamps? Updating a node's position is O(log n), not O(1).
  • Why sentinels? Insert and unlink never meet a null, so there are no edge cases.
  • What breaks with a singly linked list? Unlinking needs the previous node, which costs a walk.
  • How do you test it? Capacity 1, updating an existing key, a miss, and evicting right after a get.

Practise it: LRU Cache.

Next: Design a Parking Lot · Before this: Design Patterns in LLD

Common questions

Why does an LRU cache need a doubly linked list rather than a singly linked one?

Moving or removing a node needs its predecessor. With a prev pointer the node found through the map unlinks itself in O(1); a singly linked list would have to walk from the head to find the predecessor, which makes every get O(n).

Why does each node store the key as well as the value?

On eviction the cache takes the last node off the list and must also delete that entry from the map. The node is all it has at that moment, so the node has to carry its key.

What are sentinel nodes in an LRU cache?

Head and tail are dummy nodes that are never removed. Every real node always has a non-null prev and next, so insert and unlink need no special cases for an empty list or for the first and last entry.

Can I use LinkedHashMap or OrderedDict instead?

In real code, yes: Java's LinkedHashMap with access order and removeEldestEntry, or Python's OrderedDict with move_to_end and popitem(last=False), give an LRU cache in a few lines. In an interview, say so, then build the map and list yourself, because that is what is being tested.

How do you make an LRU cache thread-safe?

The simplest correct answer is one lock around get and put, since even get changes the list. Higher-throughput caches split keys into shards, each with its own lock and its own LRU list, at the cost of eviction being least recent per shard rather than globally.

What is the difference between LRU and LFU?

LRU evicts the entry used longest ago; LFU evicts the entry used least often. LRU adapts quickly when the working set shifts, while LFU protects entries that are popular over time but needs counters and more bookkeeping to stay O(1).

← Design Patterns in LLD · Design a Parking Lot →