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:

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:

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

new.next = head
head = new

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

new.next = dummy.next
dummy.next = new

Insert at Tail

If the tail pointer is available:

tail.next = new
new.next = null
tail = new

Without a tail pointer, traversal is required.

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

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.

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.

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.

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.

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.

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.

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:

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:

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.