Introduction

A SortedDictionary<TKey, TValue> in C# sorts by key, not by value, and that makes it a poor fit for implementing an LRU cache. An LRU cache needs to track recency of use, which changes every time an entry is read or written. The standard solution is a dictionary for fast lookup plus a linked list for usage order.

Why SortedDictionary Is the Wrong Tool

SortedDictionary<TKey, TValue> maintains entries according to key ordering. Even if you store a timestamp or usage counter as the value, the collection still does not reorder itself by that value. You would need extra work to remove and reinsert items or maintain a second structure.

That is already a sign the design is off. LRU eviction is not a sorted-by-value problem. It is an update-recency problem.

What you really need is:

• 'O(1) lookup by key'
• 'O(1) promotion of an accessed item to most-recently-used'
• 'O(1) eviction of the least-recently-used item'

A hash map plus doubly linked list gives exactly that.

The Standard LRU Design in C#

Use:

• 'Dictionary<TKey, LinkedListNode<CacheItem>> for key lookup'
• 'LinkedList<CacheItem> to keep most-recently-used items at the front and least-recently-used at the back'

1using System;
2using System.Collections.Generic;
3
4public class LruCache<TKey, TValue>
5{
6    private readonly int capacity;
7    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> map;
8    private readonly LinkedList<(TKey Key, TValue Value)> usage;
9
10    public LruCache(int capacity)
11    {
12        this.capacity = capacity;
13        map = new Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>>();
14        usage = new LinkedList<(TKey Key, TValue Value)>();
15    }
16
17    public bool TryGet(TKey key, out TValue value)
18    {
19        if (!map.TryGetValue(key, out var node))
20        {
21            value = default!;
22            return false;
23        }
24
25        usage.Remove(node);
26        usage.AddFirst(node);
27        value = node.Value.Value;
28        return true;
29    }
30
31    public void Put(TKey key, TValue value)
32    {
33        if (map.TryGetValue(key, out var existing))
34        {
35            usage.Remove(existing);
36        }
37        else if (map.Count >= capacity)
38        {
39            var lru = usage.Last!;
40            usage.RemoveLast();
41            map.Remove(lru.Value.Key);
42        }
43
44        var node = new LinkedListNode<(TKey Key, TValue Value)>((key, value));
45        usage.AddFirst(node);
46        map[key] = node;
47    }
48}

This design gives the behavior people usually want when they ask about an LRU cache.

Why Recency Needs a Linked Structure

When an item is accessed, it becomes the most recently used item. That means the data structure must support fast movement from the middle of the usage order to the front. A linked list is a natural fit because a node can be removed and reinserted without shifting the rest of the collection.

A sorted structure does not model that semantics naturally. Usage order changes based on reads, not based on a stable sort key.

Add a Small Usage Example

1var cache = new LruCache<string, int>(2);
2cache.Put("a", 1);
3cache.Put("b", 2);
4cache.TryGet("a", out _);   // "a" becomes most recently used
5cache.Put("c", 3);          // evicts "b"
6
7Console.WriteLine(cache.TryGet("b", out _)); // False
8Console.WriteLine(cache.TryGet("a", out var a)); // True
9Console.WriteLine(a); // 1

After reading a, the cache treats b as the least recently used entry, so b is evicted when c is inserted.

When a Sorted Structure Does Help

A sorted collection can still be useful for other cache policies, such as evicting the earliest expiration time or ranking by score. That is a different problem. If the cache is time-based, priority-based, or size-based, the right structure may change.

For a true LRU cache, however, dictionary plus linked list remains the standard answer.

Common Pitfalls

• Expecting SortedDictionary<TKey, TValue> to sort by value rather than by key.
• Trying to model recency with a sorted value when recency changes on every access.
• Using a list without storing linked-list nodes, which makes promotions slower than necessary.
• Forgetting to update the usage order on reads as well as writes.
• Mixing LRU semantics with TTL or priority-eviction semantics in the same structure without clear rules.

Summary

• 'SortedDictionary is not the right structure for an LRU cache because it sorts by key, not by recency.'
• LRU requires fast lookup, fast promotion on access, and fast eviction of the oldest entry.
• The standard implementation uses a dictionary plus a linked list.
• Access operations must update usage order, not just insertion operations.
• Use sorted collections only when the cache policy is based on a stable ordering such as expiration or priority.