Data Structures & Algorithms / Contracts, sequences, and search / Lesson 3

Linked nodes, ownership, and traversal

Separate constant-time pointer changes from the search needed to find their location, and preserve reachability invariants.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

A link represents reachability, not an array offset
Preserve the old head before publishing the new one
Reversal needs a saved forward link

A link represents reachability, not an array offset

A singly linked list stores a value and a next link in each node, with a head reference identifying the first node. Reaching position k requires following links from the head unless another suitable reference is already available. This differs from indexed array access. Inserting after a known node can change a constant number of links, but finding that node may take linear time. State which reference the operation receives before advertising a cost. Memory allocation, object overhead, and locality can make linked nodes less attractive than arrays for many real workloads despite elegant pointer operations.

Preserve the old head before publishing the new one

The first program prepends values. The new node points at the old head, then head becomes that node. If the order is reversed carelessly, a node can point to itself or the rest of the chain can become unreachable. The invariant is that following next from head visits all inserted nodes exactly once and eventually reaches None. Empty input naturally leaves head absent. The to_list helper is linear and allocates an output list, so it is not part of a constant-time prepend claim.

python Self-contained Python3 algorithm example using synthetic local data.

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

def to_list(head):
    result = []
    while head is not None:
        result.append(head.value)
        head = head.next
    return result

head = None
for value in [1, 2, 3]:
    head = Node(value, head)
print(to_list(head))

Expected output

[3, 2, 1]

Each prepend changes the front reference and preserves the existing suffix. The final traversal exposes reverse insertion order.

Reversal needs a saved forward link

The second program reverses a chain iteratively. Before changing current.next, it stores the next unprocessed node. The processed prefix is a reversed chain ending at previous, while current identifies the remaining original suffix. Each iteration moves exactly one node from the suffix to the reversed prefix. Without saving following first, overwriting current.next would lose the route to unprocessed nodes. The algorithm uses constant auxiliary references and linear node visits, but it mutates the original links. Callers retaining aliases to interior nodes can observe that mutation and must agree with the ownership contract.

python Self-contained Python3 algorithm example using synthetic local data.

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

def reverse(head):
    previous = None
    current = head
    while current is not None:
        following = current.next
        current.next = previous
        previous = current
        current = following
    return previous

def values(head):
    result = []
    while head is not None:
        result.append(head.value)
        head = head.next
    return result

head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(values(head))
print(reverse(None))

Expected output

[3, 2, 1]
None

Reversal reuses existing nodes rather than copying values into new nodes. The empty chain remains empty.

Head and tail references introduce coupled invariants

Keeping a tail reference can make append constant time when the chain is valid. Then an empty list must have both head and tail absent, and a one-node list must have head and tail referring to the same node. Removing the final node must clear both references. A stale tail can make later appends attach to a chain no longer reachable from head. Doubly linked lists add previous links and support different known-node operations, but every mutation must update both directions consistently. More references trade convenient operations for additional invariant maintenance.

Distinguish cycles from legitimate shared suffixes

A cycle means repeatedly following next never reaches the absent end, so a simple traversal can run forever. Two different heads sharing a suffix are not necessarily cyclic, but mutation through one head affects the other’s reachable structure. Define whether sharing is permitted. Cycle detection later uses different techniques than counting values in a set, because equal values need not identify the same node. Node identity matters. For a production API, consider whether a standard deque or list is preferable to exposing mutable links and requiring every caller to preserve reachability.

Verify identity-sensitive transformations

Test empty, one-node, two-node, and longer chains. For reversal, check the value order, the new terminal None, and that the same node identities appear exactly once. Reversing twice should restore the original links for a valid acyclic owned chain. A value-only test can miss duplicated nodes when values repeat, so include duplicate values with distinct node identities. Keep fixtures small and bound any diagnostic traversal when investigating a suspected cycle. This is safe local algorithm verification, not a memory benchmark or an instruction to operate production linked structures.

Common errors and fixes

The remaining chain disappears during reversal

Why it happens: next was overwritten before saving the forward reference.
How to fix it: Save following before rewiring current.next.
Prevent it next time: Trace a three-node example by identity.

Append uses a stale tail after the last deletion

Why it happens: The empty-state invariant updated only head.
How to fix it: Clear head and tail together when the last node is removed.
Prevent it next time: Test empty-to-one and one-to-empty transitions.

Equal values are treated as the same node

Why it happens: Value equality replaced object identity.
How to fix it: Compare node identity for structural properties.
Prevent it next time: Include duplicate values in distinct nodes.

Check your understanding

1. Is inserting after a value always constant time in a singly linked list?

Show worked solution

No. Inserting after an already supplied node can change a constant number of links. Finding the node with the requested value can require a full traversal, and duplicate values require a selection rule. State search and mutation costs separately.

2. Why is reversing twice a useful but incomplete check?