LRU Cache Implementation: Two Data Structures Fused for O(1) Get and Put

Your app calls a database. The database is slow. You add a cache. The cache fills up. Now you have a new problem: which entry do you throw away?

The Least Recently Used (LRU) cache answers that question with a single bet: whatever you touched most recently, you'll probably touch again. Whatever you haven't touched in a while, evict it. Terrible heuristic for social life. Surprisingly good heuristic for software. Any correct LRU cache implementation delivers both get and put in O(1). That's the promise. Delivering on it requires fusing two data structures that, alone, each fail in exactly the place the other succeeds.

LRU shows up in browser caches, OS page replacement, DNS resolvers, Redis eviction, and LeetCode 146. It's also a design interview favorite precisely because the answer isn't obvious until you see it.

Why One Data Structure Always Fails

Start with the wrong answers. This part matters.

A hash map alone gives you O(1) get and put. But when the cache is full and you need to evict the least recently used entry, you have to scan every entry to find the one with the oldest access time. That's O(n). Unacceptable. You just built a cache that gets slower the more data it holds.

A linked list alone lets you maintain order cheaply. Move recently accessed nodes to the front; the tail is always the LRU entry. But looking up a specific key requires traversing the entire list. O(n) again. Two structures, two ways to be slow.

You need O(1) lookup and O(1) recency tracking simultaneously, and no single structure provides both. A hash map gives the first. A doubly linked list, given a direct pointer to the node, gives the second. Together they cover every operation in O(1).

How It Works Inside

The internal structure is two things wired together:

1. A hash map from key to node pointer.
2. A doubly linked list of nodes, ordered from most recently used (head) to least recently used (tail).

Every node lives in both structures at once. The hash map holds a reference to the node for O(1) access. The linked list holds the node itself, positioned by recency.

The hash map and the doubly linked list share the same nodes. Neither structure owns them. Both use them.

hash map:
  1  -->  Node A (key=1, val=10)
  2  -->  Node B (key=2, val=20)
  3  -->  Node C (key=3, val=30)

doubly linked list (MRU at head, LRU at tail):

  HEAD <--> [ A: 1=10 ] <--> [ B: 2=20 ] <--> [ C: 3=30 ] <--> TAIL
                MRU                                  LRU

get(key=1) before and after:

Before:   HEAD <--> [ A: 1=10 ] <--> [ B: 2=20 ] <--> [ C: 3=30 ] <--> TAIL
                        MRU                                  LRU

Step 1 - detach A:
          HEAD <--> [ B: 2=20 ] <--> [ C: 3=30 ] <--> TAIL

Step 2 - push A to front:
          HEAD <--> [ A: 1=10 ] <--> [ B: 2=20 ] <--> [ C: 3=30 ] <--> TAIL
                        MRU                                  LRU

When get(1) runs:

• The hash map finds Node A in O(1).
• Splice Node A out of its current list position: O(1) because you hold pointers to both its neighbors.
• Insert Node A at the front: O(1).
• Return the value.

Three pointer operations, constant time. The hash map does the lookup. The doubly linked list does the reorder.

put(key=4, val=40) with eviction (capacity=3):

Before:   HEAD <--> [ A: 1=10 ] <--> [ B: 2=20 ] <--> [ C: 3=30 ] <--> TAIL
                        MRU                                  LRU

Step 1 - create new node D, push to front:
          HEAD <--> [ D: 4=40 ] <--> [ A: 1=10 ] <--> [ B: 2=20 ] <--> [ C: 3=30 ] <--> TAIL

Step 2 - over capacity, evict tail.prev (Node C):
          HEAD <--> [ D: 4=40 ] <--> [ A: 1=10 ] <--> [ B: 2=20 ] <--> TAIL
          delete cache[3]

When put(4, 40) runs and the cache is full:

• Create the new node, insert at front of list, add to hash map. All O(1).
• Evict by removing tail.prev (the LRU node) from the list and deleting its entry from the hash map. All O(1).

The new entry claims the MRU seat. The oldest entry gets quietly removed. Nobody mourns it.

