What is a linked list? Compare LinkedList<T> with List<T> in .NET, including big-O and real-world performance, and give a case where a linked list is the right choice.

1. Operations on a doubly linked list

Remove B (holding node B):
   A.next = C;  C.prev = A;          O(1), no shifting

   [A] ⇄ [B] ⇄ [C]   ──►   [A] ⇄ [C]

Insert X after A:
   X.prev = A; X.next = A.next; A.next.prev = X; A.next = X;

Compare with List<T>.RemoveAt(1), which copies every later element one slot left.

2. Why it is slower than it looks

Array scan:        [A][B][C][D][E][F][G][H]   one cache line → many elements
Linked list scan:  [A]────────►[B]───►[C]──────────►[D]  each hop likely a cache miss

The CPU's prefetcher cannot predict the next address because it is stored in the current node. That makes linked lists latency-bound on memory. Nodes allocated together may sit close at first, but after the GC compacts and the list is reordered, they scatter.

3. The LinkedList<T> API

• AddFirst, AddLast, AddBefore(node, value), AddAfter, Remove(node), RemoveFirst, RemoveLast: O(1).
• Find(value), Contains(value) and Remove(value): O(n), because they walk the list.
• A node belongs to exactly one list; adding it to another throws InvalidOperationException.
• Not thread-safe: concurrent writers corrupt the links. Guard it with a lock (as an LRU cache would), or use concurrent collections such as ConcurrentQueue<T> when you only need FIFO.

4. Where linked structures appear

• LRU caches (recency list + dictionary).
• Free lists in allocators and object pools.
• Undo/redo histories with cursor movement.
• Lock-free queues and stacks: ConcurrentStack<T> uses linked nodes; ConcurrentQueue<T> uses linked segments of arrays, a hybrid that keeps locality.
• Hash table collision chains: in .NET's Dictionary<TKey, TValue>, chains are indices inside an entries array, not separate node objects.

5. Classic interview operations

6. Try it yourself

1. Benchmark summing 1 million ints in List<int> versus LinkedList<int>.
2. Benchmark 100,000 removals from the front of each.
3. Implement an LRU cache with capacity 3 and test the eviction order.
4. Implement singly linked list reversal and cycle detection.

// LRU cache: O(1) get, put and eviction
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(); // First = most recent

    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);    // O(1)
            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!;
            _order.RemoveLast();      // evict least recently used
            _map.Remove(lru.Value.Key);
        }
        _map[key] = _order.AddFirst((key, value));
    }
}

// Reverse a singly linked list in place
public sealed class Node(int value) { public int Value = value; public Node? Next; }

public static Node? Reverse(Node? head)
{
    Node? prev = null;
    while (head is not null)
    {
        var next = head.Next;
        head.Next = prev;
        prev = head;
        head = next;
    }
    return prev;
}