LRU Cache

A fixed-capacity cache that guarantees O(1) access and eviction by combining a HashMap for lookup with a doubly linked list for usage ordering.

Algorithms

Context

An LRU (Least Recently Used) Cache is a fixed-capacity data structure designed to retain the most recently accessed items while evicting the least recently used ones.

It achieves O(1) time complexity for both retrieval and updates by combining:

A HashMap for constant-time key → node lookup.
A Doubly Linked List for maintaining usage order.

The list encodes recency:

Head → most recently used
Tail → least recently used

Whenever a key is accessed or updated, its node is moved to the head. When capacity is exceeded, the tail is evicted.

The key insight is structural separation:

The HashMap provides speed.
The linked list preserves order.

Neither structure alone can satisfy both constraints.

Core idea

To guarantee constant-time operations:

Store (key → node) mappings in a HashMap.
Store nodes in a doubly linked list ordered by recency.
On get or put of an existing key:
- Move the node to the head (mark as most recently used).
On inserting into a full cache:
- Remove the tail (least recently used).
- Delete its key from the map.
Maintain strict invariants:
- head always points to MRU.
- tail always points to LRU.
- Map and list must stay consistent.

This design ensures:

Lookup → O(1)
Update → O(1)
Eviction → O(1)

The entire structure is an exercise in maintaining invariants under mutation.

Implementation

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

class LRUCache<K, V> {
    private final int capacity;
    private Node<K, V> head;
    private Node<K, V> tail;
    private final Map<K, Node<K, V>> lookup = new HashMap<>();
    private int size;

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("Capacity must be positive");
        this.capacity = capacity;
    }

    public void put(K key, V value) {
        assertNotNull(key);

        var node = lookup.get(key);

        if (node != null) {
            node.value = value;
            detach(node);
            prepend(node);
        } else {
            if (isFull()) evict();
            var newNode = new Node<>(key, value);
            prepend(newNode);
            lookup.put(key, newNode);
            size++;
        }
    }

    public V get(K key) {
        assertNotNull(key);

        var node = lookup.get(key);
        if (node == null) return null;

        detach(node);
        prepend(node);

        return node.value;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }

    private void evict() {
        lookup.remove(tail.key);
        detach(tail);
        size--;
    }

    private void prepend(Node<K, V> node) {
        if (head == null) {
            head = tail = node;
        } else {
            head.prev = node;
            node.next = head;
            head = node;
        }
    }

    private void detach(Node<K, V> node) {
        if (node.prev != null) node.prev.next = node.next;
        if (node.next != null) node.next.prev = node.prev;

        if (node == head) head = node.next;
        if (node == tail) tail = node.prev;

        node.prev = node.next = null;
    }

    private void assertNotNull(K key) {
        if (key == null) throw new NullPointerException();
    }

    private static class Node<K, V> {
        private final K key;
        private V value;
        private Node<K, V> next;
        private Node<K, V> prev;

        private Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}