MerceMay.Technical Library

Data Structures · Linked Structures

Singly Linked Lists: One Pointer per Node and the Cost of Unidirectional Traversal

How a head pointer and a next field support O(1) splicing, why deletion needs the predecessor, and what pointer chasing costs on a modern cache hierarchy.

Archive date October 21, 2026 · 8 min read · foundational

A singly linked list is the smallest possible dynamic container: each element lives in its own allocation and carries exactly one machine word of bookkeeping, the address of the next element. That single word buys insertion and splicing in constant time and costs sequential access, and almost every design decision about linked lists follows from that exchange.

The node, the head, and the empty list

The representation is a struct with a payload and a successor pointer, plus one variable that names the first node.

struct node {
    int value;
    struct node *next;
};

struct list {
    struct node *head;
};

On a 64-bit target with a 4-byte int, struct node occupies 16 bytes: four bytes of payload, four bytes of padding inserted so the 8-byte pointer is naturally aligned, and eight bytes for next. The padding is not waste in the abstract; it is the cost of requiring that a struct node * can be dereferenced without unaligned-access penalties. A payload of 12 bytes or more fills the gap, which is why the overhead ratio of a linked list depends on element size rather than being a fixed percentage.

The empty list is a null head. Every operation therefore begins with a test that the list is non-empty, and that test is the source of a large share of the bugs in hand-written list code. The sentinel technique described in Doubly Linked Lists and the Sentinel Header exists to remove it.

Insertion at the front is three stores and needs no traversal:

void push_front(struct list *l, struct node *n) {
    n->next = l->head;
    l->head = n;
}

Popping the front is the same operation inverted, with the caller responsible for the storage:

struct node *pop_front(struct list *l) {
    struct node *n = l->head;
    if (n != NULL) l->head = n->next;
    return n;
}

Both run in constant time: a fixed number of stores, with no traversal. Compare this with a dynamic array, where insertion at the front requires shifting every element and is linear in the length. That asymmetry is the entire reason linked lists survive in an era of contiguous storage.

Why removal needs the predecessor

Removing the node a cursor points at requires rewriting the next field of the node before it. A singly linked node has no back pointer, so the predecessor must be found by walking from the head. Given only a pointer to the victim, the operation is O(n); given a pointer to the predecessor, it is O(1).

void remove_after(struct list *l, struct node *prev) {
    struct node *victim = prev ? prev->next : l->head;
    if (victim == NULL) return;
    if (prev) prev->next = victim->next;
    else l->head = victim->next;
    free(victim);
}

This is why list interfaces differ so much in shape. An API that returns an iterator to the element before the removed one can delete in constant time. An API that hands out bare element pointers must either search or require the caller to hold a doubly linked node. C++‘s std::forward_list encodes it in the interface directly: the container provides erase_after and has no erase taking an element position. Java’s LinkedList iterator removes the element it last returned, which means the iterator itself carries the predecessor.

The same asymmetry governs the classic interview exercise of deleting a node given only a pointer to it. Copying the successor’s payload into the victim and unlinking the successor works, and is O(1), but it fails when the victim is the last node, and it invalidates any external pointers to the successor. It is a trick, not a general deletion primitive.

Traversal is a chain of dependent loads

The expensive part of a linked list is not the arithmetic, it is the memory access pattern. Reading n->next cannot begin until n has arrived from memory, and the address of the following node is not known until then. The processor can overlap work across independent chains but not within one. For a list of n nodes the traversal performs n dependent loads, each with the full latency of the level of the hierarchy that holds the node.

On a typical machine a load that hits L1 costs a few cycles, one that misses to DRAM costs on the order of a hundred nanoseconds. A node allocated by malloc sits wherever the allocator placed it, so consecutive list elements are usually not adjacent. Each visited node tends to pull in a full 64-byte cache line, of which the traversal uses 16 bytes. The wasted bandwidth is a factor of four for this node layout and grows with element size.

There is a second effect that is easy to miss: hardware prefetchers detect strides and streams, and a pointer chase presents no stride at all. The address stream is data-dependent, so the prefetcher cannot guess the next line. Software prefetching has to issue the load for a node before the traversal needs it, which means knowing the address in advance: either the code maintains an auxiliary structure recording node addresses, or the layout exposes more than one successor at a time. Unrolled nodes, described in Unrolled Linked Lists, are the direct answer to this problem.

