LRU Cache

A dictionary finds a key's node in O(1); a doubly linked list keeps the nodes in recency order, so moving a node to the front and evicting from the back are O(1) too.

The idea

Keep every cached entry in a doubly linked list ordered by recency: the node right after head was used most recently, the node right before tail least recently. Any get or put that touches a key moves its node to the front; a put into a full cache evicts the node before tail. The dictionary maps a key straight to its node, and because each node knows both neighbours it can be unlinked in O(1) without walking the list.

Code

public class LRUCache {
    class Node { public int Key, Val; public Node Prev, Next; }
    readonly int cap;
    readonly Dictionary<int, Node> map = new();
    readonly Node head = new(), tail = new(); // sentinels: head.Next is the most recent

    public LRUCache(int capacity) { cap = capacity; head.Next = tail; tail.Prev = head; }

    public int Get(int key) {
        if (!map.TryGetValue(key, out var node)) return -1;
        MoveToFront(node); // it was just used
        return node.Val;
    }

    public void Put(int key, int value) {
        if (map.TryGetValue(key, out var node)) { node.Val = value; MoveToFront(node); return; }
        if (map.Count == cap) { var lru = tail.Prev; Unlink(lru); map.Remove(lru.Key); }
        node = new Node { Key = key, Val = value };
        map[key] = node;
        AddFront(node);
    }

    void MoveToFront(Node n) { Unlink(n); AddFront(n); }
    void Unlink(Node n) { n.Prev.Next = n.Next; n.Next.Prev = n.Prev; }
    void AddFront(Node n) { n.Next = head.Next; n.Prev = head; head.Next.Prev = n; head.Next = n; }
}

Tips

• The list must be doubly linked: unlinking a node needs its previous node, and a singly linked list would have to walk to find it.
• The head and tail sentinels mean the list is never empty, so AddFront and Unlink need no null checks.
• Store the key inside the node too: on eviction you only have the node (tail.Prev) and need its key to remove it from the dictionary.

In the .NET library

.NET has LinkedList<T> with LinkedListNode<T>, so Dictionary<int, LinkedListNode<(int key, int val)>> plus list.Remove(node) and list.AddFirst(node) gives the same O(1) cache without writing Node by hand.