Mastering O(1) LRU Cache: Python Implementation with HashMap & Doubly Linked List

1. Why is caching so important?

In the 1960s computer scientists noticed that faster CPUs did not always make programs run faster because memory access was a bottleneck; the solution was to introduce a cache that keeps recently used data close to the CPU.

The core idea of a cache is to store frequently accessed data near the processor and evict data that hasn't been used recently, which is exactly the principle behind the Least Recently Used (LRU) policy.

2. Interviewer's "soul‑question"

"Suppose you need to implement an LRU cache where both get and put operations run in O(1). How would you write it?"

If you answer simply "store items in a list and look them up with a dictionary," the interviewer will think you haven't mastered the required data‑structure tricks, because removing a middle element from a list costs O(n).

3. Idea breakdown: hash table + doubly linked list

Think of the cache as an ordered shelf:

Each item has a key.

When an item is accessed it is moved to the rightmost (most recent) position.

When the shelf is full, the leftmost (least recent) item is evicted.

This translates to two operations:

Find an item in O(1) → use a hash table (key → node).

Move or delete a node in O(1) → use a doubly linked list. head <-> node1 <-> node2 <-> node3 <-> tail On each access:

Hit: move the node to the tail.

Miss: create a new node and insert it at the tail.

Overflow: delete head.next (the least recently used node).

4. Core code (with comments)

# LRU Cache implementation: hash table + doubly linked list
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.cache = {}  # key -> Node
        self.capacity = capacity
        # pseudo head and tail to simplify edge handling
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next = nxt
        nxt.prev = prev

    def _add(self, node):
        prev = self.tail.prev
        prev.next = node
        node.prev = prev
        node.next = self.tail
        self.tail.prev = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add(node)
        return node.value

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

5. Sample demonstration

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

1
-1
-1
3
4

The output shows that recently used items stay in the cache while the least recently used ones are removed.

6. Time and space complexity

Operation

Time Complexity

Explanation

get()

O(1)

Hash lookup + linked‑list move

put()

O(1)

Hash update + linked‑list insert/delete

Space

O(n)

Hash table + linked‑list nodes

This O(1) LRU solution is what interviewers expect you to be able to code by hand.

7. Why doubly linked list beats singly linked list

With a singly linked list you must traverse from the head to delete a node, which is O(n). A doubly linked list lets you remove or insert a node directly in O(1) because each node knows its predecessor.

8. Common mistakes

Forgetting to move the accessed node to the tail in get(), leading to wrong eviction order.

Not updating predecessor and successor pointers when deleting, causing a broken list.

Mis‑handling edge cases such as capacity = 1 or duplicate keys.

9. One‑liner alternative with Python's built‑in library

Python’s OrderedDict already implements an LRU‑style cache.

from collections import OrderedDict

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

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        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)

Use OrderedDict = "the Pythonic way to solve this algorithm problem".

10. Broader thoughts

LRU is just one cache eviction strategy; others include FIFO, LFU, and ARC, each suited to different workloads. Systems like Redis, MySQL InnoDB buffer pool, and OS page replacement often rely on LRU variants.

"If cache accesses are periodic, is LRU still reasonable?" – a typical follow‑up question in second‑round interviews.

11. Recommended practice problems

Problem ID

Name

Key Concept

146

LRU Cache

Hash + doubly linked list

460

LFU Cache

Frequency counting + two‑level structure

155

Min Stack

Auxiliary stack technique

232

Implement Queue using Stacks

Data‑structure transformation

225

Implement Stack using Queues

Basic logic inversion