LRU Cache: Hash Map + Doubly Linked List

LRU Cache is LeetCode problem 146. It is probably the most famous design problem in all of coding interviews. Not because it is the hardest, but because it combines two data structures in a way that feels clever the first time you see it and obvious in hindsight.

The core insight: a hash map gives you O(1) lookup, but it has no sense of order. A linked list maintains order, but searching it is O(n). Combine them and you get O(1) everything. That pairing is what interviewers want you to discover on the whiteboard.

The problem

Design a data structure that follows the Least Recently Used (LRU) eviction policy. It should support two operations:

• get(key) - Return the value if the key exists, otherwise return -1. This counts as "using" the key.
• put(key, value) - Insert or update the key-value pair. If inserting causes the cache to exceed its capacity, evict the least recently used key first.

Both operations must run in O(1) time.

Why this is hard to get right

The O(1) constraint is what makes this tricky. Without it, you could use a list and scan for the least recently used item on each put. Or you could timestamp each entry and find the minimum. Both approaches work but are O(n) for at least one operation.

To get O(1) for both get and put, you need:

1. O(1) lookup by key - A hash map handles this.
2. O(1) insertion and removal of nodes by position - A doubly linked list handles this.
3. O(1) access to the least recently used item - Always keep it at a fixed position (right after the head sentinel).

The trick is connecting these two structures. The hash map does not just store values. It stores pointers to linked list nodes. That way, when you look up a key in the map, you get direct access to the node in the list, and you can unlink it and move it in constant time.

The data structure

You need a Node class for the doubly linked list. Each node holds a key, a value, and pointers to its previous and next neighbors.

You also need two sentinel nodes: a dummy head and a dummy tail. These never hold real data. They just mark the boundaries so you never have to deal with null checks when inserting or removing nodes.

The convention: nodes closer to the head are least recently used. Nodes closer to the tail are most recently used. When you access or insert a node, move it right before the tail. When you need to evict, remove the node right after the head.

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # key -> Node

        # Sentinel nodes
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

Two helper methods keep the code clean. One removes a node from wherever it sits in the list. The other inserts a node right before the tail (the most recently used position).

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

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

Visual walkthrough

Let's trace through a cache with capacity 3. Watch how nodes move within the list as we call get and put. The node right after HEAD is always the eviction candidate.

The key observation: every get and every put moves a node to the "most recent" position (right before TAIL). When we need to evict, we always remove the node right after HEAD. No scanning, no searching. Constant time.

The full solution

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _insert_before_tail(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._insert_before_tail(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])

        node = Node(key, value)
        self.cache[key] = node
        self._insert_before_tail(node)

        if len(self.cache) > self.cap:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

Let's break down each method:

get(key): Look up the key in the hash map. If it is not there, return -1. If it is, remove the node from its current position, reinsert it right before the tail (marking it as most recently used), and return the value.

put(key, value): If the key already exists, remove the old node first. Create a new node, add it to the hash map and insert it before the tail. If the cache is now over capacity, grab the node right after head (the LRU node), remove it from the list, and delete its key from the hash map.

The OrderedDict shortcut

Python has a built-in OrderedDict that already tracks insertion order and lets you move items to the end. This gives you a much shorter solution:

from collections import OrderedDict

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

    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.cap:
            self.cache.popitem(last=False)

This is clean and perfectly valid for interviews where the goal is to show you understand the concept. But some interviewers specifically want to see the manual linked list implementation to verify you can handle the pointer manipulation. Know both versions.

Complexity analysis

Time: O(1) for both get and put. Hash map lookup is O(1). Removing a node from a doubly linked list is O(1) when you have a direct pointer to it. Inserting before the tail is O(1). Every operation is a constant number of these O(1) steps.

Space: O(capacity). The hash map and linked list each store at most capacity entries, plus the two sentinel nodes.

Why does this need a doubly linked list?

A singly linked list would not work here. When you remove a node, you need to update the previous node's next pointer. With a singly linked list, finding the previous node requires O(n) traversal. The doubly linked list gives you node.prev for free, so removal is O(1).

The sentinel nodes (dummy head and tail) are also important. Without them, you would need special-case logic for inserting at the beginning, inserting at the end, removing the first node, and removing the last node. Four edge cases that disappear entirely when you use sentinels. The code is shorter and harder to get wrong.

Edge cases

• Capacity of 1. Every put evicts the previous entry. Make sure your eviction logic does not break when there is only one real node between head and tail.
• Updating an existing key. When you put a key that already exists, you must remove the old node first. Forgetting this leaves a stale node in the linked list.
• Getting a key that was evicted. It is no longer in the hash map, so return -1. Simple but worth verifying.
• Multiple gets of the same key. Each get moves the node to the most recent position. The rest of the list stays in order. Make sure your remove/insert helpers are idempotent.

The Building Blocks

This problem is built from two core building blocks:

Hash map for O(1) key lookup. The cache needs to find entries by key instantly. This is the same pattern you see in Two Sum, Group Anagrams, and every problem that needs fast membership testing.

Doubly linked list for O(1) ordered insertion and removal. The list maintains the usage order and lets you move or remove any node in constant time, as long as you have a direct reference to it. The sentinel node trick eliminates edge cases at the boundaries.

The combination of these two structures shows up in more places than just LRU Cache:

• LFU Cache (LeetCode 460) is the harder cousin. It uses a similar hash-map-plus-linked-list approach, but tracks frequency counts instead of recency. Multiple linked lists (one per frequency) replace the single list.
• Design HashMap (LeetCode 706) is a simpler version of the hash map side. It asks you to build the hash map itself using chaining or open addressing.
• All O(1) Data Structure (LeetCode 432) also combines a hash map with a doubly linked list to track the max and min frequency keys, supporting increment, decrement, getMaxKey, and getMinKey in O(1).
• Design Browser History (LeetCode 1472) uses a doubly linked list to track visited pages. Going back and forward is just following prev and next pointers.

Once you internalize how to pair a hash map with a linked list, you will start seeing this combination everywhere. It is one of the most powerful composite data structures in interview problems.

Why you will forget this (and how to fix it)

The LRU Cache solution has a lot of moving parts. Two helper methods, sentinel nodes, a Node class, hash map entries pointing to list nodes, and careful coordination between the two structures. You will read this, understand every line, and then struggle to reproduce it a week later.

The failure mode is always the same: you remember the big idea (hash map + linked list) but forget the details. Which direction does the list go? Does the LRU node sit after head or before tail? Where exactly do you insert new nodes? Do you delete from the map before or after removing from the list?

These details matter. Getting one wrong means the whole thing breaks. The only way to lock them in is repetition. Type the full solution from scratch, multiple times, with increasing gaps between sessions. After a few reps, the sentinel setup and the remove/insert dance become automatic.

Related posts

• Reverse Linked List - If you are rusty on linked list pointer manipulation, start here
• Hash Map Patterns - The foundation of the O(1) lookup side of this problem
• Linked List Cycle - Another problem where understanding pointer mechanics is the whole challenge

---

New to algorithms? Understand why this design achieves O(1) with our Big O Notation Guide.