Playful Cloud

A minimal blog

Building an LRU Cache

What This Is

I was working through the LRU Cache problem on NeetCode and, after a while, the solution finally clicked. Java has LinkedHashMap which handles all of this for you, but I wanted to understand what was actually happening underneath before reaching for that. So I built it from scratch with a hashmap and a doubly linked list.

This is a walkthrough of how that implementation works and why it is put together the way it is.

The constraint the problem sets is that both get and put must run in O(1) time. LRU means: when the cache is full and a new item comes in, evict the item that has not been accessed in the longest time. Implementing that in constant time is the interesting part.

class LRUCache {

    private int capacity;
    private Map<Integer, Node> cache;

    // left = LRU, right = most recently used
    // dummy nodes to avoid null checks
    private Node left;
    private Node right;

    public LRUCache(int capacity){
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.left = new Node(0, 0);
        this.right = new Node(0, 0);

        // connect the dummy nodes
        this.left.next = this.right;
        this.right.prev = this.left;
    }

    private void remove(Node node){
        Node leftNode = node.prev;
        Node rightNode = node.next;
        leftNode.next = rightNode;
        rightNode.prev = leftNode;
    }

    private void insert(Node node){
        Node mru = this.right.prev;
        mru.next = node;
        node.prev = mru;
        node.next = this.right;
        this.right.prev = node;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            remove(node);
            insert(node);
            return node.val;
        }

        return -1;
    }

    public void put(int key, int value){
        if (cache.containsKey(key)) remove(cache.get(key));

        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        insert(newNode);

        if (cache.size() > capacity){
            Node lru = this.left.next;
            remove(lru);
            cache.remove(lru.key);
        }
    }
}

The Data Structure

The doubly linked list maintains access order. The left end is the least recently used item. The right end is the most recently used item. Every time an item is accessed, it moves to the right end. When the cache is full and something needs to go, you remove from the left.

The hashmap gives you direct access to any node in the list by key, without traversal. Without it, finding a node to move would require walking the list — O(n). With it, any lookup is O(1).

private int capacity;
private Map<Integer, Node> cache;

// left = LRU, right = most recently used
private Node left;
private Node right;

The two extra nodes, left and right, are dummy sentinels. They sit at either end of the list and never hold real data. Their only job is to eliminate null checks. Without them, every insert and remove would need to handle the case of operating at the start or end of a real list. With them, every operation is always somewhere in the middle of the list, between two valid nodes.

this.left = new Node(0, 0);
this.right = new Node(0, 0);

// left dummy <-> right dummy
this.left.next = this.right;
this.right.prev = this.left;

At the start, the list is just two sentinels connected to each other. As items are inserted, real nodes appear between them.

Every real node sits somewhere in this arrangement:

left <-> node <-> right

And two relationships always hold. A node’s prev is the same as left.next from that node’s perspective — it points toward the LRU end. A node’s next is the same as right.prev — it points toward the MRU end. This invariant is what makes both eviction and promotion straightforward: the LRU is always left.next, and the MRU position is always just before right.


Removing a Node

Removing a node means relinking its neighbors around it. The node’s left neighbor should point forward to the node’s right neighbor, and the right neighbor should point back to the left neighbor. The node being removed becomes disconnected from the list.

private void remove(Node node) {
    Node leftNode = node.prev;  // get the left node of the node to be removed
    Node rightNode = node.next; // get the right node of the node to be removed
    leftNode.next = rightNode;  // connect the left node to the right node
    rightNode.prev = leftNode;  // connect the right node back to the left node
}

Because of the sentinel nodes, this always works. There is no special case for removing the first or last real element. Every real node always has a valid prev and next — at worst, they point to the sentinels.


Inserting a Node

Inserting always happens at the right end, immediately to the left of the right sentinel. That position represents “most recently used.”

private void insert(Node node) {
    Node mru = this.right.prev; // the current most recently used node
    mru.next = node;            // current most recent now points forward to the new node
    node.prev = mru;            // new node points back to current most recent
    node.next = this.right;     // new node points forward to the right sentinel
    this.right.prev = node;     // right sentinel points back to the new node
}

Four pointer updates. After these four lines, the new node sits between whatever was previously most recently used and the right sentinel.


Get

Getting a value from the cache is more than a lookup. If the key exists, the corresponding node needs to move to the most recently used position — because accessing it makes it the most recently used item.

public int get(int key) {
    if (cache.containsKey(key)) {
        Node node = cache.get(key);
        remove(node);
        insert(node);
        return node.val;
    }

    return -1;
}

Remove it from its current position, insert it at the right end, return the value. If the key is not in the cache, return -1.


Put

Inserting a new key-value pair has a few cases to handle.

If the key already exists in the cache, the old node needs to come out before the new one goes in. The hashmap will be overwritten anyway, but the old node is still sitting in the list taking up space.

After inserting the new node, if the cache has exceeded its capacity, the least recently used item needs to be evicted. That item is always immediately to the right of the left sentinel.

public void put(int key, int value) {
    if (cache.containsKey(key)) remove(cache.get(key));
    // if the key already exists, remove it from its current position

    Node newNode = new Node(key, value);
    cache.put(key, newNode);
    insert(newNode);
    // insert the new node at the most recently used position

    if (cache.size() > capacity) {
        Node lru = this.left.next; // the node right after the left sentinel is the LRU
        remove(lru);               // remove it from the list
        cache.remove(lru.key);     // remove it from the hashmap using its key
    }
}

One detail worth noticing: the Node stores its own key alongside its value. This is necessary because when you evict the LRU node from the list, you need its key to remove it from the hashmap. Without storing the key in the node, you would have no way to know what to delete.


Why It Works

Every operation — get and put — is O(1). The hashmap gives you direct access to any node in constant time. The linked list insertions and removals each touch a fixed number of pointers regardless of how large the cache is.

The access order maintenance is free. Moving a node to the most recently used position is just a remove followed by an insert, both constant time. And eviction is free: the least recently used item is always exactly one step from the left sentinel.

The two structures do different jobs. The hashmap answers “does this key exist, and where is it?” The linked list answers “in what order were things accessed, and which one is oldest?” Neither structure alone can do both jobs in constant time. Together, they can.