Singly Linked List, in depth

The model and its invariants

Start from the node. In Python it is a two-field object; in C it is a struct with a value and a pointer; in Java it is a small class. The list object that owns the nodes keeps three fields: head (the first node or None), tail (the last node or None) and size. The tail and size are optional, but both turn O(n) operations into O(1) ones, and both are the usual source of bugs because every mutation must keep them correct.

The invariants are the whole design. Write them down before writing code:

1. head is None if and only if tail is None if and only if size == 0.
2. If the list is non-empty, tail.next is None.
3. Starting at head and following next, you reach tail after exactly size - 1 steps and then None. This also rules out cycles.
4. No node belongs to two lists. Ownership is exclusive.

The asymmetry in the cost line is the defining property. Because a node knows its successor but not its predecessor, anything that needs the node before a position costs a walk. Removing the last element is O(n) even with a tail pointer: you can find the tail in O(1), but you must find the node before it to set its next to None. If you need O(1) removal at both ends, you want a doubly linked list or a deque, not a cleverer singly linked list.

Core operations, implemented

Here is a complete implementation. It keeps head, tail and size, and every method is short because each one handles the empty case and the tail explicitly rather than hoping they will not occur.

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def push_front(self, value):            # O(1)
        self.head = Node(value, self.head)
        if self.tail is None:                # list was empty
            self.tail = self.head
        self.size += 1

    def push_back(self, value):             # O(1) thanks to tail
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def pop_front(self):                    # O(1)
        if self.head is None:
            raise IndexError("pop from empty list")
        node = self.head
        self.head = node.next
        if self.head is None:                # removed the only node
            self.tail = None
        node.next = None                     # detach: no dangling chain
        self.size -= 1
        return node.value

    def find(self, value):                  # O(n)
        cur = self.head
        while cur is not None:
            if cur.value == value:
                return cur
            cur = cur.next
        return None

    def insert_after(self, node, value):    # O(1) given the node
        new = Node(value, node.next)
        node.next = new
        if node is self.tail:
            self.tail = new
        self.size += 1

Notice where the special cases live. push_front must set tail when the list was empty. pop_front must clear tail when it removes the last node. insert_after must move tail when inserting after the current tail. Forget any one of them and the list still passes most tests, because most tests never touch the boundary. That is why the invariant checker later in this article matters more than the code itself.

Deletion without special cases

Deleting by value is where singly linked lists get awkward. To unlink a node you must modify its predecessor, so the naive loop tracks two pointers, prev and cur, and has a separate branch for deleting the head. There are two standard ways to remove that branch.

The sentinel (dummy head). Create a throwaway node whose next is the real head. Now every real node, including the first, has a predecessor, so one loop handles every position. At the end, the real head is dummy.next.

def remove_all(lst, value):                 # O(n), one pass, no head branch
    dummy = Node(None, lst.head)
    prev = dummy
    while prev.next is not None:
        if prev.next.value == value:
            victim = prev.next
            prev.next = victim.next
            victim.next = None
            lst.size -= 1
        else:
            prev = prev.next
    lst.head = dummy.next
    lst.tail = prev if lst.head is not None else None

Two details deserve attention. When a match is removed, prev does not advance, because the new prev.next has not been examined yet; advancing anyway skips adjacent duplicates. And the tail fix-up at the end works because, when the loop finishes, prev is the last surviving node. Without that line, deleting the last element leaves tail pointing at a detached node, and the next push_back appends to garbage.

The pointer-to-pointer walk. In C you can walk a pointer to the link field itself rather than to the node. Whether that link is the list's head field or some node's next field no longer matters; you overwrite whatever it points at.

/* Remove the first node holding v. Returns 1 if removed. */
int remove_first(struct node **link, int v) {
    while (*link != NULL) {
        if ((*link)->value == v) {
            struct node *victim = *link;
            *link = victim->next;   /* head or a next field: same code */
            free(victim);
            return 1;
        }
        link = &(*link)->next;
    }
    return 0;
}

Call it as remove_first(&list->head, 9). The idiom is common in systems code because it has no extra allocation and no branch on position. If the list also keeps a tail, you still need one fix-up when the victim was the tail, so many C codebases simply do not keep a tail on singly linked lists.

Checking the invariants in tests

Because the bugs live at the boundaries, test the invariants, not just the outputs. A checker that walks the list and asserts every rule turns silent corruption into an immediate failure at the operation that caused it.

def check(lst):
    if lst.size == 0:
        assert lst.head is None and lst.tail is None
        return
    assert lst.head is not None and lst.tail is not None
    assert lst.tail.next is None
    steps, cur = 0, lst.head
    while cur.next is not None:
        cur = cur.next
        steps += 1
        assert steps < lst.size, "cycle or size too small"
    assert cur is lst.tail, "tail is not the last node"
    assert steps == lst.size - 1, "size does not match length"

