How to Implement an LRU Cache in O(1) Time Complexity: A Complete Guide

You can implement an O(1) LRU cache by combining a HashMap for key lookup with a doubly-linked list to track access order, enabling constant-time get and put operations.

The labuladong/fucking-algorithm repository provides a definitive implementation of this classic data structure in 高频面试系列/LRU算法.md. This article breaks down the exact design patterns, code structure, and complexity guarantees used in that source to help you build a production-ready LRU cache.

Why O(1) Time Complexity Requires Two Data Structures

An LRU (Least Recently Used) cache must support two operations in constant time: get to retrieve a value, and put to insert or update a value while evicting the oldest entry when capacity is exceeded.

No single standard data structure provides both fast lookup and ordered eviction. A HashMap offers O(1) key lookup but cannot track usage order. A linked list maintains order but requires O(n) time to find a node by key. The solution is to combine both: use the HashMap to map keys to list nodes, and use the doubly-linked list to maintain the access order.

Core Design: HashMap + Doubly-Linked List

The implementation in 高频面试系列/LRU算法.md defines three core components: a Node class, a DoubleList class to manage the linked structure, and the LRUCache class that orchestrates both data structures.

The Node Structure

Each cache entry is wrapped in a node containing the key, value, and bidirectional pointers:

class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) { 
        this.key = k; 
        this.val = v; 
    }
}

Storing the key inside the node is critical for O(1) eviction. When removing the least-recently used node from the head of the list, you need its key to delete the corresponding entry from the HashMap.

The DoubleList Class

The DoubleList class manages the linked list using dummy head and tail sentinels to eliminate edge-case checks:

class DoubleList {
    private Node head, tail;
    private int size;

    public DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    public Node removeFirst() {
        if (head.next == tail) return null;
        Node first = head.next;
        remove(first);
        return first;
    }

    public int size() { return size; }
}

All list operations—addLast, remove, and removeFirst—execute in O(1) time because the doubly-linked structure provides direct access to both previous and next nodes.

The LRUCache Class Structure

The LRUCache combines a HashMap<Integer, Node> for key lookup and the DoubleList for ordering:

class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
}

Implementing O(1) Get and Put Operations

The public API delegates to private helper methods that maintain the O(1) invariant by manipulating both data structures simultaneously.

Get Operation (makeRecently)

When a key is accessed, it becomes the most recently used entry:

public int get(int key) {
    if (!map.containsKey(key)) return -1;
    makeRecently(key);
    return map.get(key).val;
}

private void makeRecently(int key) {
    Node x = map.get(key);
    cache.remove(x);      // O(1) removal from current position
    cache.addLast(x);     // O(1) insertion at tail (most recent)
}

Put Operation Logic

Insertion handles three cases: updating an existing key, evicting when full, or adding a new entry:

public void put(int key, int val) {
    if (map.containsKey(key)) {
        deleteKey(key);
        addRecently(key, val);
        return;
    }
    if (cap == cache.size()) {
        removeLeastRecently();
    }
    addRecently(key, val);
}

private void addRecently(int key, int val) {
    Node x = new Node(key, val);
    cache.addLast(x);
    map.put(key, x);
}

private void deleteKey(int key) {
    Node x = map.get(key);
    cache.remove(x);
    map.remove(key);
}

private void removeLeastRecently() {
    Node deleted = cache.removeFirst();
    if (deleted != null) {
        map.remove(deleted.key);
    }
}

Each helper performs at most one HashMap operation and a constant number of pointer updates, preserving the O(1) time guarantee.

Complete Java Implementation from labuladong/fucking-algorithm

Below is the full, runnable implementation extracted from 高频面试系列/LRU算法.md in the labuladong/fucking-algorithm repository. This version uses the custom DoubleList approach to demonstrate the underlying mechanics:

import java.util.HashMap;

class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) { this.key = k; this.val = v; }
}

class DoubleList {
    private Node head, tail;
    private int size;

    public DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    public Node removeFirst() {
        if (head.next == tail) return null;
        Node first = head.next;
        remove(first);
        return first;
    }

    public int size() { return size; }
}

