LRU cache (design + code) — Coding Round Practice (DSA in C#)

9. LRU cache (design + code)

AdvancedMediumLesson 9 of 14

Least Recently Used cache with O(1) Get and Put: a Dictionary for lookup + a doubly linked list for recency order.

csharp

public class LruCache<TKey, TValue>(int capacity) where TKey : notnull
{
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _map = new();
    private readonly LinkedList<(TKey Key, TValue Value)> _list = new();   // front = most recent

    public bool TryGet(TKey key, out TValue value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            _list.Remove(node); _list.AddFirst(node);
            value = node.Value.Value; return true;
        }
        value = default!; return false;
    }

    public void Put(TKey key, TValue value)
    {
        if (_map.TryGetValue(key, out var existing)) _list.Remove(existing);
        else if (_map.Count == capacity) { _map.Remove(_list.Last!.Value.Key); _list.RemoveLast(); }
        _map[key] = _list.AddFirst((key, value));
    }
}