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

Implement a single-threaded LruCache<TKey, TValue> with TryGet and Put. A hit becomes most recently used; insertion over capacity evicts the least recently used key. Thread safety is outside this exercise.

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.
• The cache is used by one thread; concurrent access is outside the contract.
• 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 combine a dictionary for O(1) key lookup with a linked list for recency order. The front is most recent and the back is least recent. The dictionary maps keys to linked-list nodes, so a hit or update can move one node without searching. Insertion over capacity removes the last node from both structures. This implementation assumes a single caller at a time; adding a concurrent dictionary alone would not make the linked-list updates atomic.

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);
}

Under the stated single-threaded contract, get and put are O(1) average time because dictionary lookup and linked-list node moves are constant time. Space is O(capacity). Supporting concurrent callers would require synchronization around both structures and a separate contention discussion.

• 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.
• Presenting the dictionary-plus-linked-list implementation as thread-safe without synchronizing their combined mutations.