3.10 Deletion Patterns

Deletion removes one or more nodes from a linked list by changing links around them. The values stored in the nodes are usually irrelevant. What matters is the predecessor of the node being removed and the successor that must remain reachable afterward.

In a singly linked list, deletion is harder than insertion because a node does not know its predecessor. For this reason, most deletion algorithms maintain a prev pointer, use a sentinel node, or both.

Delete After a Known Node

The simplest deletion removes the node immediately after prev.

if prev.next != null:
  prev.next = prev.next.next

This runs in O(1) time. It assumes that prev itself is still part of the list.

If the removed node must be detached explicitly, save it first.

node = prev.next

if node != null:
  prev.next = node.next
  node.next = null

The important invariant is that prev.next must point to the first node after the removed node.

Delete the Head

The head has no predecessor, so it needs separate handling unless a sentinel is used.

if head != null:
  head = head.next

This is correct, but it creates special cases in larger algorithms. A sentinel removes that difference.

dummy.next = head
prev = dummy
cur = head

After the algorithm finishes, return:

dummy.next

Delete First Matching Node

Remove the first node whose value equals target.

dummy = new Node()
dummy.next = head

prev = dummy
cur = head

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

  prev = cur
  cur = cur.next

return dummy.next

The loop invariant is:

prev.next == cur

This invariant gives the algorithm a uniform deletion rule. Even when cur is the original head, prev is the dummy node.

Delete All Matching Nodes

When deleting multiple nodes, prev advances only when the current node is retained.

dummy = new Node()
dummy.next = head

prev = dummy
cur = head

while cur != null:
  if cur.value == target:
    next = cur.next
    prev.next = next
    cur.next = null
    cur = next
  else:
    prev = cur
    cur = cur.next

return dummy.next

This distinction is essential. After deleting cur, the predecessor remains the same because the next node has not yet been examined.

For example, deleting 2 from:

1 -> 2 -> 2 -> 3 -> null

must produce:

1 -> 3 -> null

If prev moves after the first deletion, the second 2 may be skipped.

Delete by Predicate

Deletion by predicate generalizes deletion by value.

dummy = new Node()
dummy.next = head

prev = dummy
cur = head

while cur != null:
  if remove(cur):
    next = cur.next
    prev.next = next
    cur.next = null
    cur = next
  else:
    prev = cur
    cur = cur.next

return dummy.next

The predicate may check value, position, frequency, membership in a set, or a structural property.

Delete the Nth Node from the End

Use a fixed gap between two pointers. A sentinel makes deletion of the head uniform.

dummy = new Node()
dummy.next = head

lead = dummy
follow = dummy

for i in 1..n+1:
  lead = lead.next

while lead != null:
  lead = lead.next
  follow = follow.next

node = follow.next
follow.next = node.next
node.next = null

return dummy.next

The gap is n + 1, so when lead reaches null, follow points to the predecessor of the node to delete.

Delete Duplicates from a Sorted List

If the list is sorted and duplicate values should be collapsed to one node:

cur = head

while cur != null and cur.next != null:
  if cur.value == cur.next.value:
    node = cur.next
    cur.next = node.next
    node.next = null
  else:
    cur = cur.next

return head

This keeps the first node in each duplicate run.

For:

1 -> 1 -> 2 -> 3 -> 3 -> null

the result is:

1 -> 2 -> 3 -> null

Delete All Duplicate Values from a Sorted List

Sometimes every value that appears more than once must be removed completely.

For:

1 -> 1 -> 2 -> 3 -> 3 -> 4 -> null

the result should be:

2 -> 4 -> null

Use a sentinel and skip whole runs.

dummy = new Node()
dummy.next = head

prev = dummy
cur = head

while cur != null:
  duplicated = false

  while cur.next != null and cur.value == cur.next.value:
    next = cur.next
    cur.next = next.next
    next.next = null
    duplicated = true

  if duplicated:
    next = cur.next
    prev.next = next
    cur.next = null
    cur = next
  else:
    prev = cur
    cur = cur.next

return dummy.next

The important point is that prev advances only after a non-duplicate value is confirmed.

Delete a Known Node Without Head

Some interview problems give a pointer to a node but not the head of the list. In a singly linked list, the node cannot be removed directly unless it is not the tail. The workaround copies the successor value and bypasses the successor.

delete_given_node(node):
  if node == null or node.next == null:
    error

  next = node.next
  node.value = next.value
  node.next = next.next
  next.next = null

This does not remove the given node object. It removes the next node and mutates the given node to look like it. This distinction matters when node identity is observable.

Complexity Summary

Common Failure Modes

The most common deletion bug is moving prev after deleting cur. When a node is removed, prev should still point to the last retained node.

Another common bug is failing to update head when the removed node is the first node. A sentinel removes this case by making every real node have a predecessor.

A third bug is dropping a suffix by writing cur.next = null before saving cur.next. The safe order is:

next = cur.next
prev.next = next
cur.next = null
cur = next

Key Insight

Deletion is predecessor control. In a singly linked list, you rarely delete “the current node” directly. You delete the node after a predecessor by changing one edge. A sentinel gives the head a predecessor, and the invariant prev.next == cur makes deletion uniform.