The Least Recently Used (LRU) Cache is one of the most popular data structure interview questions. It tests your understanding of hash maps, linked lists, and how to combine them to achieve optimal performance.

In this blog, we’ll understand:

  • What an LRU Cache is
  • Why a naive approach fails
  • The optimal data structure
  • Step-by-step implementation in Python
  • Time and space complexity

Problem Statement

Implement an LRUCache class that supports two operations:

  • get(key) → Return the value if the key exists, otherwise return -1.
  • put(key, value) → Insert or update the key-value pair. If the cache exceeds its capacity, remove the least recently used item.

The tricky part?

Both operations must run in O(1) average time.

Example:

capacity = 2

put(1,10)
put(2,20)

Cache:
1 -> 2

get(1)

Cache becomes:
2 -> 1

put(3,30)

Cache exceeded capacity.
Remove key 2.

Final Cache:
1 -> 3

Notice how simply calling get() changes the usage order.

Why a Normal Dictionary Isn’t Enough

A dictionary gives us:

get(key)  -> O(1)
put(key)  -> O(1)

But it doesn’t know which key was least recently used.

Imagine the cache:

1 2 3

After:

get(2)

The order should become

1 3 2

A dictionary alone cannot efficiently reorder elements.

What About a List?

Suppose we store keys in a list.

Whenever we access a key:

get(2)

We need to:

  1. Find it
  2. Remove it
  3. Move it to the end

Finding and removing from a list takes

O(n)

which violates the required complexity.

The Optimal Solution

The solution combines two data structures.

1. Hash Map

Stores

key -> node

This gives constant-time lookup.

2. Doubly Linked List

Maintains the order of usage.

LRU <-------------------------> MRU

left                        right
  • Left = Least Recently Used
  • Right = Most Recently Used

Whenever a key is accessed, we simply move its node to the right end.

Whenever capacity is exceeded, we remove the node next to the left dummy node.

Why Doubly Linked List?

We frequently need to remove nodes from the middle.

With a singly linked list we’d need the previous node.

A doubly linked list already stores:

prev
next

so removal becomes

node.prev.next = node.next
node.next.prev = node.prev

which is O(1).

Using Dummy Nodes

Instead of worrying about empty lists or deleting the first/last node, we create two dummy nodes.

left(dummy) <-> ...cache... <-> right(dummy)

Actual cache nodes always exist between these two.

This greatly simplifies insertion and deletion.

Node Structure

Each node stores:

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

Notice that we store both key and value.

The key is needed when we evict a node so we can remove it from the hash map.

Initializing the Cache

self.cache = {}
self.left = Node(0,0)
self.right = Node(0,0)

self.left.nxt = self.right
self.right.prev = self.left

Initially:

left <-> right

No real nodes exist yet.

Insert Operation

Every newly used node should become the Most Recently Used.

So we always insert just before the right dummy node.

def insert(self, node):
    prev, nxt = self.right.prev, self.right

    prev.nxt = nxt.prev = node
    node.prev = prev
    node.nxt = nxt

Example:

Before:

left <-> A <-> B <-> right

Insert C

After:

left <-> A <-> B <-> C <-> right

Now C is the most recently used.

Remove Operation

Removing a node only requires reconnecting its neighbors.

def remove(self, node):
    prev, nxt = node.prev, node.nxt
    prev.nxt = nxt
    nxt.prev = prev

Example:

Before

A <-> B <-> C

Remove B

After

A <-> C

No traversal required.

get()

If the key exists:

  1. Remove it.
  2. Insert it again at the end.
  3. Return its value.
def get(self, key):
    if key in self.cache:
        self.remove(self.cache[key])
        self.insert(self.cache[key])
        return self.cache[key].val
    return -1

This marks the key as recently used.

put()

If the key already exists:

  • Remove the old node.

Create a fresh node:

newNode = Node(key, value)

Insert it at the end.

Store it in the dictionary.

If capacity is exceeded:

Remove

left.next

because that node is the least recently used.

lru = self.left.nxt
self.remove(lru)
del self.cache[lru.key]

That’s the only eviction we ever perform.

Dry Run

Capacity = 2

put(1,10)

left <-> 1 <-> right

Dictionary

{1}

put(2,20)

left <-> 1 <-> 2 <-> right

2 is the newest.

get(1)

Move 1 to the end.

left <-> 2 <-> 1 <-> right

Now 2 becomes the least recently used.

put(3,30)

Insert:

left <-> 2 <-> 1 <-> 3 <-> right

Capacity exceeded.

Remove the leftmost node.

2

Final cache

left <-> 1 <-> 3 <-> right

Exactly what the problem expects.

Complexity Analysis

Time Complexity

Operation

Complexity

get()

O(1)

put()

O(1)

remove()

O(1)

insert()

O(1)

Every operation involves only dictionary lookups and pointer updates.

Space Complexity

  • Hash map stores every node.
  • Doubly linked list stores every node.

Overall:

O(capacity)

Complete Solution

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


class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}

        # Left = LRU
        # Right = MRU
        self.left, self.right = Node(0, 0), Node(0, 0)
        self.left.nxt = self.right
        self.right.prev = self.left

    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.nxt = nxt.prev = node
        node.prev, node.nxt = prev, nxt

    def remove(self, node):
        prev, nxt = node.prev, node.nxt
        prev.nxt = nxt
        nxt.prev = prev

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

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

        newNode = Node(key, value)
        self.insert(newNode)
        self.cache[key] = newNode

        if len(self.cache) > self.cap:
            lru = self.left.nxt
            self.remove(lru)
            del self.cache[lru.key]

Key Takeaways

  • A hash map alone cannot maintain usage order.
  • A linked list alone cannot provide O(1) lookups.
  • Combining a hash map with a doubly linked list gives the best of both worlds.
  • Dummy nodes eliminate edge cases and make insertion/removal much cleaner.
  • Every operation only performs pointer updates and hash map lookups, giving the required O(1) time complexity.

The LRU Cache is a classic example of combining two data structures to satisfy strict performance constraints. Once you understand this pattern, you’ll recognize similar techniques in problems involving caches, browser history, undo/redo systems, and operating system memory management.