Blog

Linked Lists in C#: Nodes, Sentinels and Classic Problems

A linked list removes a node you hold in O(1) but pays for a separate object per element: 100,000 ints take 400 KB in a List and 4.8 MB in a LinkedList<int>, and walking 1 million scattered nodes is 259 times slower than a List. We write singly and doubly linked lists with sentinels, in-place reverse, Floyd's cycle detection, the middle node and a sorted merge, all with xUnit tests.