Mastering LRU Cache: O(1) Implementation with Hash‑Linked List in Java

Introduction

Cache capacity is limited; when it is full we must evict some entries to make room for new data. The LRU (Least Recently Used) algorithm assumes that recently accessed items are useful, while items not used for a long time can be removed.

Algorithm Description

Design and implement an LRU (Least Recently Used) cache mechanism with the following API:

LRUCache(int capacity) – initialize the cache with a positive integer capacity.

int get(int key) – return the value associated with key if it exists; otherwise return -1.

void put(int key, int value) – insert or update the key‑value pair; if the cache is full, evict the least recently used entry before inserting.

Note: Both get and put must run in O(1) time complexity.

Example

/* Cache capacity is 2 */
LRUCache cache = new LRUCache(2);
cache.put(1, 1); // cache = [(1,1)]
cache.put(2, 2); // cache = [(2,2),(1,1)]
cache.get(1);    // returns 1, cache = [(1,1),(2,2)]
cache.put(3, 3); // evicts key 2, cache = [(3,3),(1,1)]
cache.get(2);    // returns -1 (not found)
cache.put(1, 4); // updates key 1, cache = [(1,4),(3,3)]

Design Analysis

To achieve O(1) operations we need a data structure that supports fast lookup, fast insertion/deletion, and maintains order. A hash table provides O(1) lookup but lacks order; a doubly linked list provides order and O(1) insertion/deletion but slow lookup. Combining them yields a "hash‑linked list".

The core structure consists of a doubly linked list (to keep elements ordered from most to least recent) and a hash map (to locate nodes by key quickly).

Code Implementation

Define a doubly linked node class that stores key, value, and pointers to previous and next nodes.

class DLinkedNode {
    int key;
    int value;
    DLinkedNode pre;
    DLinkedNode next;
    public DLinkedNode() {}
    public DLinkedNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

Helper methods for the linked list:

private void addFirst(DLinkedNode node) {
    node.pre = head;
    node.next = head.next;
    head.next.pre = node;
    head.next = node;
}
private void moveToFirst(DLinkedNode node) {
    remove(node);
    addFirst(node);
}
private void remove(DLinkedNode node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;
}
private DLinkedNode removeLast() {
    DLinkedNode ans = tail.pre;
    remove(ans);
    return ans;
}
private int getSize() { return size; }

LRUCache class fields and constructor:

private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;
    head = new DLinkedNode();
    tail = new DLinkedNode();
    head.next = tail;
    tail.pre = head;
}

Core methods:

public int get(int key) {
    DLinkedNode node = cache.get(key);
    if (node == null) return -1;
    moveToFirst(node);
    return node.value;
}
public void put(int key, int value) {
    DLinkedNode node = cache.get(key);
    if (node != null) {
        node.value = value;
        moveToFirst(node);
    } else {
        if (size == capacity) {
            DLinkedNode tail = removeLast();
            cache.remove(tail.key);
            --size;
        }
        DLinkedNode newNode = new DLinkedNode(key, value);
        cache.put(key, newNode);
        addFirst(newNode);
        ++size;
    }
}

Summary

The LRU cache combines a doubly linked list (for ordered access) with a hash table (for O(1) lookup).

Using a doubly linked list allows O(1) deletion of the least‑recently used node.

Storing both key and value in the list node is necessary to remove the corresponding entry from the hash map when evicting.