Singly linked lists: preserve head and tail invariants

Last updated: 3 Oct 20269 min read

tutorial

A singly linked list stores each value with a reference to its successor. A head reference reaches the first node; an optional tail reference makes append O(1) when maintained correctly. Prepending is O(1), but finding an arbitrary value or the predecessor of a node is O(n). Inserting after a node already in hand is O(1); finding that node is not. The empty list has both head and tail absent, and the last node points to no successor. Python object references add allocation and cache costs, so a linked list is not automatically faster than a built-in list for a small workload.

Operational case

A repair queue records jobs J-47 and J-61, then places emergency J-52 at the head. The queue order becomes J-52, J-47, J-61 without shifting array entries. If the dispatcher later asks whether J-61 is present, traversal still walks nodes from the head. The tail must stay J-61 after the prepend. Removing the last job requires finding its predecessor unless the structure also keeps backward links. This case separates a cheap head mutation from a general indexed operation.

Working Python program

class RepairNode:
    def __init__(self, job_id, next_node=None):
        self.job_id = job_id
        self.next_node = next_node

head = RepairNode("J-47", RepairNode("J-61"))
head = RepairNode("J-52", head)
job_ids = []
current = head
while current is not None:
    job_ids.append(current.job_id)
    current = current.next_node
print(job_ids)

Output

['J-52', 'J-47', 'J-61']

Time, space, and tradeoff

The prepend allocates one node in O(1) time and space. Traversal is O(n) time and uses O(n) output space here because the demonstration builds a list; a streaming visitor could use O(1) extra space. Every node carries reference overhead, and pointer chasing tends to be less cache-friendly than contiguous storage. A cycle introduced by a bad link would make this traversal fail to terminate, so production mutation methods must maintain invariants and test empty, one-node, and last-node cases.

Common Mistakes

Do not claim arbitrary insertion is O(1) without an existing node reference.
Do not leave a stale tail after removing the final node.
Do not traverse a potentially cyclic list without a cycle policy.

Connected lessons

Circular linked lists: keep one tail and a valid cycle adds a related operation contract.

Unrolled lists: link small blocks instead of single items adds a related sequence operation contract.

data structures

linked-lists