Deleting from a linked list

In a linked list each item, a node, holds a value and an arrow to the next node. To remove a node, point the arrow before it past it. Nothing has to shift along, unlike an array, but you have to walk the list to find the node first.

O(n) to findO(1) to unlinkno extra space

Remove every node holding 3. Press play or step forward to start.

step 0 / 12

1function removeAll(head, target) {2  while (head !== null && head.value === target) {3    head = head.next;4  }5  let curr = head;6  while (curr !== null && curr.next !== null) {7    if (curr.next.value === target) {8      curr.next = curr.next.next;9    } else {10      curr = curr.next;11    }12  }13  return head;14}

Keys: Space play or pause, ← → step. The URL always points at the frame you are on.

What it costs

Case	Time	When
best	n	every node is checked once
average	n	each removal itself is one pointer change
worst	n	the same: removals never shift anything
space	1	just head and curr

Where it breaks

Removing the head. The first node has no arrow pointing at it, only head. Pick Remove 3: the head is handled by moving head itself, before the main loop starts.
Two matches in a row. After unlinking, curr must stay put, because the new next node could also match. Pick Remove 8: move on after every unlink and the second 8 is skipped.
No jumping to the middle. An array finds item i in one step. A list has to follow i arrows from the head. Lists win when you already hold the node you want to remove.