class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            deleteKey(key);
            addRecently(key, val);
            return;
        }
        if (cap == cache.size()) removeLeastRecently();
        addRecently(key, val);
    }

    private void makeRecently(int key) {
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }

    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        cache.addLast(x);
        map.put(key, x);
    }

    private void deleteKey(int key) {
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }

    private void removeLeastRecently() {
        Node deleted = cache.removeFirst();
        if (deleted != null) map.remove(deleted.key);
    }
}

Alternative: Using LinkedHashMap for O(1) LRU Cache

For production Java code, you can achieve the same O(1) behavior without implementing the linked list manually. The java.util.LinkedHashMap class maintains insertion or access order and provides O(1) operations when configured correctly:

import java.util.LinkedHashMap;

class LRUCache {
    private final int cap;
    private final LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.cap = capacity;
        // accessOrder = true enables LRU ordering (most recent at tail)
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true);
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        return cache.get(key);  // Automatically moves entry to tail
    }

    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            cache.put(key, val);  // Updates value and moves to tail
            return;
        }
        if (cache.size() >= cap) {
            // Head contains the least recently used entry
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        cache.put(key, val);
    }
}

Both approaches satisfy the O(1) time requirement. The custom implementation demonstrates the underlying algorithmic mechanics, while the LinkedHashMap approach leverages the JDK's optimized internal implementation.

Complexity Analysis

Understanding why this design achieves O(1) requires examining the cost of each component:

• HashMap operations: get, put, and remove run in O(1) average time.
• Doubly-linked list operations: addLast, remove, and removeFirst manipulate exactly four pointers per operation, making them O(1).

Because every public method (get and put) performs a constant number of HashMap lookups and list pointer updates, the overall time complexity remains O(1) for both operations.

Space complexity is O(capacity) because the cache stores at most capacity nodes in both the HashMap and the linked list.

Summary

• O(1) LRU cache implementation requires combining a HashMap for key-to-node mapping with a doubly-linked list to maintain usage order.
• The HashMap provides instant access to any node, while the doubly-linked list allows O(1) removal and insertion at both ends.
• The labuladong/fucking-algorithm repository provides a complete Java implementation in 高频面试系列/LRU算法.md using custom Node and DoubleList classes.
• For production Java code, LinkedHashMap with accessOrder=true provides a built-in O(1) LRU cache without manual list management.
• All operations—get, put, insertion, update, and eviction—execute in guaranteed O(1) time with O(capacity) space usage.

Frequently Asked Questions

Why must we use a doubly-linked list instead of a singly-linked list for LRU cache?

A singly-linked list cannot remove an arbitrary node in O(1) time because you need a pointer to the previous node to perform the deletion. In an LRU cache, when you access an existing key via get, you must move that node to the tail (most recent position). With a doubly-linked list, each node stores prev and next pointers, allowing O(1) removal from any position and O(1) insertion at the tail.

Can I implement an O(1) LRU cache in Python or C++ using the same approach?

Yes, the same HashMap + Doubly-Linked List design works in any language. In Python, you can use collections.OrderedDict which maintains insertion order and provides O(1) move_to_end and popitem methods. In C++, you can combine std::unordered_map with std::list, storing iterators in the map to achieve O(1) deletion from the list. The core algorithm remains identical: map for key lookup, list for order maintenance.

How does LinkedHashMap maintain O(1) time complexity for LRU operations?

LinkedHashMap extends HashMap and maintains a doubly-linked list running through all entries in the background. When initialized with accessOrder=true, every get or put operation automatically moves the accessed entry to the end of this internal linked list. Because LinkedHashMap stores direct references to the linked list nodes within its hash buckets, it can perform this reordering in O(1) time, just like the custom implementation. The removeEldestEntry method can also be overridden to automate eviction when the capacity is exceeded.

What happens if the capacity is set to zero in the LRU cache implementation?

If the capacity is initialized to zero, the cache cannot store any entries. In the custom implementation from 高频面试系列/LRU算法.md, calling put when cap == 0 and cache.size() == 0 will trigger removeLeastRecently(), which attempts to remove the first node. Since the list is empty, removeFirst() returns null, and the method proceeds to add the new entry. However, this violates the intended capacity constraint. Production implementations should guard against zero capacity by either throwing an exception or immediately returning without insertion when capacity <= 0.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}