3.1 Singly Linked Lists

A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node. The structure is defined inductively: an empty list is nil, and a non-empty list is a node followed by another list. This definition forces all traversal to proceed in one direction, from head to tail.

Structure

A minimal node definition in pseudocode is:

Node {
  value
  next : Node | null
}

The list is identified by a single pointer head. If head = null, the list is empty. Otherwise, head points to the first node, and repeated application of next eventually reaches null.

Traversal

The fundamental operation is linear traversal. Every algorithm builds on this pattern.

cur = head
while cur != null:
  process(cur.value)
  cur = cur.next

Time complexity is O(n). Random access is not available.

Insertion

Insertion depends on whether you control the predecessor node.

Insert after a given node:

new.next = cur.next
cur.next = new

Insert at the head:

new.next = head
head = new

Both operations run in O(1). The invariant is that no existing node becomes unreachable.

Deletion

Deletion requires access to the predecessor.

Delete after a given node:

cur.next = cur.next.next

Delete the head:

head = head.next

Again, both are O(1). The key constraint is that you must not lose the remaining list. If the only reference to a node is removed, the node becomes unreachable.

Search

Search is sequential:

cur = head
while cur != null:
  if cur.value == target:
    return cur
  cur = cur.next
return null

Time complexity is O(n).

Invariants

Most list algorithms rely on a simple invariant:

At each step, the portion of the list before cur has already been processed, and the portion starting at cur remains unchanged.

Maintaining this invariant prevents structural errors such as skipping nodes or breaking the chain.

Common Patterns

Dummy (sentinel) head

A dummy node simplifies edge cases:

dummy.next = head
cur = dummy

This ensures every real node has a predecessor, which simplifies deletion and insertion logic.

Two pointers

Maintain two references:

prev = null
cur = head

This pattern appears in reversal, deletion, and partitioning.

Example: Reverse a List

prev = null
cur = head

while cur != null:
  next = cur.next
  cur.next = prev
  prev = cur
  cur = next

head = prev

The invariant is:

• prev points to the already reversed prefix
• cur points to the remaining suffix

Each step moves one node from the suffix to the prefix.

Complexity Summary

Failure Modes

• Losing the rest of the list by overwriting next without saving it
• Creating cycles accidentally
• Skipping nodes due to incorrect pointer updates
• Failing to update head when modifying the first node

A singly linked list is simple in definition but strict in execution. Every algorithm reduces to careful control of references and preservation of reachability.