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

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

You are going to sum 1,000,000 order totals. The totals sit in three different structures: a List<int>, the BCL (Base Class Library) LinkedList<int> and a singly linked list of our own whose nodes are scattered randomly in memory. All three perform the same 1,000,000 additions and none of them allocates on the heap.

If the List takes 0.3 ms, how long does LinkedList<int> take? And the list with scattered nodes? A second question: keeping 100,000 ints in a List takes around 400 KB of memory. How many bytes do the same 100,000 ints take in a LinkedList<int>?

Nodes and the Singly Linked List

A linked list keeps elements not next to each other in memory but in separate nodes, each pointing to the next. Unlike an array, adding or removing an element does not shift anyone; changing two references is enough. The price is also the opposite of the array's: to reach the i-th element you walk i steps from the start, and there is no indexing.

namespace Algorithms.Linear;

public sealed class ListNode<T>(T value)
{
    public T Value { get; set; } = value;
    public ListNode<T>? Next { get; set; }
}

The singly linked list we build from these nodes keeps a sentinel node at the front:

using System.Collections;

namespace Algorithms.Linear;

public sealed class SinglyLinkedList<T> : IEnumerable<T>
{
    // sentinel: always exists, never holds data, so "empty list" and "first node" need no special case
    private readonly ListNode<T> _head = new(default!);
    private ListNode<T> _tail;

    public SinglyLinkedList() => _tail = _head;

    public int Count { get; private set; }
    public ListNode<T>? First => _head.Next;

    public void AddFirst(T value)
    {
        ListNode<T> node = new(value) { Next = _head.Next };
        _head.Next = node;
        if (_tail == _head) _tail = node;
        Count++;
    }

    public void AddLast(T value)
    {
        ListNode<T> node = new(value);
        _tail.Next = node;
        _tail = node;
        Count++;
    }

    public bool Remove(T value)
    {
        EqualityComparer<T> comparer = EqualityComparer<T>.Default;
        // walk with "previous" starting at the sentinel: removing the first node is not special
        for (ListNode<T> previous = _head; previous.Next is { } current; previous = current)
        {
            if (!comparer.Equals(current.Value, value)) continue;
            previous.Next = current.Next;
            if (current == _tail) _tail = previous;
            Count--;
            return true;
        }
        return false;
    }

