LRU Cache Design: HashMap + Doubly Linked List

The LRU Cache is one of the most frequently asked system design and coding interview questions. It tests your ability to combine two data structures for optimal performance. Let’s understand why it works and build one from scratch.

What is an LRU Cache?

An LRU (Least Recently Used) Cache is a fixed-size key-value store that evicts the least recently accessed item when it reaches capacity.

Rules:

1. get(key) — Return the value if the key exists, and mark it as recently used. Return -1 if not found.
2. put(key, value) — Insert or update the key-value pair. If the cache is full, evict the least recently used item first.
3. Both operations must be O(1) time.

Why HashMap + Doubly Linked List?

No single data structure gives us O(1) for all operations:

Data Structure	Lookup	Insert/Delete	Track Order
Array	O(1) index, O(n) value	O(n)	Need shifting
HashMap	O(1)	O(1)	No order
Linked List	O(n)	O(1) with ref	Maintains order
HashMap + DLL	O(1)	O(1)	O(1)

The combination works because:

• HashMap gives O(1) lookup by key, pointing to the DLL node
• Doubly Linked List maintains access order — most recent at head, least recent at tail
• DLL nodes can be removed in O(1) when you have a direct reference (via the HashMap)

Implementation from Scratch

Step 1: The DLL Node

class DLLNode:
    """Node for the doubly linked list."""
    __slots__ = ['key', 'val', 'prev', 'next']

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

Using __slots__ reduces memory overhead per node.

Step 2: The LRU Cache

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

        # Sentinel nodes eliminate edge cases
        self.head = DLLNode()  # Dummy head (most recent side)
        self.tail = DLLNode()  # Dummy tail (least recent side)
        self.head.next = self.tail
        self.tail.prev = self.head

    # ---------- Internal DLL operations ----------

    def _add_to_front(self, node):
        """Add node right after head (most recent position)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """Remove a node from the DLL. O(1)."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_front(self, node):
        """Mark node as most recently used."""
        self._remove_node(node)
        self._add_to_front(node)

    def _evict_lru(self):
        """Remove the least recently used node (just before tail)."""
        lru_node = self.tail.prev
        self._remove_node(lru_node)
        del self.cache[lru_node.key]

    # ---------- Public API ----------

    def get(self, key: int) -> int:
        """
        Get value by key. Returns -1 if not found.
        Time: O(1)
        """
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self._move_to_front(node)  # Mark as recently used
        return node.val

    def put(self, key: int, value: int) -> None:
        """
        Insert or update a key-value pair.
        Evicts LRU item if at capacity.
        Time: O(1)
        """
        if key in self.cache:
            # Update existing
            node = self.cache[key]
            node.val = value
            self._move_to_front(node)
        else:
            # Insert new
            if len(self.cache) >= self.capacity:
                self._evict_lru()

            new_node = DLLNode(key, value)
            self.cache[key] = new_node
            self._add_to_front(new_node)

    def __repr__(self):
        items = []
        node = self.head.next
        while node is not self.tail:
            items.append(f"{node.key}:{node.val}")
            node = node.next
        return f"LRU([{', '.join(items)}])"

Step 3: Testing

cache = LRUCache(3)

cache.put(1, 'A')
cache.put(2, 'B')
cache.put(3, 'C')
print(cache)  # LRU([3:C, 2:B, 1:A])

cache.get(1)  # Access key 1 — moves to front
print(cache)  # LRU([1:A, 3:C, 2:B])

cache.put(4, 'D')  # Capacity full — evicts key 2 (LRU)
print(cache)  # LRU([4:D, 1:A, 3:C])

print(cache.get(2))  # -1 (evicted)
print(cache.get(3))  # C (moves to front)
print(cache)  # LRU([3:C, 4:D, 1:A])

cache.put(5, 'E')  # Evicts key 1
print(cache)  # LRU([5:E, 3:C, 4:D])

Why sentinels?

Without sentinel nodes, _add_to_front and _remove_node need to check if the node is the head or tail:

