# 3.11 Insertion Patterns

Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes. In a singly linked list, insertion is defined relative to a known position, usually a predecessor node. In a doubly linked list, insertion can be defined relative to either neighbor.

## Problem

Given a linked list and a rule for placement, insert a new node or a sequence of nodes while maintaining structural correctness.

Typical rules include:

```text id="0h7l6a"
insert at head
insert at tail
insert after a node
insert before a node
insert in sorted order
insert at position k
```

## Core Pattern

Insertion requires two assignments:

```text id="8c6t8y"
new.next = next_node
prev.next = new
```

The order matters. First connect the new node to the remainder of the list, then connect the predecessor to the new node.

## Insert at Head

```text id="b1y4qz"
new.next = head
head = new
```

This runs in O(1). If a sentinel is used, this becomes:

```text id="kz5m7x"
new.next = dummy.next
dummy.next = new
```

## Insert at Tail

If the tail pointer is available:

```text id="v6p0me"
tail.next = new
new.next = null
tail = new
```

Without a tail pointer, traversal is required.

```text id="2o3m4n"
cur = head
while cur.next != null:
  cur = cur.next

cur.next = new
new.next = null
```

This runs in O(n).

## Insert After a Given Node

```text id="1h0u3t"
new.next = cur.next
cur.next = new
```

This is O(1). The invariant is that `cur` remains reachable and now points to `new`.

## Insert Before a Given Node

In a singly linked list, insertion before a node requires access to its predecessor. Use a sentinel or maintain `prev`.

```text id="j5y2w1"
dummy.next = head

prev = dummy
cur = head

while cur != null:
  if cur == target:
    new.next = cur
    prev.next = new
    break
  prev = cur
  cur = cur.next

head = dummy.next
```

In a doubly linked list, insertion before is direct.

```text id="n7z2kq"
before = cur.prev

new.prev = before
new.next = cur

before.next = new
cur.prev = new
```

## Insert at Position k

Insert at index `k` (0-based). Use a sentinel for uniform handling.

```text id="4s9y6h"
dummy.next = head
prev = dummy

for i in 0..k-1:
  if prev.next == null:
    break
  prev = prev.next

new.next = prev.next
prev.next = new

return dummy.next
```

If `k = 0`, insertion occurs at the head.

## Insert into a Sorted List

Find the first node with value greater than or equal to the new value.

```text id="p8r4vj"
dummy.next = head

prev = dummy
cur = head

while cur != null and cur.value < new.value:
  prev = cur
  cur = cur.next

new.next = cur
prev.next = new

return dummy.next
```

This preserves sorted order and stability.

## Batch Insertion

Insert a sequence of nodes after a position.

```text id="h6f8k1"
after = prev.next

prev.next = first_new
last_new.next = after
```

This pattern connects an entire segment in O(1), assuming the segment endpoints are known.

## Insert While Traversing

Sometimes insertion happens during traversal.

```text id="7p3z2b"
cur = head

while cur != null:
  if condition(cur):
    new = make_node(...)
    new.next = cur.next
    cur.next = new
    cur = new.next
  else:
    cur = cur.next
```

The step `cur = new.next` avoids reprocessing the inserted node.

## Doubly Linked List Insertion

General insertion between two nodes:

```text id="c8y2mh"
insert_between(left, right, new):
  new.prev = left
  new.next = right
  left.next = new
  right.prev = new
```

This uniform pattern works for all positions when sentinel nodes are present.

## Complexity Summary

| Pattern                            | Time | Space |
| ---------------------------------- | ---: | ----: |
| Insert at head                     | O(1) |  O(1) |
| Insert at tail (with tail pointer) | O(1) |  O(1) |
| Insert at tail (no tail pointer)   | O(n) |  O(1) |
| Insert after node                  | O(1) |  O(1) |
| Insert before node (singly)        | O(n) |  O(1) |
| Insert at position k               | O(k) |  O(1) |
| Insert in sorted list              | O(n) |  O(1) |

## Common Failure Modes

The most common mistake is reversing the order of assignments. Writing:

```text id="1y2e3r"
prev.next = new
new.next = cur
```

is correct only if `cur` is still reachable. If `prev.next` is overwritten before saving the old successor, the rest of the list may be lost.

Another failure is not updating `head` when inserting at position zero. A sentinel avoids this issue.

In traversal-based insertion, failing to advance correctly after insertion can lead to infinite loops or repeated insertions.

## Key Insight

Insertion is local but must preserve global reachability. The safe pattern is: identify the predecessor, save the successor, connect the new node to the successor, then connect the predecessor to the new node. This sequence guarantees that no part of the list is lost.