Lesson 9 of 12 Case Studies

Design an LRU Cache in Python and Java

Design an LRU cache with O(1) get and put using a hash map and doubly linked list, with runnable Python and Java code, thread safety and extensions.

40-50 min intermediate 0/12 lessons done
Course contents Lesson 9 of 12 · 0 done
On this page (9 sections)
  1. What you will learn
  2. The problem
  3. Python
  4. Java
  5. Shortcuts and when to use them
  6. Follow-up questions
  7. Key takeaways
  8. Exercises
  9. Quiz

What you will learn

  • Why an LRU cache needs two data structures.
  • A clean O(1) implementation with sentinel nodes, in Python and Java.
  • How to make it thread-safe, and common follow-up questions.

The problem

A cache with fixed capacity. get(key) returns the value (or a miss) and marks the key as recently used. put(key, value) inserts or updates; if the cache is full, it evicts the least recently used key. Both must be O(1).

  • A hash map gives O(1) lookup but no order.
  • A list gives order, but moving an item to the front is O(n) unless you can reach its neighbours directly.

Solution: a hash map from key to node, plus a doubly linked list ordered from most to least recently used. The map finds the node; the links let us unlink and move it in O(1).

head <-> [4] <-> [3] <-> tail
          MRU           LRU
map = {4: node4, 3: node3}

Sentinel head and tail nodes remove all the “is the list empty?” special cases.

Python

"""LRU cache with O(1) get and put: hash map + doubly linked list."""


class Node:
    __slots__ = ("key", "value", "prev", "next")

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


class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.map: dict = {}  # key -> Node
        self.head, self.tail = Node(), Node()  # sentinels: head.next is most recent
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node: Node):
        node.prev.next, node.next.prev = node.next, node.prev

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

    def get(self, key, default=-1):
        node = self.map.get(key)
        if node is None:
            return default
        self._unlink(node)  # mark as most recently used
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.tail.prev  # least recently used sits just before the tail
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

    def keys_mru_to_lru(self):
        out, n = [], self.head.next
        while n is not self.tail:
            out.append(n.key)
            n = n.next
        return out


if __name__ == "__main__":
    c = LRUCache(2)
    c.put(1, "one")
    c.put(2, "two")
    print(c.get(1))           # one  (1 becomes most recent)
    c.put(3, "three")         # evicts 2
    print(c.get(2))           # -1
    c.put(4, "four")          # evicts 1
    print(c.get(1), c.get(3), c.get(4))  # -1 three four
    print("order:", c.keys_mru_to_lru())

Output:

one
-1
-1 three four
order: [4, 3]

Java

import java.util.HashMap;
import java.util.Map;

/** LRU cache with O(1) get/put, generic over key and value. */
public class LRUCache<K, V> {
    private static final class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null); // most recent after head
    private final Node<K, V> tail = new Node<>(null, null); // least recent before tail

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

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

    public synchronized void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value;
            unlink(node);
            pushFront(node);
            return;
        }
        if (map.size() == capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);
        }
        node = new Node<>(key, value);
        map.put(key, node);
        pushFront(node);
    }

    private void unlink(Node<K, V> n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void pushFront(Node<K, V> n) {
        n.prev = head;
        n.next = head.next;
        head.next.prev = n;
        head.next = n;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> c = new LRUCache<>(2);
        c.put(1, "one");
        c.put(2, "two");
        System.out.println(c.get(1));                 // one
        c.put(3, "three");                            // evicts 2
        System.out.println(c.get(2));                 // null
        c.put(4, "four");                             // evicts 1
        System.out.println(c.get(1) + " " + c.get(3) + " " + c.get(4)); // null three four
    }
}

Output (compiled with javac and run with java LRUCache):

one
null
null three four

synchronized makes each method atomic. Note that even get modifies the list, so a read/write lock wouldn’t help: every operation is a write to the ordering.

Shortcuts and when to use them

  • Python: collections.OrderedDict with move_to_end(key) and popitem(last=False); functools.lru_cache for memoising functions.
  • Java: LinkedHashMap with accessOrder=true and an overridden removeEldestEntry.

In interviews, say you know the shortcut, then implement the linked list unless told otherwise.

Follow-up questions

  • Thread safety at high concurrency: one lock serialises everything. Shard the cache into N segments by key hash, each with its own lock and capacity (approximate LRU, much higher throughput).
  • TTL: store an expiry per node; treat expired entries as misses on get, and optionally sweep in the background.
  • LFU instead of LRU: evict the least frequently used key; an O(1) design keeps a map of frequency → doubly linked list plus a min_freq pointer.
  • Distributed cache: that becomes an HLD question; see caching in the System Design course. Redis itself offers approximate LRU eviction policies.

This problem is also LeetCode 146 and appears on the LeetCode 150 sheet.

Key takeaways

  • LRU = hash map (find node) + doubly linked list (order); both operations are O(1).
  • Sentinel nodes remove empty-list edge cases.
  • Every get changes the order, so the whole operation needs the lock; shard for throughput.
  • Know the library shortcuts but be ready to build it from scratch.

Exercises

  1. Add ttl_seconds to put and make expired keys behave like misses.
  2. Implement a ShardedLRUCache with 8 segments, each guarded by its own lock.
  3. Implement an LFU cache with O(1) operations.

Quiz

  1. Why must the linked list be doubly linked?
  2. What do sentinel nodes save you from?
  3. Why doesn’t a read/write lock help an LRU cache?
Show answers
  1. To unlink a node in O(1) you need its previous node; a singly linked list would require an O(n) search.
  2. Special cases for an empty list and for inserting or removing at the ends; every real node always has non-null neighbours.
  3. get also updates recency order, so every operation mutates shared state and needs exclusive access.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).