The step bound doubles as cycle detection: a cycle would make the walk exceed size, so the assertion fires instead of looping forever. Pair the checker with a randomized test that applies thousands of random operations to both your list and a plain Python list used as a reference model, calling check after every step and comparing contents. This kind of model-based test finds the empty-list and last-element bugs in seconds, which hand-written cases routinely miss. When you only have a raw head with no size, use Floyd's tortoise-and-hare instead; see Floyd cycle detection.

Worked example: one session, traced

Trace one session on an empty list to see every invariant hold. Start: head, tail None, size 0.

Five of the seven steps hit a boundary case. That ratio is typical, and it is why the structure looks simple and still produces bugs.

What it costs on real hardware

Big-O hides the most important practical fact: linked lists are slow to traverse on modern CPUs. An array stores elements contiguously, so the hardware prefetcher streams them into cache. A linked list stores nodes wherever the allocator put them, and each next is a dependent load: the CPU cannot start fetching node k+1 until node k has arrived. When nodes are scattered, every step can be a cache miss costing on the order of a hundred nanoseconds, while an array scan touches a new cache line only every several elements.

Memory overhead matters too. On 64-bit HotSpot with compressed references, a Java node with a value reference and a next reference occupies 12 bytes of header plus 4 + 4 bytes of fields, rounded to 24 bytes, and a boxed Integer value adds another 16. That is 40 bytes to hold a 4-byte int, against 4 bytes in an int[]. In C, a node with an int and a pointer is 16 bytes after alignment, plus the allocator's per-allocation header.

The last row is the quiet advantage. A node never moves once allocated, so other structures can hold references to it safely. That is often the real reason a linked list is chosen, not insertion speed.

Where singly linked lists still win

Singly linked lists survive in production where their properties fit exactly:

• Hash-table chaining. Each bucket holds a short chain of entries that collided. Chains are expected to be short, insertion at the front is O(1), and entries never move. See hash tables for load factors and why chains stay short.
• Free lists in allocators. Memory allocators thread a singly linked list through the free blocks themselves, storing the next pointer inside the unused memory. Allocation is pop_front and freeing is push_front, both O(1) with zero extra memory.
• Lock-free stacks. The Treiber stack is a singly linked list whose head is updated with compare-and-swap. Push and pop touch only the head, which is why it works. It also inherits the ABA problem: a node can be popped, freed, reused and pushed back between a thread's read and its CAS, so production versions add tagged pointers or safe memory reclamation.
• Skip lists. A skip list is a stack of singly linked lists with express lanes, giving expected O(log n) search. See skip lists.

Where you need recency ordering with O(1) removal of arbitrary nodes, such as an LRU cache, the singly linked list is the wrong choice because removal needs the predecessor; LRU caches use a doubly linked list plus a hash map.

Failure modes

The failures repeat across languages and codebases:

• Stale tail. Removing the last node without updating tail. The next append writes into a detached node and the element vanishes. The invariant checker catches it on the very next call.
• Empty-list dereference. pop_front or head.value on an empty list. Decide on one behavior (exception or sentinel return) and test it.
• Skipped duplicates. Advancing the predecessor after a removal skips the next element, so removing all 3s from 3 → 3 → 5 leaves a 3 behind.
• Use-after-free in C. Reading victim->next after free(victim). Always copy the next pointer first, as the pointer-to-pointer example does.
• Recursive destruction. A chain of std::unique_ptr nodes destroys itself recursively, one stack frame per node, and a long list overflows the stack. Destroy iteratively by detaching nodes in a loop. Recursive algorithms such as recursive reversal have the same limit; see reversing a linked list.
• Accidental cycles. Linking a node that is already in the list, often by reusing a node object across two lists, creates a cycle and every traversal hangs. The ownership invariant forbids it; the checker's step bound detects it.

What to do next

1. Write the four invariants at the top of your list class as a comment, and implement a check function that asserts all of them.
2. Implement push_front, push_back, pop_front, find, insert_after and remove_all from memory, then compare against the code above.
3. Rewrite remove_all once with a sentinel and once with the pointer-to-pointer walk in C, and confirm both handle head, middle, tail and duplicate removals.
4. Build a randomized model test against a Python list that calls check after every operation, and run it for at least ten thousand steps.
5. Benchmark summing a million integers from a linked list and from an array in your language, and note the ratio.
6. Before choosing a linked list in production, name the property you need: O(1) front operations, stable node addresses, or zero-copy splicing. If you cannot name one, use an array.