NOA Labs
Caching Strategies Lesson 5 of 6 ⏱️ 4 min read

Build an LRU Cache from Scratch

Implement a least-recently-used cache with O(1) get and put using a hash map and doubly linked list — a classic interview question.

Updated Oct 30, 2026

The problem

Design a cache with a fixed capacity that supports:

  • get(key) — return the value, or -1 if missing.
  • put(key, value) — insert or update; if the cache is full, evict the least recently used item.

Both operations must run in O(1) time. This is one of the most frequently asked coding interview questions, and the same design is used inside real caches.

The key insight

We need two things at once:

  1. Fast lookup by key → a hash map.
  2. Fast "move to most recent" and "remove least recent" → a doubly linked list ordered by recency.

The hash map stores key → node, so we can find any node in O(1) and unlink it from the list in O(1).

Plaintext
head ⇄ [most recent] ⇄ ... ⇄ [least recent] ⇄ tail
         ↑ insert here                ↑ evict from here

Sentinel head and tail nodes remove all the "is the list empty?" edge cases.

Implementation from scratch

Python
class Node:
    __slots__ = ("key", "value", "prev", "next")

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


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map: dict[int, Node] = {}
        self.head, self.tail = Node(), Node()      # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node: Node) -> None:
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_to_front(self, node: Node) -> None:
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)                 # mark as most recently used
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_to_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev           # least recently used
            self._remove(lru)
            del self.map[lru.key]


cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1   (order now: 1, 2)
cache.put(3, 3)        # evicts key 2, the least recently used
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

Output:

Plaintext
1
-1
-1
3
4

Complexity

Operation Time Why
get O(1) Hash lookup + constant pointer changes
put O(1) Hash insert + constant pointer changes + possible O(1) eviction
Space O(capacity) One node and one map entry per item

The Pythonic version

In real Python code, collections.OrderedDict already keeps insertion order and can move keys to the end in O(1):

Python
from collections import OrderedDict

class LRUCacheOD:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)         # most recent at the end
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)  # remove least recent from the front

And for caching function results, the standard library has it built in:

Python
from functools import lru_cache

@lru_cache(maxsize=1024)
def course_price(course_id: int) -> int:
    print("computing...")
    return course_id * 1000

course_price(5)
course_price(5)                 # served from cache, no "computing..."
print(course_price.cache_info())
Plaintext
computing...
CacheInfo(hits=1, misses=1, maxsize=1024, currsize=1)

In interviews, implement the linked-list version first, then mention OrderedDict and lru_cache to show you know the practical tools.

Extensions interviewers ask about

  • Thread safety — wrap get/put in a lock, or shard the cache into segments with their own locks.
  • TTL support — store an expiry time per node and treat expired nodes as misses.
  • LFU cache — evict the least frequently used; needs frequency buckets (a harder follow-up).
  • Approximate LRU — Redis samples a few keys and evicts the oldest among them, avoiding a global linked list.

Common mistakes

  • Using a list and list.remove, which is O(n).
  • Forgetting to update recency on get.
  • Not storing the key inside the node, making it impossible to delete the evicted entry from the map.
  • Evicting before inserting when updating an existing key, which can evict the wrong item.

Key takeaways

  • LRU = hash map for O(1) lookup + doubly linked list for O(1) recency updates.
  • Sentinel nodes simplify insertion and removal.
  • In Python, OrderedDict and functools.lru_cache give you LRU behaviour for free.
  • Be ready to discuss thread safety, TTLs and LFU as follow-ups.
Finished this lesson?
Tick it off to track your Caching Strategies progress.
Next lesson