On this page
Description
A singly linked list is a chain of nodes. Each node holds a value and a reference to the next node. Its strength is that inserting, deleting and reversing only rewire a few references, O(1) at a node you already hold, with no shifting as in an array. Its weakness is that reaching position i takes i steps. This skill makes the rewiring safe: save what you're about to overwrite, and know where the head ends up.
We'll go from simple to more technical:
- The pattern: reversing a list with prev, curr and next.
- A second flavor: deleting a node when you don't have the head.
- Where linked structures run in production (LRU caches, allocators, queues).
- The rewiring bugs, and when a linked list is the wrong choice.
The approach
To reverse a list, turn every arrow around. Walk the list with curr, and keep prev, the start of the part you've already reversed. At each node, first save curr.next, because you're about to overwrite it. Then point curr back at prev. Finally move both prev and curr one step forward.
Reversing 4 -> 7 -> 9:
| Step | Saved next | Reversed so far (starts at prev) | Still to do (starts at curr) |
|---|---|---|---|
| Start | (empty) | 4 -> 7 -> 9 | |
| 1 | 7 | 4 | 7 -> 9 |
| 2 | 9 | 7 -> 4 | 9 |
| 3 | none | 9 -> 7 -> 4 | (empty) |
When curr runs off the end, prev is the new head, 9.
Java
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // save before overwriting
curr.next = prev; // rewire
prev = curr;
curr = next;
}
Python
prev = None
curr = head
while curr is not None:
nxt = curr.next # save before overwriting
curr.next = prev # rewire
prev = curr
curr = nxt
The rule that matters most: save curr.next before you overwrite it. Many linked-list bugs that aren't null-pointer errors break exactly this rule.
A second flavor: deleting a node without the head
Sometimes you're given a node, not the head of its list. The usual way to delete it, telling the node before it to skip it, is impossible: a singly linked list can't be walked backward. But the node still has a next. So copy the next node's value into this node, then unlink the next node:
Java
node.val = node.next.val;
node.next = node.next.next;
Python
node.val = node.next.val
node.next = node.next.next
In 4 -> 7 -> 9, deleting the node holding 7 copies 9 into it and unlinks the old 9 node, leaving 4 -> 9. Read from the head, the list looks as if 7 were removed. That's fine as long as nothing outside the list holds on to particular nodes; the deep dive covers when it does. The trick can't remove the last node: there's nothing after it to copy.
Where you'll see it
An LRU cache keeps its eviction order in a linked list (see the Object-Oriented Design course). So do memory allocators that track free blocks, and many event queues. Each one is this same careful rewiring.
Which tool for which job?
| You need | Use |
|---|---|
| Insert/remove at a node you already hold | a linked list - O(1) rewiring |
| Access by index | an array (ArrayList, Python list) |
| Add and remove at both ends | ArrayDeque (Java), collections.deque (Python) |
| Edits that may touch the head | a dummy node before the head |
| Reverse a long list | iteratively - recursion runs out of stack |
| Delete a node with no access to the one before | copy the next value in (not for the last node) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
Overwriting curr.next before saving it | the rest of the list is lost | save next first |
Returning head after reversing | returns the old head, now the tail | return prev |
| Special-casing the head everywhere | duplicated, buggy branches | start from a dummy node |
| The value-copy trick on the last node | there's nothing to copy | it can't be done without the previous node |
list.get(i) in a loop over a Java LinkedList | O(n^2) | iterate with an iterator / for-each |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why save curr.next in a variable before rewiring it?
Show answer
curr.next is about to point back at prev. If you haven't saved its old value, nothing else refers to the rest of the list, and every node after curr is lost for good.
2. After the loop, why is prev the new head and not head?
Show answer
When the loop ends, curr is null and prev sits on what used to be the last node, which now comes first. head still points at the old first node, which is now the last. On a one-node list both are the same, which is why a quick test can miss this bug.
3. Why can't the value-copy trick delete the last node?
Show answer
It works by copying the next node's value in and unlinking the next node. The last node has no next node. And the other way, unlinking it from the node before it, needs exactly the node you can't reach.
Key takeaways
- Save a node's
nextbefore you overwrite it. - After reversing,
previs the new head. The oldheadis now the tail. - Without the previous node, you can still delete a node by copying its successor in, but not the last node.
- That trick assumes nothing outside the list cares which node object holds which value.
- Choose a linked list when inserting and removing at known positions is the main need, not by default.