The O(1) removal is exactly why you need a doubly linked list. A singly linked list can delete the next node in O(1), but removing an arbitrary node requires knowing its predecessor. You'd have to walk the list. With node.prev, you always have that pointer. Done in O(1).

Sentinel Nodes: The Detail That Eliminates Edge Cases

Most clean implementations use two dummy nodes at head and tail that never hold real data.

  sentinel HEAD <--> [real nodes ...] <--> sentinel TAIL
  (key=0, val=0)                          (key=0, val=0)

Without sentinels, inserting at the front requires a null check for an empty list. Removing from the back requires checking if you're removing the only node. With sentinels, the list is structurally never empty and every splice follows the same four lines of pointer surgery. No special cases. You can throw out the null checks like they owe you money.

The real nodes always sit between the two sentinels, so the code looks identical whether the list has one element or a thousand.

The Node Must Store Its Key

This is the bug that teaches humility. Not because it crashes. Because the cache looks fine. It returns correct values. The map just quietly grows past capacity, and your "bounded" cache isn't actually bounded. Nothing explodes. The leak is polite about it.

When you evict the LRU node (the one before the tail sentinel), you need to remove it from the hash map too. That requires the key. So the node must store it.

     node layout:
    +-------+-------+------+------+
    |  key  |  val  | prev | next |
    +-------+-------+------+------+
       ^^^
  you need this to clean up the hash map on eviction

If your node stores only the value, you know which list node to remove. You do not know which hash map entry to delete. The map silently grows past capacity and you have a memory leak.

The key field looks redundant until eviction. Then it's the only thing that makes the hash map cleanup work.

Every Operation Is O(1)

Every operation is strictly O(1), not amortized. There are no batched operations and no periodic reorganizations. Each get and put touches a constant number of pointers.

