When would you use LinkedList<T> in C#? Explain how it is implemented, the LinkedListNode<T> API (AddBefore, AddAfter, Remove(node)), its real costs compared with List<T>, and the classic LRU cache that combines it with a Dictionary.

1. Node layout and memory

public sealed class LinkedListNode<T>
{
    internal LinkedList<T>? list;
    internal LinkedListNode<T>? next;
    internal LinkedListNode<T>? prev;
    internal T item;
}

On 64-bit: 16 bytes of object header + MethodTable, three 8-byte references, plus T (8 bytes for a reference, padded). That's ~48 bytes per node for LinkedList<int> — versus 4 bytes per element in List<int>. For a million elements, ~48 MB vs ~4 MB, plus a million objects for the GC to trace.

2. Why linked lists are cache-unfriendly

CPUs load memory in 64-byte cache lines and prefetch sequential addresses. Traversing a List<T> walks contiguous memory, so the prefetcher keeps data ready. Traversing a linked list follows next pointers to arbitrary addresses — each hop can be a cache miss (~100 ns from DRAM). Nodes allocated close together initially may be adjacent, but after the GC compacts and the list is reordered, locality degrades.

This is why Bjarne Stroustrup's well-known benchmark showed vectors beating linked lists even for middle insertion: finding the position (a linear scan) dominates, and scanning arrays is far faster.

3. The circular design

.NET's LinkedList<T> keeps only head; head.prev is the tail. AddLast(x) is "insert before head" (because the list is circular), and Last returns head.prev. The public Next/Previous properties return null at the ends even though the internal links wrap — the property getters hide the circularity.

4. Version checks and safe removal during iteration

LinkedList<T> has a version field and its enumerator throws if the list is modified during foreach. But you can traverse manually and modify safely:

for (var node = list.First; node is not null; )
{
    var next = node.Next;          // save before removal
    if (ShouldRemove(node.Value)) list.Remove(node);
    node = next;
}

5. LRU cache analysis

Performance refinements:

• Reuse the evicted node instead of allocating a new one (update its value, move it to the front).
• Store (Key, Value) in the node so eviction can remove the dictionary entry without a reverse lookup.
• For high concurrency, a single lock becomes a bottleneck: use striped/sharded caches (N independent LRUs keyed by hash), or approximate LRU like CLOCK or W-TinyLFU (as in the BitFaster.Caching library), which avoid moving entries on every hit.
• An array-based variant (nodes as indexes into struct arrays) avoids per-node objects entirely.

6. IMemoryCache and HybridCache

Microsoft.Extensions.Caching.Memory.MemoryCache:

• Supports absolute and sliding expiration, priorities, and SizeLimit with per-entry Size.
• When over the size limit, it compacts asynchronously, removing expired entries, then low-priority and least-recently-used ones — approximately LRU, not strict.
• Thread-safe.

HybridCache (.NET 9) layers an in-memory cache over a distributed cache (Redis) with stampede protection (only one caller computes a missing value). For most service caching needs, these are better than a custom LRU.

7. Alternatives to LinkedList<T>

• Deque needs (add/remove at both ends): a circular buffer (e.g. implement one over an array, or use Queue<T> for one end).
• Ordered with fast insert: SortedSet<T>/SortedDictionary.
• Frequent middle edits on text: rope or gap-buffer structures.
• Intrusive lists: storing Next/Prev in your own objects (e.g. pooled objects) avoids separate node allocations.

Try it yourself

1. Benchmark iterating and summing 1 million ints in List<int> vs LinkedList<int>.
2. Benchmark inserting 10,000 items in the middle of each — including the time to find the insertion point.
3. Implement the LRU cache, add node reuse on eviction, and test eviction order.
4. Compare your LRU with IMemoryCache configured with SizeLimit under a load test.

public sealed class LruCache<TKey, TValue>(int capacity) where TKey : notnull
{
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _map = new(capacity);
    private readonly LinkedList<(TKey Key, TValue Value)> _order = new();

    public bool TryGet(TKey key, out TValue value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            _order.Remove(node);        // O(1): we hold the node
            _order.AddFirst(node);      // reuse the node, no allocation
            value = node.Value.Value;
            return true;
        }
        value = default!;
        return false;
    }

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

// Usage
var cache = new LruCache<string, byte[]>(capacity: 3);
cache.Put("a", [1]); cache.Put("b", [2]); cache.Put("c", [3]);
cache.TryGet("a", out _);   // order now a, c, b
cache.Put("d", [4]);        // evicts b