LRU Cache Explained: HashMap + Doubly Linked List (Python Guide)

If there is one data structure and algorithm (DSA) question that is practically guaranteed to show up in Big Tech interviews, it is the LRU Cache (Least Recently Used). It perfectly tests your understanding of HashMaps, Doubly Linked Lists, pointer manipulation, and object-oriented design.

But beyond passing interviews (like LRU Cache LeetCode 146), LRU Caches are everywhere in real system design cache architecture. Redis uses an approximation of the LRU cache eviction policy to evict keys. Operating systems use it to decide which memory pages to swap to disk. Browsers use it to decide which cached assets to clear.

Here is the complete visual and code guide to mastering the LRU Cache in Python.

What is an LRU Cache?

A cache is a temporary storage area to make future requests faster. But a cache has a limited size (capacity). When it gets full, you must evict something.

LRU Eviction Policy: When the cache is full, find the item that was accessed the longest time ago and throw it away.

If you think about your own browser history: if you only had room for 3 tabs, and you visited Google, then YouTube, then GitHub, and then went back to Google, your tabs would be [GitHub, Google] (YouTube gets evicted because it was the least recently used).

Why two data structures?

To build an LRU Cache, we need two operations to run in $O(1)$ time: 1. Look up an item (Fast reads). 2. Update the "recently used" order (Fast insertions/deletions from the middle of the order).

If we use only an Array, lookups are $O(1)$, but updating the order is $O(N)$ because we have to shift elements. If we use only a Singly Linked List, updating the order is $O(1)$, but lookups are $O(N)$ because we have to traverse the list.

The Golden Combo: A HashMap + a Doubly Linked List. * The HashMap stores key -> Node mappings for instant $O(1)$ lookups. * The Doubly Linked List maintains the chronological order of access, allowing $O(1)$ insertions and removals.

💡 The "Why Doubly?" Trap: A singly linked list makes removing an arbitrary node $O(N)$, because you first need to find its predecessor to update the next pointer. A doubly linked list stores both prev and next, allowing removal in $O(1)$ since the node already knows its predecessor.

The Architecture

graph TD
    subgraph HashMap
        H1[key1] --> N1
        H2[key2] --> N2
        H3[key3] --> N3
    end

    subgraph Doubly Linked List
        Head[Head Dummy] <--> N1[Node: key1] <--> N2[Node: key2] <--> N3[Node: key3] <--> Tail[Tail Dummy]
    end

    style Head fill:#f9f,stroke:#333
    style Tail fill:#f9f,stroke:#333

The Rules: 1. The Head of the list represents the Most Recently Used (MRU) item. 2. The Tail of the list represents the Least Recently Used (LRU) item. 3. Every time we get or put an item, we move its node to the Head. 4. If we exceed capacity, we remove the node right before the Tail.

💡 The Pro-Tip that saves 10 minutes in an interview: Always use Dummy Head and Tail nodes (also known as sentinel nodes). If you don't use dummies, you will spend the entire interview writing if node.prev is not None: and if node.next is not None: edge cases. Dummies create a stable boundary.

Memory Overhead

Every cache entry stores the key, the value, a prev pointer, and a next pointer. This extra memory overhead is the engineering tradeoff for achieving $O(1)$ operations.

The Implementation (Python)

Here is the clean, production-ready LRU Cache Python implementation.

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # Maps key -> Node

        # Dummy head and tail (sentinel nodes) to avoid edge cases
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    # Helper 1: Remove a node from the list
    def _remove(self, node: Node):
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

    # Helper 2: Add a node right after the Head (make it MRU)
    def _add_to_head(self, node: Node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # Move to front (it's now the most recently used)
            self._remove(node)
            self._add_to_head(node)
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update value and move to front
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_head(node)
        else:
            # Create new node
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)

            # Check capacity
            if len(self.cache) > self.capacity:
                # Remove the LRU item (right before the dummy tail)
                lru_node = self.tail.prev
                self._remove(lru_node)
                del self.cache[lru_node.key] # Don't forget to delete from HashMap!

Walkthrough: Visualizing put and get

