Write a simple fixed-capacity LRU cache in C#.

Implement LruCache<TKey, TValue> with Get and Put. Get returns true when the key exists and moves it to most recently used. Put inserts or updates and evicts the least recently used key when capacity is exceeded.

Capacity 2: put A, put B, get A, put C. Key B is evicted because A was recently used and C is new.

• Capacity must be positive.
• Get moves an existing key to most recently used.
• Put existing key updates value and moves it to most recently used.
• Put new key over capacity evicts least recently used.

I would combine a dictionary for O(1) key lookup with a linked list for recency order. The front of the list is most recent and the back is least recent. The dictionary maps keys to linked-list nodes. On get or update, I move the node to the front. On insert over capacity, I remove the last node and remove its key from the dictionary.

public sealed class LruCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<Entry>> _nodes = new();
    private readonly LinkedList<Entry> _order = new();

    public LruCache(int capacity)
    {
        if (capacity <= 0) throw new ArgumentOutOfRangeException(nameof(capacity));
        _capacity = capacity;
    }

    public bool TryGet(TKey key, out TValue value)
    {
        if (!_nodes.TryGetValue(key, out var node))
        {
            value = default!;
            return false;
        }

        _order.Remove(node);
        _order.AddFirst(node);
        value = node.Value.Value;
        return true;
    }

    public void Put(TKey key, TValue value)
    {
        if (_nodes.TryGetValue(key, out var existing))
        {
            existing.Value = new Entry(key, value);
            _order.Remove(existing);
            _order.AddFirst(existing);
            return;
        }

        var node = new LinkedListNode<Entry>(new Entry(key, value));
        _order.AddFirst(node);
        _nodes[key] = node;

        if (_nodes.Count > _capacity)
        {
            var last = _order.Last!;
            _order.RemoveLast();
            _nodes.Remove(last.Value.Key);
        }
    }

    private sealed record Entry(TKey Key, TValue Value);
}

Get and put are O(1) average time because dictionary lookup and linked-list node moves are constant time. Space is O(capacity).

• Capacity of 1.
• Get missing key.
• Put existing key.
• Evict after a get changed recency.
• Reference or nullable values depending on TValue.

• Use capacity 1 to catch eviction mistakes.
• Update an existing key and verify count does not grow.
• Get a key before inserting another to verify recency updates.

• Using only a list and making get O(n).
• Forgetting to remove evicted keys from the dictionary.
• Not moving keys on get.
• Growing beyond capacity when updating existing keys.