This contrasts with dynamic array operations, where append is amortized O(1) due to occasional O(n) resizes. LRU has no such debt. The hash map lookup is O(1) average (worst case O(n) for degenerate hash collisions, but that's a hash map problem, not an LRU one).

One Structure, Every Language

class Node:
    def __init__(self, key: int, val: int):
        self.key = key
        self.val = val
        self.prev: "Node | None" = None
        self.next: "Node | None" = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: dict[int, Node] = {}
        self.head = Node(0, 0)  # sentinel MRU end
        self.tail = Node(0, 0)  # sentinel LRU end
        self.head.next = self.tail
        self.tail.prev = self.head

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

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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._push_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._push_front(node)
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

What Problems Does It Solve?

LRU fits any context where you have a fixed memory budget and want the hot working set to stay in memory. Common cases:

Caching with bounded size. The canonical case. You can fetch anything, but storing everything costs too much. Keep the recently accessed items; let the cold ones fall off.

OS page replacement. When physical memory fills up, the OS evicts a page. LRU is the textbook policy. In practice, operating systems use Clock (a hardware-friendly approximation), but the reasoning is identical.

Session storage. Keep recently active sessions in memory. Sessions that haven't been touched fall out naturally.

Redis eviction. Redis's allkeys-lru policy does approximately this. Redis samples a small set of keys and evicts the one with the oldest access timestamp, rather than tracking exact recency. Same idea, cheaper implementation.

Design interview building blocks. Twitter's timeline cache, YouTube's video metadata cache, CDN edge caches. Understanding LRU unlocks these because each is a variation on the same bounded-cache problem.

LRU also connects to dynamic programming: memoization is an unbounded cache. LRU is what memoization becomes when you have a memory budget.

How to Spot an LRU Cache Interview Question

Signal 1: The words "least recently used" or "most recently accessed"

When a problem description mentions evicting the least recently used item, or keeping only the most recently accessed N items, you are looking at LRU verbatim.

Example: LeetCode 146, LRU Cache. The problem says: implement get and put, both O(1), evict the least recently used item when full. Unpack that sentence.

• "O(1) get" requires a hash map.
• "O(1) eviction of the LRU item" requires an ordered structure where you can remove from the back in O(1). That's a doubly linked list.
• "O(1) reordering on access" requires that you can move a node to the front in O(1). You need a direct pointer to the node. That's the hash map's job, pointing directly at the list node.

Every word of the problem specification maps to a piece of the data structure. Once you see the pattern, the solution assembles itself.

Signal 2: "Fixed capacity" plus any form of recency tracking

Any time you see "keep the last K" or "cache the N most recent results", stop and think LRU. The stored items might be API responses, rendered page fragments, parsed tokens, DNS entries, or database rows. The eviction logic is the same.

Example: Browser history with fast URL lookup. You want to store the last 100 pages a user visited. Requirements: O(1) lookup by URL (to check if a page is already in history), O(1) insertion of new pages, automatic eviction of pages beyond the last 100.

A hash map alone handles lookup but has no ordering. A linked list alone has ordering but O(n) lookup. LRU: hash map from URL to list node, doubly linked list ordered by visit time. New visits push to the front; the 101st visit evicts the tail.

When LRU Is Not the Right Answer

LRU bets on temporal locality: recent access predicts future access. That bet loses on sequential scans. If your workload reads through a large dataset in order, LRU evicts the next item you need every single time. Cache hit rate drops to zero. This is called cache thrashing.

For frequency-based workloads, where some items are accessed constantly regardless of when they were last touched, LFU (Least Frequently Used) is a better fit. For sequential workloads, most-recently-used (MRU) eviction or a non-temporal policy works better.

The Four Things People Get Wrong

1. Forgetting to move the node on get. Reading a key counts as using it. If you return the value without moving the node to the front of the list, your recency order breaks silently. The cache still returns correct values but evicts the wrong entries. It will pass every test that checks return values and fail every test that checks eviction order. The most common LRU bug, and the quietest.

2. Not storing the key inside the node. When evicting, you remove the tail's predecessor from the list and from the hash map. The list removal is straightforward. The hash map removal requires the key. If the node only holds the value, you cannot find and delete the map entry. The map grows without bound and your "bounded" cache is not bounded. It will take a while to notice.

3. Using a singly linked list. You need O(1) removal of an arbitrary node. A singly linked list can remove the next node in O(1), but removing a node you hold a pointer to requires finding its predecessor, which requires traversal. Always doubly linked.

4. Off-by-one in pointer updates. _push_front and _remove each touch four pointers. Skipping any one of them leaves dangling references. The structure silently corrupts. The linked list now lies to you about its own shape. Write these as named helpers and test them independently before composing them into get and put. Drawing the pointer surgery on paper first is not embarrassing. Debugging a corrupt doubly linked list at midnight is.

For a broader view of how implementation bugs like these play out under interview pressure, these common coding interview mistakes cover the pattern in detail.

The Short Version

• LRU keeps the most recently used entries in memory and evicts the oldest when the cache is full.
• A hash map gives O(1) lookup but no ordering. A linked list gives O(1) ordering but O(n) lookup. You need both.
• A doubly linked list removes any node in O(1) given a pointer to it. A singly linked list cannot.
• Sentinel head and tail nodes eliminate edge-case null checks and make every splice identical.
• Every node must store its own key so eviction can clean up the hash map.
• get and put are strictly O(1). No amortization.
• Languages with ordered maps (JavaScript Map, Python OrderedDict, Ruby Hash, PHP array, Java LinkedHashMap, Kotlin LinkedHashMap) let you skip the manual linked list. Interviews almost always want the manual version.
• LRU bets on temporal locality. Sequential scan workloads will trash it.

The structure is clear on paper. Under interview conditions, with a clock running and someone asking follow-ups, the pointer surgery falls apart. SpaceComplexity runs live voice-based mock interviews on problems exactly like this, with rubric-based feedback on your explanation and your approach, not just whether the code compiles. Worth trying before the real thing.

Further Reading

• Cache Replacement Policies (Wikipedia)
• LRU Cache Implementation (GeeksforGeeks)
• LeetCode 146: LRU Cache
• Key Eviction in Redis (Redis Docs)
• std::list::splice (cppreference)