visual walkthrough
Remove Linked List Elements
Shows why a dummy head removes head-deletion special cases.
The idea
To remove a node you need the node before it, but the head has none. That's why removing from the front usually needs extra code.
A dummy node in front of the head gives every real node a predecessor, so one loop handles the head and the rest alike.
Complexity
| approach | time | space |
|---|---|---|
| Head first, then the rest | O(n) | O(1) |
| Dummy head | O(n) | O(1) |