Linked List

Linked List Code Labs

Mental Model

A linked list stores order in references, not in adjacent array positions. A node owns a value and a next reference; the head is the only external entry point required to reach the chain. There is no constant-time list[index] operation. To reach the kth node, follow k links.

In the Labs, an integer array represents those references: next_indices[node] is the next node or -1. The representation makes pointer changes observable without hiding the central ownership rule inside a helper class.

Nodes, References, and Ownership

Python variables hold references to node objects. Two names may alias the same node, so changing node.next is visible through every alias. Reassigning the local variable node only moves that one cursor; it does not change the chain.

The key question before mutation is: which reference owns the edge being replaced? Removing a node means updating its predecessor’s next, or updating the external head when there is no predecessor.

Traverse Without Random Access

Start at the head and repeatedly follow next. Before each step, the output contains exactly the nodes already visited in chain order, and the cursor names the next unvisited node. This scan is O(n) time and O(1) auxiliary space when it only aggregates; materializing visited values costs O(n) output space.

def chain_order(next_indices, head):
    order = []
    current = head
    while current != -1:
        order.append(current)
        current = next_indices[current]
    return order

Relink Without Losing the Suffix

Pointer updates must preserve the successor before overwriting the edge that reaches it. During reversal, keep three meanings stable: previous is the reversed prefix head, current is the next node to move, and successor preserves the untouched suffix. Then redirect current.next, advance both boundaries, and repeat.

def reverse_chain(next_indices, head):
    links = next_indices.copy()
    previous = -1
    current = head
    while current != -1:
        successor = links[current]
        links[current] = previous
        previous = current
        current = successor
    return links, previous

If successor is read after the redirect, the original suffix is no longer reachable from the cursor. This is the linked-list version of overwriting data before saving it.

Use a Sentinel for Head Boundaries

A sentinel is a temporary predecessor whose next points at the real head. It lets deletion use the same “predecessor skips target” transition even when the target is currently first. Return the sentinel’s updated successor as the new head; the sentinel itself is not part of the result.

def bypass_node(next_indices, head, remove_index):
    sentinel = len(next_indices)
    links = next_indices.copy() + [head]
    predecessor = sentinel
    while links[predecessor] != remove_index:
        predecessor = links[predecessor]
    links[predecessor] = links[remove_index]
    return links[:-1], links[sentinel]

Sentinels simplify control flow but do not remove the need for a contract. Decide whether the target is guaranteed to exist and whether the removed node must be detached for memory or API semantics.

Choose a Linked List or Another Structure

Choose a linked list when the input is already node-based and the task depends on local relinking, streaming merge, or constant-space reversal. Choose a Python list when indexed access dominates; its compact built-in representation is usually faster and simpler. Choose a deque for an ordinary queue instead of manually maintaining nodes.

Linked lists do not make arbitrary deletion O(1) unless the operation already owns the predecessor or the node contract provides enough local references. Searching for the deletion point remains O(n).

Common Pitfalls

• Advancing before saving the successor can lose the rest of the chain.
• Returning the old head after reversal exposes only the former first node.
• Comparing node values instead of node identity can break problems with duplicate values.
• Mutating a shared input when the function promises a new chain violates alias expectations.
• Forgetting an empty head or one-node chain often produces an attribute error or stale reference.

Explain It in an Interview

Name each cursor by meaning before coding: predecessor, current, successor, or sentinel. State which part of the chain is already final and which edge still connects to untouched nodes. Draw one three-node example, then verify the empty and head-changing cases. Complexity follows from how many times each link is visited; pointer assignment is constant time, but locating a node may require a full traversal.

Relink Nodes Safely(opens in a new tab) isolates one edge replacement. Add Two Numbers(opens in a new tab) adds synchronized traversal, carry state, unequal lengths, and result ownership.