LESSON 40 · INTERMEDIATE4 min read

Composite Data Structures: Designing an O(1) LRU Cache with Hash-Doubly-Linked Lists

Engineer an industrial-grade Least Recently Used (LRU) Cache combining a HashMap with a Doubly Linked List to achieve strict O(1) get and put operations.

OpenJDK 21+ (LTS)Free to readModule 10 of 15

YOUR NEXT SMALL WINS

By the end, you’ll be able to…

Synthesize HashMaps and Doubly Linked Lists into a composite O(1) data structure
Implement sentinel head and tail nodes to eliminate edge-case boundary checks during node insertion and deletion
Analyze eviction policies and cache hit/miss latency in high-concurrency systems

01The Architectural Dilemma of LRU Caches

A Least Recently Used (LRU) cache is a bounded in-memory store that evicts the least recently accessed item when capacity is exceeded. It is ubiquitous in database buffer pools (InnoDB buffer pool), web browser asset caching, and CPU hardware cache line replacement.

The algorithmic challenge lies in achieving O(1) time complexity for BOTH get(key) and put(key, value) operations. An array or standard ArrayList allows O(1) index access, but evicting the oldest item or moving an accessed item to the front requires O(n) shifting.

Conversely, a singly linked list allows fast insertion if we hold the head pointer, but finding an item by key requires an O(n) linear scan. Even if we use a HashMap to locate a node in O(1), deleting a node from a singly linked list still requires traversing to its predecessor—an O(n) operation.

02The Dual Hash + Doubly Linked List Solution

To achieve strict O(1) for both operations, we combine two complementary structures: 1. A HashMap<K, Node> that maps every key directly to its corresponding doubly linked list node, enabling O(1) key lookups.

2. A Doubly Linked List where each Node contains prev and next pointers. When given a node reference from the HashMap, we can remove it from its current position in O(1) time by re-linking node.prev.next = node.next and node.next.prev = node.prev.

By introducing dummy 'head' and 'tail' sentinel nodes, we guarantee that the list is never empty, completely eliminating null checks when adding to the front or removing from the back.

example.js☕Java

Ctrl + ↵

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { this.key = k; this.value = v; }
    }

private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head, tail; // Sentinels

public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node); // Mark as most recently used
        return node.value;
    }

public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            if (map.size() >= capacity) {
                Node lru = tail.prev;
                removeNode(lru);
                map.remove(lru.key);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);
        }
    }

private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
}

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

03State Transition Trace Table

Observing the state progression of an LRU Cache with capacity 2 clarifies the eviction mechanism:

notes.txtPlain text

+-----------+-------------+----------------------+--------------------+| Operation | Key, Value  | Cache Order (MRU->LRU)| Evicted Item       |+-----------+-------------+----------------------+--------------------+| put(1, 1) | 1, 1        | [1]                  | None               || put(2, 2) | 2, 2        | [2, 1]               | None               || get(1)    | Returns 1   | [1, 2]               | None (1 moved MRU) || put(3, 3) | 3, 3        | [3, 1]               | Key 2 evicted!     || get(2)    | Returns -1  | [3, 1]               | Cache Miss         || put(4, 4) | 4, 4        | [4, 3]               | Key 1 evicted!     |+-----------+-------------+----------------------+--------------------+

04Production Considerations: Concurrency and Sizing

In production enterprise systems, a naive synchronized wrapper around an LRU cache creates high lock contention because every single get() operation performs a structural write to the linked list (moving the node to the head).

Modern high-concurrency caches like Caffeine solve this by decoupling cache access from eviction book-keeping using ring buffers and probabilistic sampling (Window TinyLFU), achieving near-perfect hit ratios with lock-free reads.

05Production Architecture & Engineering Trade-Offs

Algorithmic efficiency in real-world software is heavily influenced by CPU hardware architecture, specifically the L1, L2, and L3 cache hierarchies and hardware branch predictors. While an algorithm may exhibit an optimal theoretical asymptotic complexity like O(n), poor spatial locality caused by pointer chasing across fragmented memory blocks can make it perform slower than a theoretically inferior algorithm operating over contiguous array memory.

When implementing two pointers and sliding window routines, developers must maintain strict boundary invariants to eliminate off-by-one errors and avoid redundant recomputations. Precomputing prefix sums or maintaining monotonic tracking queues transforms polynomial search operations into deterministic linear scans that execute with minimal memory allocations.

LET IT CLICK

The ideas worth keeping.

Combining a HashMap with a Doubly Linked List achieves O(1) get and put cache operations.
Sentinel head and tail nodes eliminate null pointer checks during node additions and removals.
Nodes must store their key to enable O(1) removal from the hash map upon LRU eviction.

TURN UNDERSTANDING INTO SOMETHING YOU CAN DO

Make it yours.

Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.

Exercise 1: Why must the Doubly Linked List Node in an LR

Why must the Doubly Linked List Node in an LRU Cache store both the key AND the value, rather than just the value?

your_turn_1.java☕Java

Ctrl + ↵

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

Explore a worked solution

one_possible_solution.javaJava

// When the cache capacity is exceeded, we evict tail.prev (the least recently used node).// To remove that item from the HashMap in O(1) time, we need its key (map.remove(node.key)).// If the node only stored value, we would have to search the entire map to find which key points to it,// degrading eviction time from O(1) to O(n).

Consider what happens during map.remove() when the tail node is evicted.

Exercise 2: Implement an O 1 removeNode method for a Dou

Implement an O(1) removeNode method for a Doubly Linked List node with prev and next pointers.

your_turn_2.java☕Java

Ctrl + ↵

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

Explore a worked solution

one_possible_solution.javaJava

public class NodeOps {    public static void remove(Node node) {        node.prev.next = node.next;        node.next.prev = node.prev;    }}

Update node.prev.next to bypass node, and node.next.prev to bypass node.

Keep exploring.

The official references behind this lesson, when you want a second angle or the full details.

MODULE 10 · PRACTICAL SELF-CHECK

Pause. Put the pieces together.

You’ve reached the end of Linked Lists, Sentinel Nodes & Floyd's Cycle Detection. Before moving on, use this task to check what you can do independently.

Engineer a production-ready LRU cache combining a HashMap with a Doubly Linked List.

Try it in your own environment and write down the result. This is a self-check; reading completion does not evaluate your code.

Review this module

One lesson closer.

Reading is a start. Trying it yourself makes the connection.

Solve the hands-on coding challenge in the knowledge section to verify your code and unlock lesson completion.

By the end, you’ll be able to…

01The Architectural Dilemma of LRU Caches

02The Dual Hash + Doubly Linked List Solution

03State Transition Trace Table

04Production Considerations: Concurrency and Sizing

05Production Architecture & Engineering Trade-Offs

The ideas worth keeping.

Make it yours.

Exercise 1: Why must the Doubly Linked List Node in an LR

Exercise 2: Implement an O 1 removeNode method for a Dou

What stayed with you?

Exercise 1: Why must the Doubly Linked List Node in an LR

Keep exploring.

Pause. Put the pieces together.

One lesson closer.