    public void Reverse()
    {
        ListNode<T>? oldFirst = _head.Next;
        _head.Next = LinkedListProblems.Reverse(oldFirst);
        if (oldFirst is not null) _tail = oldFirst;
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (ListNode<T>? node = _head.Next; node is not null; node = node.Next)
            yield return node.Value;
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Removing Edge Cases with a Sentinel

Try writing Remove without a sentinel. If the first node goes, you must update _head; if a middle node goes, the previous node's Next. An empty list needs its own check, and a single-element list needs another to reset _tail to null. Most linked list bugs live in these branches: a _tail that breaks when the first or last element is removed, a NullReferenceException on an empty list.

A sentinel (dummy head) is a node that never holds data and is never removed. Every real node now has a predecessor; the first node's predecessor is the sentinel. Because the loop in Remove starts at previous = _head, removing the first node is the same two lines as removing one in the middle. An empty list is simply a list where _head.Next == null; it needs no special check. The cost is one extra node.

The tests target the two places that break most often: _tail staying in the right place after removing from the front, middle and end, and AddLast appending to the new end after a reverse:

[Fact]
public void SinglyRemove_FirstMiddleLast_KeepsListConsistent()
{
    SinglyLinkedList<string> list = new();
    foreach (string s in new[] { "a", "b", "c", "d" }) list.AddLast(s);

    Assert.True(list.Remove("a"));
    Assert.True(list.Remove("c"));
    Assert.True(list.Remove("d"));
    list.AddLast("e"); // tail must have moved back to "b"

    Assert.Equal(["b", "e"], list);
    Assert.Equal(2, list.Count);
}

[Fact]
public void SinglyReverse_ThenAddLast_UsesNewTail()
{
    SinglyLinkedList<int> list = new();
    foreach (int i in new[] { 1, 2, 3 }) list.AddLast(i);

    list.Reverse();
    list.AddLast(0);

    Assert.Equal([3, 2, 1, 0], list);
}

Doubly Linked List and a Circular Sentinel

In a singly linked list you need the previous node to remove a node; if all you hold is the node to remove, you have to search from the start. A doubly linked list also keeps Previous in every node and removes the node you hold in O(1). Make the sentinel circular, so that its Next points to the first node and its Previous to the last, and null checks disappear entirely:

using System.Collections;

namespace Algorithms.Linear;

public sealed class DoublyNode<T>(T value)
{
    public T Value { get; set; } = value;
    public DoublyNode<T> Previous { get; internal set; } = null!;
    public DoublyNode<T> Next { get; internal set; } = null!;
}

public sealed class DoublyLinkedList<T> : IEnumerable<T>
{
    // circular sentinel: sentinel.Next is the first node, sentinel.Previous is the last
    private readonly DoublyNode<T> _sentinel;

    public DoublyLinkedList()
    {
        _sentinel = new DoublyNode<T>(default!);
        _sentinel.Next = _sentinel.Previous = _sentinel;
    }

    public int Count { get; private set; }

    public DoublyNode<T> AddLast(T value) => InsertAfter(_sentinel.Previous, value);
    public DoublyNode<T> AddFirst(T value) => InsertAfter(_sentinel, value);

    private DoublyNode<T> InsertAfter(DoublyNode<T> previous, T value)
    {
        DoublyNode<T> node = new(value) { Previous = previous, Next = previous.Next };
        previous.Next.Previous = node;
        previous.Next = node;
        Count++;
        return node;
    }

    // O(1): the node knows both neighbours, no search needed
    public void Remove(DoublyNode<T> node)
    {
        node.Previous.Next = node.Next;
        node.Next.Previous = node.Previous;
        node.Next = node.Previous = null!;
        Count--;
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (DoublyNode<T> node = _sentinel.Next; node != _sentinel; node = node.Next)
            yield return node.Value;
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

AddFirst and AddLast call the same InsertAfter; the same four assignments run on an empty list and a full one. The BCL's LinkedList<T> is also doubly linked and circular: it keeps no separate sentinel, but the prev of the first node in its head field points to the last node. Every LinkedListNode<T> also keeps a reference to the list it belongs to, which is how you get an exception when you pass another list's node to Remove. Its API (Application Programming Interface) is in the C# Collections series post "C# Queue, Stack, LinkedList and PriorityQueue".

Classic Problems: Reverse, Cycle, Middle, Merge

Linked list problems teach you to change pointers in the right order. The first is the in-place reverse:

public static ListNode<T>? Reverse<T>(ListNode<T>? head)
{
    ListNode<T>? previous = null;
    ListNode<T>? current = head;
    while (current is not null)
    {
        ListNode<T>? next = current.Next; // save it first, or the rest of the list is lost
        current.Next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

Each step has three pointers: the head of the part already reversed (previous), the node being processed (current) and the head of the untouched part (next). Order matters: if you do not save next before changing current.Next, you lose the only reference to the rest of the list. That part is now garbage for the GC (Garbage Collector). O(n) time, O(1) extra memory.

The second is cycle detection. If, because of corrupt data or a wrong link, the last node's Next points to an earlier node in the list, every loop that walks the list runs forever. Floyd's algorithm finds it with two pointers and no extra memory: the slow one moves one node per step, the fast one two. Without a cycle the fast one reaches the end; with a cycle the fast one catches the slow one from behind inside the loop.

// Floyd: slow moves 1, fast moves 2; they meet only if there is a cycle
public static bool HasCycle<T>(ListNode<T>? head)
{
    ListNode<T>? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (ReferenceEquals(slow, fast)) return true;
    }
    return false;
}

public static ListNode<T>? CycleStart<T>(ListNode<T>? head)
{
    ListNode<T>? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (!ReferenceEquals(slow, fast)) continue;
        // restart one pointer from head; moving both by 1, they meet at the cycle start
        for (slow = head; !ReferenceEquals(slow, fast); slow = slow!.Next, fast = fast!.Next) { }
        return slow;
    }
    return null;
}

Why the second phase of CycleStart works takes a short calculation. Let a be the distance from the head to the start of the cycle, b the distance from the start of the cycle to the meeting point, and c the cycle length. At the meeting point the fast pointer has travelled twice as far as the slow one: 2(a + b) = a + b + kc, so a = kc − b. Walking a more steps from the meeting point lands on the start of the cycle. The same fast/slow idea also finds the middle node in a single pass: when the fast one reaches the end, the slow one is in the middle.

// for an even count returns the second of the two middle nodes
public static ListNode<T>? Middle<T>(ListNode<T>? head)
{
    ListNode<T>? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
    }
    return slow;
}

public static ListNode<int>? MergeSorted(ListNode<int>? a, ListNode<int>? b)
{
    ListNode<int> dummy = new(0);
    ListNode<int> tail = dummy;
    while (a is not null && b is not null)
    {
        // <= keeps equal values from "a" first: the merge is stable
        if (a.Value <= b.Value) { tail.Next = a; a = a.Next; }
        else { tail.Next = b; b = b.Next; }
        tail = tail.Next;
    }
    tail.Next = a ?? b;
    return dummy.Next;
}

MergeSorted is where the sentinel idea pays off once more: thanks to dummy there is no separate branch for "which node is the first node of the result?". It allocates no new nodes either; it relinks the existing ones. This method is the heart of the linked list version of merge sort in the series' sorting post. The tests build a cycle by hand (5 → 3) and check that the cycle's start node is the same instance:

[Fact]
public void HasCycle_TailPointsBack_DetectsCycleAndStart()
{
    ListNode<int> head = FromValues(1, 2, 3, 4, 5)!;
    ListNode<int> third = head.Next!.Next!;
    ListNode<int> last = third.Next!.Next!;
    last.Next = third; // 5 -> 3

    Assert.True(HasCycle(head));
    Assert.Same(third, CycleStart(head));
    Assert.False(HasCycle(FromValues(1, 2, 3)));
    Assert.Null(CycleStart(FromValues(1, 2, 3)));
}

[Fact]
public void MergeSorted_TwoSortedLists_ReturnsSortedList()
{
    ListNode<int>? merged = MergeSorted(FromValues(1, 4, 9), FromValues(2, 4, 10, 11));

    Assert.Equal([1, 2, 4, 4, 9, 10, 11], ToList(merged));
}

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.LinkedListTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (600ms)

Test run summary: Passed!
  total: 11
  failed: 0
  succeeded: 11

When Does a Linked List Lose?

On paper, iterating a linked list is O(n), just like an array. In practice it has two costs. The first is memory: every node is a separate object, so each element carries an object header, a method table pointer and the link references. A small program that adds 100,000 ints to both structures measures the allocated bytes with GC.GetAllocatedBytesForCurrentThread:

List<int>       100,000 items:      400,056 bytes (4.0 per item)
LinkedList<int> 100,000 items:    4,800,040 bytes (48.0 per item)

48 bytes for a 4-byte int. The 16-byte object header of LinkedListNode<T>, three 8-byte references for list, next and prev and the 4-byte value round up to 48 with alignment. The same data takes 12 times the memory, and on top of that 100,000 separate objects are 100,000 separate targets the GC has to trace on every scan.

The second cost is the cache. In an array the next element is at the next address; the processor predicts that and fetches it in advance. In a linked list the next node's address is only known once the current node is read (pointer chasing), and that address can be anywhere. The benchmark measures two kinds of linked list: nodes allocated in order (sitting next to each other), and nodes linked in shuffled order and spread out by allocating garbage between them. The second resembles a list that grew over time in a long-running process.

[GlobalSetup]
public void Setup()
{
    _list = [.. Enumerable.Range(0, N)];
    _linkedList = new LinkedList<int>(Enumerable.Range(0, N));
    _ownSequential = LinkedListProblems.FromValues([.. Enumerable.Range(0, N)])!;

    // same values, but nodes linked in a shuffled allocation order, with garbage between them:
    // the next node is usually far away in memory, like a list that grew over a long-running process
    ListNode<int>[] nodes = new ListNode<int>[N];
    for (int i = 0; i < N; i++)
    {
        nodes[i] = new ListNode<int>(i);
        _keepAlive.Add(new byte[48]);
    }
    Random.Shared.Shuffle(nodes);
    for (int i = 0; i < N - 1; i++) nodes[i].Next = nodes[i + 1];
    _ownScattered = nodes[0];
}

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method             | N       | Mean         | Ratio  | Allocated |
|------------------- |-------- |-------------:|-------:|----------:|
| ListOfInt          | 100000  |     31.68 us |   1.00 |         - |
| BclLinkedList      | 100000  |     89.89 us |   2.84 |         - |
| OwnSequentialNodes | 100000  |     81.86 us |   2.58 |         - |
| OwnScatteredNodes  | 100000  |    867.07 us |  27.37 |         - |
|                    |         |              |        |           |
| ListOfInt          | 1000000 |    319.12 us |   1.00 |         - |
| BclLinkedList      | 1000000 |    907.13 us |   2.84 |         - |
| OwnSequentialNodes | 1000000 |    817.50 us |   2.56 |         - |
| OwnScatteredNodes  | 1000000 | 82,700.92 us | 259.16 |         - |

With nodes allocated in order, the linked list is about 2.6–2.8 times slower than the List. .NET's allocator places consecutive objects next to each other, so prefetching still works to some degree. With scattered nodes the picture changes: 27 times at 100,000 nodes, 259 times at 1,000,000. One million scattered nodes spread over roughly 100 MB that never fits in the cache; each step is most likely a read that goes all the way to main memory. The complexity is the same, O(n); the whole difference is in the constants. That is why "insertion is O(1) in a linked list" is not enough on its own to choose one; the Big-O and Complexity series post "What Big-O Doesn't Tell You" covers the general form of this gap.

In Production

The linked list's real advantage is "if you hold a node, you can remove it or insert next to it in O(1)". Its best-known use is the LRU (Least Recently Used) cache: a Dictionary<TKey, LinkedListNode<TValue>> takes you from key to node in O(1), and the doubly linked list moves the accessed node to the front and evicts the last one in O(1). In any scenario where you have to search (find by value, then remove), the advantage disappears; the search is already O(n).

Do not tie code that wants indexing to a linked list. ElementAt(i) on a LinkedList<T> walks i steps from the start on every call; inside a for loop it becomes O(n²). That is why LinkedList<T> does not implement IList<T>.

The default choice is still List<T>. Even when removing from the middle is frequent, if the list has a few thousand elements, the List's shift (a copy of a contiguous block in memory) is often faster than finding the node in a linked list. Measure with your own n before deciding.

Common Pitfalls

Losing next in reverse. If the line current.Next = previous is written before next = current.Next, the list breaks at the first node and the rest is lost. In any code that changes pointers, save first, then change.

An infinite loop on a list with a cycle. When walking a structure that comes from outside or is linked by hand and a cycle is possible, check with Floyd first or put an upper bound on the walk. The test helper ToList in this post has a limit parameter of 1,000; a test that accidentally walks a list with a cycle fails instead of hanging.

Forgetting to update the tail. If _tail keeps pointing to the old node after the last node is removed or the list is reversed, the next AddLast appends to a node that is no longer in the list and the element silently disappears. Write tests for exactly these scenarios.

Leaving the links of a removed node in place. If a removed node still points to its neighbours, outside code holding that node can keep the whole list alive. That is why DoublyLinkedList.Remove clears the Next and Previous of the node it removes.

A Small Experiment

★☆☆ Add RemoveAll(Predicate<T> match) to SinglyLinkedList<T>. Show that the sentinel lets you write it with a single loop, and write a test that removes nodes at the front, in the middle and at the end.

★★☆ Using MergeSorted and Middle, write merge sort for a linked list: split the list in the middle, sort both halves recursively, merge them. How does the extra memory compare with the array version?

★★★ Write a capacity-limited LruCache with Dictionary<string, DoublyNode<(string Key, Book Value)>> and DoublyLinkedList: Get moves the accessed entry to the front, Set evicts the last one when the capacity is full. Add a benchmark showing that both operations are O(1).

The linked list and the array are the two building blocks of the next post. Stack and queue are really ADTs (Abstract Data Types): "last in, first out" and "first in, first out" contracts. In the next post we implement both on an array, and write a circular buffer for the queue and a bounded ring buffer that keeps the last N log lines.