LRU Cache: Build One With a Hash Map and a Linked List

Why this problem shows up everywhere

If you have ever sat through a software interview, you have probably met this question: “Design a data structure that follows a Least Recently Used cache.” It is a favourite of interviewers for good reason. It is short to state, it cannot be solved with a single built-in structure, and the solution reveals whether you understand how data structures complement each other.

But it is far more than an interview trick. I have used LRU caches to speed up image thumbnails, to keep recent database lookups in memory, and to throttle expensive API calls. The idea is so useful that it appears at almost every level of computing, from the cache inside your processor to the apps in your phone’s switcher.

In this article we will build an LRU cache from scratch. I will explain the idea with everyday examples, show why each simple approach fails, then assemble the real solution step by step with working code you can paste and run. There are diagrams, a traced example, a simulation comparing LRU with other policies, and a quiz.

What is a cache, and why does it need to forget?

A cache is a small, fast store that holds copies of things that are slow to get. If you read the same record from a database a thousand times, it makes sense to keep the answer in memory rather than asking the database again.

The catch is that fast storage is small. Memory is limited, so the cache must have a maximum size, called its capacity. Once it is full and a new item arrives, something has to go. Deciding what to remove is the job of the eviction policy.

Think of a small desk. You can keep ten books on it. Whenever you need an eleventh book, you must send one back to the shelf. Which one? You would probably return the book you have not touched for the longest time, because you are least likely to need it soon. That intuition is the entire LRU policy.

Eviction policies compared

LRU is not the only choice. Here are the common ones in plain words.

LRU strikes a very good balance. It is easy to explain, it adapts quickly to changing behaviour, and as we will see in a simulation, it beats FIFO and random eviction on realistic access patterns.

The job description: what our cache must do

We need a class with two operations:

• get(key) returns the stored value, or -1 if the key is not there. If it is there, it counts as a use.
• put(key, value) stores or updates a value. If the cache is already at capacity and the key is new, it first evicts the least recently used item.

And here is the demanding part: both operations must run in O(1) time, meaning constant time no matter how many items are cached. That requirement is what makes the problem interesting.

Why one data structure is not enough

Let us test the obvious ideas first, because the failures teach you the design.

Attempt 1: just a hash map

A hash map (a dictionary in Python, an object or Map in JavaScript) finds a value by key in constant time. Perfect for get. But a plain hash map has no useful notion of “least recently used.” When the cache is full, you would have to scan every entry to find the oldest. That makes eviction O(n).

Attempt 2: just a list or array

Keep items in an array, most recent at the front. Now the order is explicit and the least recent is always at the end. But finding a key means searching the array, which is O(n). And moving an item to the front means shifting the others. Both are slow.

The insight

The hash map is excellent at finding things and terrible at order. The list is excellent at order and terrible at finding things. So use both: the hash map finds the item instantly, and the list tracks order. To connect them, the hash map does not store values directly. It stores a pointer to the item’s node in the list.

Why a doubly linked list

A linked list is a chain of nodes where each node points to the next. In a singly linked list you can only move forward. A doubly linked list also keeps a pointer to the previous node.

That second pointer is the whole trick. When the hash map hands us a node in the middle of the list, we want to cut it out and move it to the front. Cutting out requires updating the previous node’s next pointer and the following node’s prev pointer. With a doubly linked list, the node already knows both neighbours, so removal takes a few assignments, with no searching. That is O(1).

We also add two dummy nodes, a head and a tail, that never hold data. They sit at the two ends so we never have to write special code for an empty list or for the first and last real node. This small habit eliminates a whole class of bugs.

Notice that the hash map keys (A, C, D) are in no particular order, and the lines cross. That is fine. The map only answers “where is this item?” The list answers “which item is oldest?”

The four moves

Every operation reduces to a handful of pointer moves.

Move 1: get on a hit

Look up the node through the map, unlink it from where it is, and insert it right after HEAD. Return its value.

Move 2: get on a miss

If the key is not in the map, return -1. The order does not change.

Move 3: put on an existing key

Update the stored value, then move the node to the front, because writing counts as a use.

Move 4: put on a new key

If the cache is full, remove the node just before TAIL, and delete its key from the map. Then create a new node, add it to the map, and insert it after HEAD.

The full Python implementation

Here is the whole thing. It is about fifty lines, and I have tested it against a second implementation on thousands of random operations.

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

    def __init__(self, key=0, value=0):
        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()            # dummy node on the "most recent" side
        self.tail = Node()            # dummy node on the "least recent" side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):          # unlink a node from the list
        node.prev.next = node.next
        node.next.prev = node.prev

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

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)            # it was just used,
        self._add_front(node)         # so move it to the front
        return node.value

    def put(self, key, value):
        if self.capacity <= 0:
            return
        node = self.map.get(key)
        if node is not None:          # key exists: update and refresh
            node.value = value
            self._remove(node)
            self._add_front(node)
            return
        if len(self.map) >= self.capacity:
            lru = self.tail.prev      # least recently used node
            self._remove(lru)
            del self.map[lru.key]     # this is why nodes store their key
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

    def order(self):                  # helper for demos: most recent first
        out, cur = [], self.head.next
        while cur is not self.tail:
            out.append(cur.key)
            cur = cur.next
        return out

Let us walk through the key details.