Let's trace an execution with a capacity of 2.

1. put(1, "Apple")
   • Cache is empty. Node (1, Apple) is created.
   • Added to head. List: Head <-> (1, Apple) <-> Tail
2. put(2, "Banana")
   • Cache size is 1. Node (2, Banana) is created.
   • Added to head. List: Head <-> (2, Banana) <-> (1, Apple) <-> Tail
3. get(1)
   • Key 1 is in HashMap. Value is "Apple".
   • Remove (1, Apple) from its position. Add to head.
   • List: Head <-> (1, Apple) <-> (2, Banana) <-> Tail
   • Returns "Apple".
4. put(3, "Cherry") (Cache is now full at capacity 2)
   • Key 3 is not in cache. Create Node (3, Cherry).
   • Add to head. List: Head <-> (3, Cherry) <-> (1, Apple) <-> (2, Banana) <-> Tail
   • Capacity exceeded (size is 3).
   • Evict tail.prev which is (2, Banana). Remove from list and HashMap.
   • Final List: Head <-> (3, Cherry) <-> (1, Apple) <-> Tail

Why Not Use a Heap?

A common question in system design cache interviews is: "Why not use a Heap (Priority Queue) with timestamps?"

While a Min-Heap based on last_accessed_time would give you $O(\log n)$ insertions, deletions, and lookups, the fundamental requirement of an LRU cache is $O(1)$ speed. In high-throughput systems like Redis or CPU caches, $O(\log n)$ is simply too slow. The HashMap + Doubly Linked List combination guarantees constant time.

Common Interview Mistakes

When implementing this in an interview, watch out for these silent bugs:

• ❌ Forgetting to remove from the HashMap: You remove the node from the Linked List, but you forget to del self.cache[lru_node.key]. Now your HashMap and List are out of sync.
• ❌ Updating the list but not the map: You move a node to the head, but forget to update its value in the HashMap if it was an update put.
• ❌ Using a singly linked list: You realize halfway through that you can't update the prev node's next pointer in $O(1)$.
• ❌ Forgetting to move the node after get: The cache returns the right value, but doesn't mark the item as recently used, leading to wrong evictions later.
• ❌ Not updating an existing key: put(1, "NewApple") adds a second Node 1 instead of updating the existing one.
• ❌ Forgetting capacity == 1: Your code crashes because tail.prev is also head.next, and pointer swaps get messy (Dummy nodes fix this!).

The Production Python Solution

If an interviewer asks: "How would you do this in production Python?" you should mention collections.OrderedDict.

Since Python 3.7, standard dictionaries preserve insertion order, but OrderedDict still provides convenient methods such as move_to_end() and popitem(last=False) that make implementing an LRU cache straightforward.

Here is the 5-line production implementation:

from collections import OrderedDict

class LRUCacheProd:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        self.cache.move_to_end(key)  # Move to MRU position
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False) # Pop the LRU item (first item)

Note on functools.lru_cache: If you are caching function results rather than implementing a cache data structure from scratch, Python provides @functools.lru_cache. This decorator handles the LRU logic for you automatically and is highly optimized at the C level.

Real-World Uses of LRU Caches

LRU is the default eviction policy for countless systems you interact with daily:

• Browser Cache: Deciding which images or scripts to purge from memory.
• CDN Edge Cache: Deciding which cached web pages to drop when the edge node's disk is full.
• Database Buffer Pool: Databases like PostgreSQL and MySQL use LRU (or variants like Clock/LRU-K) to decide which memory pages to flush to disk.
• Redis: Uses an approximate LRU algorithm to evict keys when maxmemory is reached.
• CPU Cache Replacement: Hardware-level caches use approximate LRU to decide which cache lines to evict.
• API Response Cache & ORM Query Cache: Frameworks cache recent query results to avoid hitting the database repeatedly.

Complexity Analysis

• Time Complexity: $O(1)$ for both get and put. HashMap lookups are $O(1)$, and linked list pointer updates are $O(1)$.
• Space Complexity: $O(capacity)$ since the HashMap and Linked List will only ever contain up to capacity number of elements.