# WITHOUT sentinels — many edge cases:
def _remove_node(self, node):
    if node.prev:
        node.prev.next = node.next
    else:
        self.head = node.next  # Was the head

    if node.next:
        node.next.prev = node.prev
    else:
        self.tail = node.prev  # Was the tail

# WITH sentinels — clean, no edge cases:
def _remove_node(self, node):
    node.prev.next = node.next
    node.next.prev = node.prev

The OrderedDict Shortcut

Python’s collections.OrderedDict maintains insertion order and supports move_to_end, making LRU trivial:

from collections import OrderedDict

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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # Mark as recently used
        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)  # Remove oldest (first)

This is acceptable in Python interviews, but interviewers usually want the full HashMap + DLL implementation to test your understanding.

Thread-Safe LRU Cache

In production, caches are accessed by multiple threads:

import threading

class ThreadSafeLRUCache:
    def __init__(self, capacity):
        self.cache = LRUCache(capacity)
        self.lock = threading.Lock()

    def get(self, key):
        with self.lock:
            return self.cache.get(key)

    def put(self, key, value):
        with self.lock:
            self.cache.put(key, value)

For high-concurrency systems, consider using a sharded cache (multiple LRU caches, one per shard) to reduce lock contention.

LRU vs LFU Cache

Feature	LRU	LFU
Eviction criteria	Least recently used	Least frequently used
Tracks	Access order	Access count
Data structure	HashMap + DLL	HashMap + frequency buckets
Good for	Temporal locality	Long-term popularity
Drawback	One-time accesses stay	Old popular items linger

# LFU evicts based on access count
# If key A was accessed 100 times an hour ago,
# and key B was accessed once just now:
# LRU evicts A (less recent)
# LFU evicts B (less frequent)

Real-World Usage

Redis

Redis uses an approximated LRU algorithm called allkeys-lru. Instead of maintaining an exact DLL, it samples random keys and evicts the one with the oldest access time. This is more memory-efficient for millions of keys.

Browser Cache

Browsers cache HTTP responses (HTML, CSS, JS, images). When the cache is full, the least recently accessed resources are evicted. This is why revisiting a page is fast but visiting many new sites slows things down.

Operating System Page Replacement

When RAM is full and a new page is needed, the OS evicts the least recently used page to disk. The LRU policy approximates optimal page replacement for most workloads.

CPU Cache

L1/L2/L3 CPU caches use LRU (or pseudo-LRU) to decide which cache line to evict. This is critical for performance — a cache miss to main memory is ~100x slower.

Complexity Analysis

Operation	Time	Space
get(key)	O(1)	-
put(key, value)	O(1)	-
Space (total)	-	O(capacity)

Why O(1)?

• HashMap lookup: O(1) average
• DLL add/remove/move: O(1) — just pointer changes
• No operation touches more than a constant number of nodes

LeetCode-Ready Implementation

Here is the exact implementation that passes LeetCode 146:

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.head = DLLNode()
        self.tail = DLLNode()
        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 _insert(self, 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]
            self._remove(node)
            self._insert(node)
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])

        node = DLLNode(key, value)
        self.cache[key] = node
        self._insert(node)

        if len(self.cache) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

Practice Problems

1. LeetCode 146 — LRU Cache: The classic problem (Medium)
2. LeetCode 460 — LFU Cache: Least Frequently Used variant (Hard)
3. LeetCode 1171 — Remove Zero Sum Consecutive Nodes: Uses OrderedDict (Medium)
4. LeetCode 432 — All O’one Data Structure: HashMap + DLL for min/max (Hard)
5. Design a TTL Cache: LRU with time-to-live expiration (System Design)

Key Takeaways

• An LRU Cache combines a HashMap (O(1) lookup) with a Doubly Linked List (O(1) ordered insertion/removal).
• Sentinel nodes eliminate all edge cases in the DLL operations.
• Python’s OrderedDict provides a shortcut, but interviewers expect the full implementation.
• LRU is the most common eviction policy in practice — used in Redis, browsers, OS page replacement, and CPU caches.
• The key insight: storing key in the DLL node lets you delete from the HashMap when evicting.