A useful comparison, stated as orders of magnitude rather than measurements: scanning an array of n 4-byte integers reads 4n bytes contiguously, in units the hardware prefetcher can request ahead of the consumer. Scanning a list of the same values reads at least 16n bytes scattered across the heap, one dependent load at a time. The array case is limited by bandwidth; the list case is limited by latency, because each node’s address arrives only with its predecessor. The gap therefore widens as the working set outgrows the last-level cache. This is why std::vector outperforms std::list for traversal even though neither container has a better asymptotic bound.

Where the shape is still correct

Pointer-based linking wins whenever the operation is splicing rather than scanning. Moving a range of elements between two lists is a constant-time pointer exchange regardless of range length, provided the range is already bounded by two nodes:

/* Move the contiguous run first..last from src to the front of dst, in O(1).
   before_first is the node preceding the run, or NULL if the run starts at the head. */
void splice_front(struct list *src, struct list *dst,
                  struct node *before_first, struct node *first, struct node *last)
{
    struct node *rest = last->next;          /* remainder of the source list */
    if (before_first) before_first->next = rest;
    else              src->head = rest;      /* run began at the source head */

    last->next = dst->head;
    dst->head = first;
}

Three pointer writes move the run, and the number of writes does not depend on how many nodes the run contains. The precondition is that before_first really precedes first; the function cannot verify it, and a wrong predecessor splices an unrelated chain into the destination.

No array can do that without copying the range. This property is why linked lists appear in scheduler run queues, in memory allocators, and in any structure where elements are moved between owners far more often than they are scanned.

The second case is stability of address. Because nodes never move, a pointer to an element remains valid until that element is removed. A dynamic array invalidates every pointer and iterator on growth. Code that hands out long-lived references to elements, such as an event loop holding timers, can use a linked structure to keep those references valid across insertions.

The third case is unbounded growth without relocation. A list grows one allocation at a time and never needs a contiguous region, which matters when the heap is fragmented or when elements arrive one at a time and the final count is unknown.

Failure modes and boundary conditions

The recurring defects are mechanical, and each has a known cause.

  • Losing the tail. A tail pointer cached for O(1) append must be updated on every operation that changes the last node, including removal of the last element, which must reset tail to the predecessor or to null. Forgetting this turns append into a traversal of a corrupted chain.
  • Dangling cursors. A cursor to a removed node is invalid but often still readable, because the freed memory is usually still mapped. The resulting traversal can loop forever or read unrelated data. In managed runtimes the same bug appears as a retained reference that keeps a whole chain alive.
  • Cycles. A list that accidentally points back into itself turns any traversal into an infinite loop. Floyd’s two-pointer method detects a cycle in O(n) time and O(1) space by advancing one cursor one step and another two steps; if they meet, a cycle exists.
  • Recursive destruction. Freeing a list with a recursive free_list(n->next) overflows the stack for long lists. Iterative destruction with a saved successor is required, and the saved successor must be read before the free.
  • Head deletion in a function. A push_front that takes the head pointer by value cannot update the caller’s variable. Passing struct node ** or returning the new head are the two correct signatures.

None of these are exotic. They are the reason list code tends to be wrapped in a small library with a fixed set of primitives rather than open-coded at each call site.

Relation to the rest of the family

The singly linked list is the base case for the other layouts in this cluster. Adding a back pointer gives bidirectional traversal and O(1) removal with only a node pointer, at the cost of a second word per node. Embedding the link fields inside the payload rather than allocating a wrapper removes the separate allocation entirely, which is the intrusive pattern used by kernel and real-time code. Storing the difference of the two neighbour addresses instead of either one halves the link storage at the cost of traversal restrictions. Each variant keeps the same core promise, constant-time relinking, and pays for it in a different currency.

References

  1. Introduction to Algorithms, 4th edition — Chapter 10, Elementary Data Structures — Cormen, Leiserson, Rivest, Stein; MIT Press
  2. What Every Programmer Should Know About Memory — Ulrich Drepper
  3. ISO/IEC 9899:2018 — Programming languages — C — ISO/IEC