LRU Cache

Table of Contents +

LRU Cache is a favorite interview question. It looks like a storage problem. But it is really a data structure design test. The interviewer wants to see if you can make both reading and writing fast at the same time. That is the real challenge here.

🎯 The Problem

You build a cache that throws out whatever was touched longest ago. Here are the rules.

A cache is a small fast store that keeps recent answers so you do not compute them again.
A cache has limited room. When it fills up, you must throw something out.
LRU stands for Least Recently Used.
When the cache is full, remove the item nobody has touched for the longest time.
get(key) returns the value if the key is there, else -1.
put(key, value) saves a key and value.
Both must run in O(1) time, no matter how big the cache is.

Capacity = 2

put(1, 1)      cache: {1=1}
put(2, 2)      cache: {1=1, 2=2}
get(1)  -> 1   cache: {2=2, 1=1}   (1 is now most recent)
put(3, 3)      evicts key 2        cache: {1=1, 3=3}
get(2)  -> -1  (2 was evicted)
put(4, 4)      evicts key 1        cache: {3=3, 4=4}
get(1)  -> -1
get(3)  -> 3
get(4)  -> 4

Every get and every put counts as using a key. So a used key becomes the most recent. The item that stays untouched the longest is the one we drop.

Here is the order of operations and what comes out of each call.

🐢 Approach 1: One Ordered List (Brute Force)

The idea in one line: keep items in a plain list ordered by use, front is newest, back is oldest.

The idea:

The front holds the most recently used item.
The back holds the least recently used item.
To read a key, scan the list to find it, then move it to the front.
When full, drop the item at the back.

Why it is weak:

Finding a key means walking the whole list.
That is O(n) time per operation, where n is the number of items.
The interviewer asked for O(1). So this is too slow.

Here is the ordered-list code:

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}
        self.order = []

    def get(self, key):
        if key not in self.data:
            return -1
        self.order.remove(key)
        self.order.append(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.order.remove(key)
        elif len(self.order) == self.capacity:
            old = self.order.pop(0)
            del self.data[old]
        self.data[key] = value
        self.order.append(key)

⚡ Approach 2: Hash Map Plus Doubly Linked List (Best)

The idea in one line: pair a map for instant lookup with a doubly linked list for instant reordering.

The idea:

A doubly linked list is a chain where each node points to the next and back to the previous.
Keep the most recent node near the head and the least recent near the tail.
A hash map points each key straight to its node, so you never scan.

How it works:

For get, the map finds the node in O(1). Move it to the head to mark it most recent.
For put, add a new node at the head.
If over capacity, drop the node at the tail and remove its key from the map.
The tail is always the least recently used item.
Use two guard nodes, a head guard and a tail guard, so you never check for empty pointers.

Why it is fast:

The map makes lookup instant.
The doubly linked list makes moving a node instant.
So both get and put run in O(1).

This is the structure. The map points into the list, and the list keeps the recent-to-old order.

Steps to Solve

Build a doubly linked list with a head guard and a tail guard node.
Keep a hash map from each key to its node in the list.
For get(key), if the key is not in the map return -1. Otherwise unhook the node, move it right after the head, and return its value.
For put(key, value), if the key exists update its value and move its node to the front.
If the key is new, create a node, add it right after the head, and store it in the map.
If the size is now over capacity, remove the node right before the tail and delete its key from the map.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a dictionary for lookups and a doubly linked list with guard nodes for the recent-to-old order.

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


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                 # key -> node
        self.head = Node(0, 0)        # guard at the front
        self.tail = Node(0, 0)        # guard at the back
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):          # unhook a node
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):       # place right after head
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)            # touched, move to front
        self._add_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            node = self.map[key]
            node.value = value
            self._remove(node)
            self._add_front(node)
            return
        fresh = Node(key, value)
        self._add_front(fresh)
        self.map[key] = fresh
        if len(self.map) > self.capacity:   # drop the oldest
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]


cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))   # 1
cache.put(3, 3)       # evicts key 2
print(cache.get(2))   # -1
cache.put(4, 4)       # evicts key 1
print(cache.get(1))   # -1
print(cache.get(3))   # 3
print(cache.get(4))   # 4

The output of the above code will be:

Let us walk through the Python version line by line, because the design is the whole point here.

The Node class holds the key, the value, and two pointers prev and next. We store the key inside the node too. That matters because when we evict the tail node we need its key to delete it from the map.

In __init__ we create two guard nodes, head and tail, and link them to each other. A guard node is a fake node that always sits at the end so the real list is never empty. This removes a lot of edge-case checks. Real items always go between these two guards.

_remove(node) takes a node out of the chain. It points the previous node’s next to skip over this node, and the next node’s prev back to skip it too. The node is now unhooked. This is O(1) because we touch only the two neighbors.

_add_front(node) inserts a node right after the head guard. The front is the most recently used spot. So anything we touch lands here.

In get, if the key is missing we return -1. Otherwise we grab the node from the map, unhook it, and re-add it at the front. That marks it as just used.

In put, if the key already exists we update its value and move it to the front. If it is new we make a node, add it to the front, and record it in the map. Then comes the eviction check. If the map is now larger than the capacity, we look at self.tail.prev, which is the least recently used node. We unhook it and delete its key from the map.

⏱️ Time and Space Complexity

The simple single-list version is slow because finding a key means scanning the list, which is O(n). The optimal design pairs a hash map with a doubly linked list. The map makes lookups instant. The doubly linked list makes moving a node instant. Together they give O(1) for both get and put. The cost is extra memory for the map and the node pointers.

Approach	Time Complexity	Space Complexity
Single ordered list (scan to find)	O(n) per operation	O(n)
Hash map + doubly linked list	O(1) per operation	O(n)

Tip

The key insight to say out loud in an interview is that no single structure gives you both fast lookup and fast reordering. The hash map gives fast lookup. The doubly linked list gives fast reordering. You combine them.

🧩 Key Takeaways

✅ LRU drops the item nobody has touched for the longest time when the cache is full.
✅ A hash map alone cannot track order, and a list alone cannot find keys fast. So combine both.
✅ The doubly linked list keeps items from most recent at the head to least recent at the tail.
✅ Guard nodes at the head and tail remove almost all the edge cases.
✅ Both get and put run in O(1) time, which is exactly what the interviewer asks for.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

LFU Cache
Reverse a Linked List

Previous Find the Duplicate Number Next Merge K Sorted Lists

LRU Cache

Follow Us

Follow Us