• Dummy head and tail: the real nodes always live between them, so _remove and _add_front never meet a null neighbour.
• _remove and _add_front: these two helpers do all the pointer surgery. Every public method is built from them, which keeps the code short and the bugs few.
• Storing the key in the node: when we evict the tail node, we only have the node in our hand. We need its key to delete the matching entry from the map. Forget this and the map slowly fills with stale entries.
• Order of operations in put: check for an existing key first, then evict if full, then insert. Mixing the order leads to evicting the very key you are about to update.
• Capacity guard: a capacity of zero or less simply stores nothing.

Tracing it by hand

Code is easier to trust when you have watched it work. Here is a run with capacity 3. The last column shows the list from most recent to least recent after each step. I generated this table by actually running the code above.

Look at step 5. The cache holds A, C, B with B at the back, so adding D evicts B. At step 6 we ask for B and get -1, because it was evicted. Step 7 updates C, and step 9 evicts A, which has not been touched since step 4. Every eviction was the item that had waited longest.

The shortcut: OrderedDict in Python

Python gives you a dictionary that remembers insertion order and can move items to the end in constant time. That means you can write an LRU cache in about fifteen lines.

from collections import OrderedDict

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

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)          # mark as most recently used
        return self.data[key]

    def put(self, key, value):
        if self.capacity <= 0:
            return
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # drop the oldest entry

This version is shorter, and in real projects it is usually the right choice. But in an interview, or when you want to understand the machinery, build the manual version first. Interviewers often use the OrderedDict version as a follow-up: “Great, now tell me how that works inside.” The answer is that it is a hash map plus a doubly linked list, exactly like ours.

There is also a ready-made option for caching function results. The functools.lru_cache decorator wraps a function and remembers its most recent calls, discarding the least recently used when it hits its limit.

The same idea in JavaScript

JavaScript’s Map remembers insertion order too. Delete and re-insert a key to make it the most recent, and the first key in the map is always the least recent.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();               // Map remembers insertion order
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);           // re-insert = most recent
    return value;
  }
  put(key, value) {
    if (this.capacity <= 0) return;
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);          // first key = least recent
    }
  }
}

This is neat for small caches. For very large or very hot caches, a hand-built linked list can have better performance characteristics, since the delete-and-reinsert approach relies on the engine’s implementation details. For most web applications, this version is perfectly good.

Why it is O(1)

Every step is constant time, so get and put are O(1) on average. The memory cost is O(capacity), because we store at most that many nodes and map entries.

Where LRU caches live in the real world

Tap through five places you already rely on, each with the reasoning behind it.

maxmemory 100mb
maxmemory-policy allkeys-lru

from functools import lru_cache

@lru_cache(maxsize=128)
def get_rate(currency):
    ...  # slow work here

get_rate("USD")
print(get_rate.cache_info())

Notice how often real systems use an approximation of LRU. Perfect order tracking costs memory and time on every access, so engineers trade a little accuracy for a lot of speed. Understanding the exact version, which is what we built, is what lets you reason about those approximations.

Does LRU actually beat the alternatives? A simulation

Claims are cheap, so I ran an experiment. I generated 20,000 requests over 200 different keys, with some keys far more popular than others, which is how real traffic tends to behave. Then I replayed the same requests against LRU, FIFO and random eviction at four cache sizes.

LRU gets roughly four to six percentage points more hits than FIFO and random eviction at each size. That may sound modest, but remember what a hit means: a request answered from fast memory instead of a slow database or network call. Across millions of requests, those extra hits add up to real money and real seconds.

The result also shows something else: bigger caches help a lot. Going from 10 slots to 80 lifts LRU from about 32% to about 77%. Eviction policy matters, but capacity matters more.

When LRU fails

I would be misleading you if I presented LRU as perfect. It has two classic weaknesses, and knowing them is the mark of someone who has used caches in production.

The looping worst case

Suppose your cache holds 10 items and your program loops over 11 different keys, again and again. Every time you ask for a key, it has just been evicted, because it was the least recently used. The result: a hit rate of exactly 0%. I confirmed this by running it: with a loop of 11 keys and a capacity of 10, both LRU and FIFO miss on every single request after the first pass.

The big scan

Imagine a database that caches popular rows, and then someone runs a report that reads every row once. Each of those one-time reads enters the cache as the “most recently used” and pushes out the genuinely popular items, which are never used again by the scan. This is called cache pollution. Variants such as 2Q, LRU-K and ARC, or a midpoint-insertion scheme, exist specifically to resist it.

The lesson is not to avoid LRU. It is to know that no policy is best for every workload, and to measure your own traffic before deciding.

Testing your implementation

When I review an LRU cache, I look for these cases. They catch most bugs.

• Missing key: get on an empty cache returns -1.
• Capacity of one: every new put evicts the previous key.
• Update an existing key: the value changes, the size does not, and the key becomes most recent.
• Get refreshes recency: after a successful get, that key must survive the next eviction.
• Zero capacity: nothing is stored, and nothing crashes.
• Randomised comparison: run thousands of random operations against a trusted version, such as the OrderedDict one, and compare every result.

The randomised check is my favourite. It finds the strange edge cases you did not think to write by hand.

Six mistakes people make (tap to open)

Quick quiz: test yourself

Tap each question to reveal the answer and its reasoning.

Frequently asked questions