# 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:

```text
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.

```text
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:

```text
new.next = cur.next
cur.next = new
```

Insert at the head:

```text
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:

```text
cur.next = cur.next.next
```

Delete the head:

```text
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:

```text
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:

```text
dummy.next = head
cur = dummy
```

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

**Two pointers**

Maintain two references:

```text
prev = null
cur = head
```

This pattern appears in reversal, deletion, and partitioning.

## Example: Reverse a List

```text
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

| Operation                    | Time | Space |
| ---------------------------- | ---- | ----- |
| Traversal                    | O(n) | O(1)  |
| Insertion (known position)   | O(1) | O(1)  |
| Deletion (known predecessor) | O(1) | O(1)  |
| Search                       | O(n) | O(1)  |

## 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.