Data Structures Pattern: LRU Cache

I’ve been working through LeetCode patterns in a little C# repo, one pattern at a time, and this one is different from the others. Sliding window, two pointers, BFS/DFS — those are all about traversing a data structure that already exists. This pattern is about building one, when the ones you’re handed off the shelf don’t quite fit the job.

The pattern: when neither a hashmap nor a linked list is enough alone

The setup shows up over and over in interviews: “design a data structure that supports X and Y, both in O(1).” A plain array gives you O(1) access by index but O(n) insert/remove in the middle. A plain hashmap gives you O(1) lookup but no sense of order — no way to cheaply say “which entry hasn’t been touched in the longest time.” A plain linked list gives you O(1) insert/remove once you’re holding the node, but O(n) just to find that node in the first place.

The trick is combining two of them: a hashmap for O(1) lookup pointing directly at linked-list nodes for O(1) reordering. The hashmap tells you where something is instantly; the linked list lets you move it, delete it, or reinsert it without shifting anything else around it. Once that clicks, a whole family of “design a cache / design a data structure with eviction” problems stop being scary — they’re all this same combination wearing different clothes.

The canonical example, and the one I used to actually internalize it, is LeetCode 146: LRU Cache.

The problem

Design a cache with a fixed capacity that supports two operations, both in O(1) average time:

• Get(key) — return the value if the key exists, otherwise -1. If it exists, treat it as just-used.
• Put(key, value) — insert or update the value for a key. If this pushes the cache over capacity, evict the least recently used entry first.

“Recently used” means either operation touched it — a Get counts as a use, not just a Put. So the cache needs to track usage order and update it on every single operation, without ever scanning the whole thing.

Code walkthrough

Here’s the actual implementation from my repo (DataStructures/LruCache.cs, trimmed of using/namespace lines):

public class Node
{
    public int key;
    public int value;
    public Node prev;
    public Node next;

    public Node(int key, int value)
    {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {

    private readonly Dictionary<int, Node> map;
    private readonly int _capacity;

    private readonly Node _head;
    private readonly Node _tail;

    public LRUCache(int capacity) {
        this._capacity = capacity;
        map = new Dictionary<int, Node>();

        _head = new Node(-1, -1);
        _tail = new Node(-1, -1);

        _head.next = _tail;
        _tail.prev = _head;
    }

    // Add node right after head
    private void AddNode(Node node)
    {
        node.next = _head.next;
        node.prev = _head;

        _head.next.prev = node;
        _head.next = node;
    }

    // Remove node from DLL
    private void DeleteNode(Node node)
    {
        Node prevNode = node.prev;
        Node nextNode = node.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    public int Get(int key) {
        if (!map.TryGetValue(key, out Node? node))
            return -1;

        DeleteNode(node);
        AddNode(node);

        return node.value;
    }

    public void Put(int key, int value) {
        // Key already exists
        if (map.TryGetValue(key, out Node? existingNode))
        {
            existingNode.value = value;

            DeleteNode(existingNode);
            AddNode(existingNode);
        }
        else
        {
            // Cache full
            if (map.Count == _capacity)
            {
                Node lru = _tail.prev;

                DeleteNode(lru);
                map.Remove(lru.key);
            }

            Node newNode = new Node(key, value);

            AddNode(newNode);
            map[key] = newNode;
        }
    }
}

A few things worth calling out:

The sentinel _head/_tail nodes are the whole trick to keeping this code simple. Without them, AddNode and DeleteNode would need special-case branches for “the list is empty,” “we’re adding at the very front,” “we’re removing the last real node,” and so on — every one of those is a null-check waiting to be forgotten. With two dummy nodes wired together (_head.next = _tail, _tail.prev = _head) at construction time, the list is never actually empty from the code’s point of view. There’s always a real prev and a real next to rewire, no matter which node you’re touching. Most-recently-used lives right after _head; least-recently-used lives right before _tail.

AddNode and DeleteNode are the only two primitives that touch pointers. Everything else — Get, Put, eviction — is built by composing these two: to “move a node to the front,” you DeleteNode it from wherever it is, then AddNode it back right after _head. There’s no separate “move” function because there doesn’t need to be one.

Get promotes on read. If the key exists, it deletes the node from its current position and re-adds it at the front — that’s the “this was just used” signal. If it doesn’t exist, it bails out with -1 before touching the list at all.

Put evicts from the tail, not the head. When the map is already at _capacity and the key is new, it grabs _tail.prev — the actual least-recently-used node, not a stand-in — deletes it from the list and removes it from the map (skipping the map removal here would leak a stale entry that no longer points anywhere in the list), then inserts the new node at the front.

Complexity: Get and Put are both O(1) — dictionary lookup is O(1) average, and AddNode/DeleteNode only ever touch a fixed number of pointers regardless of list size. Space is O(capacity), since the map and list never hold more than capacity entries at once.

Try it

Here’s a capacity-3 cache running a fixed sequence of operations: put(1,A), put(2,B), put(3,C), get(1), put(4,D). Watch how get(1) promotes key 1 to the front even though it doesn’t change its value, and how put(4,D) evicts key 2 — not key 1, even though 1 was inserted before 2 — because key 1 was the one touched most recently.

Blue = node just touched, moving to the front (most recently used). Red = about to be evicted (least recently used, cache was full). Green flash = just landed at the front.

Takeaways

The big idea isn’t really about caches specifically — it’s that when a problem demands two different O(1) capabilities that no single built-in structure gives you both of, look for a pair that covers each other’s weak spot. Hashmap for “find it instantly,” linked list for “reorder it instantly,” sentinels so the edges of the list don’t need special-casing. Once I had that combination in my head, a handful of other “design X with these constraints” problems (LFU cache, browser history, that kind of thing) stopped feeling like new problems and started feeling like the same two Lego pieces snapped together differently.