Linked Lists & Pointer-Based Structures

A linked structure stores each element together with one or more links that encode where traversal continues. Unlike an array, it cannot compute element $i$ from a base address. Its advantage is local structural change: once the relevant nodes are known, insertion or removal rewrites a bounded number of links without shifting a suffix. Its costs are the work required to find that location, extra link storage, allocation, and dependent memory loads.

Start from the shape invariant #

A finite null-terminated singly linked list rooted at head satisfies:

• head is null for the empty list or points to the first node;
• every reachable node contains one next link;
• following next eventually reaches null;
• under exclusive ownership, each reachable node has exactly one owning incoming path.

The abstract sequence is the values encountered by following next from head. The invariant rules out cycles; if cycles are allowed, the ADT is a circular list and traversal needs a different stopping condition.

template<class T>
struct Node {
    T value;
    std::unique_ptr<Node> next;
};

std::unique_ptr makes the ownership chain explicit, but it is only one representation. Arena allocation, indices into a node pool, garbage-collected references, or intrusive raw links can be correct under different lifetime contracts.

Insertion is constant only after position is known #

Insert node x after node p:

x.next = p.next
p.next = x

The assignment order matters. Overwriting p.next before saving the old successor loses the remainder of the list. With owning pointers:

template<class T>
void insert_after(Node<T>& p, std::unique_ptr<Node<T>> x) {
    x->next = std::move(p.next);
    p.next = std::move(x);
}

The rewiring is $O(1)$. Finding the predecessor by index is $O(i)$ in a singly linked list. Therefore “linked insertion is $O(1)$” is true only when the API already supplies a valid predecessor/iterator or inserts at a maintained endpoint.

The same separation applies to deletion. Removing the successor of p:

template<class T>
std::unique_ptr<Node<T>> erase_after(Node<T>& p) {
    auto removed = std::move(p.next);
    if (!removed) return nullptr;
    p.next = std::move(removed->next);
    return removed;
}

Returning the removed node makes destruction timing explicit. An API may destroy immediately instead, but concurrent readers then require a memory-reclamation protocol.

Head operations need either a special case or a sentinel #

Insertion/removal before the first element changes head, while interior operations change a node's next. A dummy sentinel head turns both into the same erase_after(predecessor) shape: the sentinel is the predecessor of the first real node.

Sentinels reduce branches but introduce obligations:

• the sentinel must never be returned as a user element;
• empty is sentinel.next == null, not head == null;
• size excludes the sentinel;
• ownership and destruction must include it exactly once.

A circular sentinel can represent both ends: sentinel.next is first, sentinel.prev is last, and empty means both links point to the sentinel. This is the common shape behind robust doubly linked lists.

Singly, doubly, circular, and intrusive forms #

For a doubly linked node x, the core invariant is:

$$x.next\ne null\Rightarrow x.next.prev=x,$$

$$x.prev\ne null\Rightarrow x.prev.next=x.$$

Erasing x must update both neighbors before reclaiming x. A one-sided update creates a structure that may appear correct in forward traversal and corrupt memory in reverse traversal.

Reversal is a three-reference invariant #

To reverse a singly linked list iteratively, maintain:

• prev: already reversed prefix;
• cur: first unprocessed node;
• next: saved remainder before overwriting cur.next.

template<class T>
std::unique_ptr<Node<T>> reverse(std::unique_ptr<Node<T>> head) {
    std::unique_ptr<Node<T>> prev;
    while (head) {
        auto next = std::move(head->next);
        head->next = std::move(prev);
        prev = std::move(head);
        head = std::move(next);
    }
    return prev;
}

At every iteration, the nodes are partitioned between the reversed prefix owned by prev and the untouched suffix owned by head; none is duplicated or lost. The algorithm is $O(n)$ time and $O(1)$ auxiliary ownership state.

Cost includes search, allocation, and locality #

Big-O hides a decisive hardware difference. Array iteration produces predictable adjacent addresses. A node chain makes the next address available only after loading the current node; allocations may scatter nodes across cache lines and pages. A theoretically constant splice does not compensate when the workload mostly scans or searches.

Allocation can also dominate. A non-intrusive list normally allocates one node per element, adding allocator metadata, fragmentation, failure points, and synchronization. Pools or arenas improve locality and allocation cost but change reclamation and lifetime semantics.

Stability is a reason to choose nodes—but state it precisely #

Node-based containers often preserve references to existing elements across insertion and splicing because nodes do not move. Erasing one node invalidates references to that node. Iterator rules can be stricter, and moving nodes between lists may change which container owns an iterator's position.

Stable address is not stable logical identity:

• a freed address can later be reused for another object (ABA problem);
• a raw pointer does not keep an object alive;
• an index into a node pool needs a generation if slots are reused;
• an intrusive hook cannot remain linked after its object is destroyed.

If clients need durable handles, design handles and reclamation explicitly instead of exposing raw node pointers by accident.

Concurrency makes deletion the hard operation #

Publishing a new node can be as small as one atomic link update, but safe removal is not “store around it and delete.” A reader may have loaded the removed pointer before unlinking and dereference it afterward. Mutex protection solves this only when every traversal and retained reference obeys the same lock lifetime.

Lock-free lists require both:

1. a linearizable link-update algorithm, usually compare-and-exchange with marked/versioned state;
2. safe reclamation such as hazard pointers, epochs/RCU, or another proven scheme.

These are separate proofs. Correct CAS logic with immediate delete is still use-after-free.

Choosing linked structures deliberately #

Choose a linked representation when at least one requirement outweighs locality and allocation overhead:

• splice/erase occurs at already-known positions and must not shift other elements;
• stable node addresses are part of the API;
• objects already exist and an intrusive index is appropriate;
• the sequence is assembled from variable-lifetime pieces under an explicit ownership model;
• a pool/block representation can keep the actual workload local.

Prefer a dynamic array when indexing, scanning, compactness, serialization, or vectorization dominates. Prefer a deque/ring buffer for frequent endpoint operations without per-element nodes. Prefer a balanced tree when the real problem is finding ordered insertion points rather than rewiring once found.

Failure diagnostics #

1. Is the structure null-terminated, circular, sentinel-based, or something else?
2. Does traversal have a valid stopping condition, and can malformed input contain a cycle?
3. Is the claimed $O(1)$ update excluding an $O(n)$ search for its position?
4. Was the old successor saved before overwriting a link?
5. Do next.prev and prev.next agree after every doubly linked update?
6. Are head, tail, size, and empty state updated atomically with the links?
7. Who owns each node, and exactly when is it destroyed?
8. Can readers retain a pointer across erase, pool reuse, or container destruction?
9. Is poor performance caused by pointer chasing or allocator pressure rather than comparison count?
10. Does recursive traversal or destruction encounter adversarial chain depth?

Exercises #

1. Insert x before a known node in a doubly linked circular-sentinel list and list every link assignment.
2. Explain why deleting a singly linked node given only a pointer to that node is not generally possible while preserving arbitrary value semantics and tail identity.
3. Give an $O(n)$ time, $O(1)$ space cycle-detection method and state what it does not tell you about ownership.