How to Implement an LRU Cache with O(1) Time Complexity in Java

To implement an LRU Cache with O(1) time complexity, combine a HashMap for constant-time key lookups with a doubly-linked list to maintain usage order, enabling O(1) get, put, and eviction operations.

The kdn251/interviews repository provides foundational patterns for solving this classic system design problem. To implement an LRU Cache with O(1) time complexity for all operations, you must support get and put methods that retrieve values, insert new entries, and evict the least-recently-used item without scanning the data structure. This implementation leverages the HashMap pattern from company/google/InsertDeleteGetRandomO1.java and the linked node approach from company/bloomberg/MinStack.java.

The O(1) Design: HashMap Plus Doubly Linked List

An LRU Cache must support three core operations in constant average time: retrieving a value and marking it as recently used, inserting or updating a value, and evicting the least-recently-used entry when capacity is exceeded. Achieving O(1) time complexity requires two complementary data structures that work in tandem.

HashMap for Constant-Time Lookup

A HashMap maps each cache key to its corresponding node object, providing O(1) average time complexity for key existence checks and value retrieval. This eliminates the need to search through cache entries sequentially. The repository demonstrates this pattern in company/google/InsertDeleteGetRandomO1.java, where a HashMap enables O(1) insertion and deletion by maintaining direct references to elements.

Doubly Linked List for Usage Tracking

A doubly-linked list maintains the usage order of cache entries, with the most-recently used (MRU) item at the head and the least-recently used (LRU) item at the tail. Because the list is doubly linked, removing a node or inserting a node at the head requires only pointer updates—O(1) operations without traversal. This node-based approach follows the pattern demonstrated in company/bloomberg/MinStack.java, which uses a custom linked node to maintain auxiliary state (the current minimum) alongside stack elements.

Complete Java Implementation

The following implementation combines these patterns to create an LRU Cache with O(1) get and put operations. This code follows the architectural conventions established in the kdn251/interviews repository.

// File: src/main/java/lru/LRUCache.java
// Reference: HashMap O(1) pattern from company/google/InsertDeleteGetRandomO1.java
// Reference: Linked node pattern from company/bloomberg/MinStack.java

import java.util.HashMap;

/**
 * LRU Cache with O(1) time complexity for get and put operations.
 * Uses a HashMap for key lookup and a doubly-linked list for usage order.
 */
public class LRUCache {

    private final int capacity;
    private final HashMap<Integer, Node> map;
    private final Node head;   // dummy head (most-recent side)
    private final Node tail;   // dummy tail (least-recent side)

    /** Doubly linked node storing key, value and references. */
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    /** Initialize the LRU cache with positive capacity. */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        // Sentinel nodes simplify insert/remove logic
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    /** 
     * Return the value of the key if it exists, otherwise return -1.
     * Updates the entry to be most-recently used.
     */
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        // Move to front (MRU position)
        detach(node);
        insertAfterHead(node);
        return node.value;
    }

    /**
     * Update the value of the key if it exists, otherwise add the key-value pair.
     * If the cache exceeds capacity, evicts the least-recently used item.
     */
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            // Key exists: update value and move to front
            node.value = value;
            detach(node);
            insertAfterHead(node);
        } else {
            // New key: check capacity
            if (map.size() == capacity) {
                // Evict LRU (node before tail)
                Node lru = tail.prev;
                detach(lru);
                map.remove(lru.key);
            }
            Node newNode = new Node(key, value);
            insertAfterHead(newNode);
            map.put(key, newNode);
        }
    }

    /** Remove node from linked list by updating neighbour pointers. */
    private void detach(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /** Insert node right after dummy head (most-recent position). */
    private void insertAfterHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

Usage Example

The following demonstrates the LRU eviction policy and verifies the O(1) operation semantics:

public class Demo {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2); // capacity of 2
        
        cache.put(1, 1);    // cache: {1=1}
        cache.put(2, 2);    // cache: {1=1, 2=2}
        System.out.println(cache.get(1)); // returns 1, updates order: 2,1
        
        cache.put(3, 3);    // evicts key 2, cache: {1=1, 3=3}
        System.out.println(cache.get(2)); // returns -1 (not found)
        
        cache.put(4, 4);    // evicts key 1, cache: {3=3, 4=4}
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 3
        System.out.println(cache.get(4)); // 4
    }
}

Key Files in the kdn251/interviews Repository

The LRU cache implementation builds upon patterns demonstrated in these existing files:

• company/google/InsertDeleteGetRandomO1.java – Demonstrates O(1) insertion and deletion using a HashMap to store references, the same pattern used for key lookup in the LRU cache.
• company/bloomberg/MinStack.java – Uses a custom linked node to maintain auxiliary state (the current minimum) in O(1), providing the node-based approach used for the doubly-linked list in the LRU cache.

Summary

• An LRU Cache requires O(1) time complexity for get, put, and eviction operations to handle high-throughput scenarios efficiently.
• The implementation combines a HashMap (for constant-time key-to-node mapping) with a doubly-linked list (for usage order tracking).
• Sentinel nodes (dummy head and tail) eliminate null checks and simplify pointer manipulation logic.
• All operations involve only pointer updates via detach and insertAfterHead, ensuring constant time complexity.
• The kdn251/interviews repository provides foundational examples in InsertDeleteGetRandomO1.java and MinStack.java that demonstrate the HashMap and linked-node patterns essential to this design.

Frequently Asked Questions

Why is a doubly linked list necessary for O(1) LRU operations?

A singly linked list requires O(n) time to remove a node because you must traverse from the head to find the previous node. A doubly linked list stores both next and prev pointers, allowing O(1) removal when you have a direct reference to the node, which is exactly what the HashMap provides.

Can I use Java's LinkedHashMap to implement an LRU Cache?

Yes. Java's LinkedHashMap supports access-order iteration and can function as an LRU cache when constructed with accessOrder=true and by overriding removeEldestEntry(). However, implementing the cache manually using a HashMap and doubly-linked list demonstrates the underlying mechanics required in coding interviews and provides full control over the data structure.

What is the space complexity of this LRU Cache implementation?

The space complexity is O(capacity) because the HashMap stores at most capacity key-node pairs, and the doubly-linked list contains exactly the same number of nodes. Both structures grow linearly with the cache size, not with the number of operations performed.

How does the eviction policy handle updates to existing keys?

When put is called with an existing key, the implementation updates the node's value and moves it to the front of the doubly-linked list (the MRU position) using detach and insertAfterHead. This ensures the access order is correctly maintained and the updated entry is not incorrectly evicted due to being marked as least-recently used.

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