Card 02/ 09
Insert and Delete a Node by Rewiring References
Point the new node forward first, then point the previous node at it.
Inserting a node into a linked list, or deleting one, changes a few references and moves no value, but the changes have to happen in a fixed order. This card covers both operations on the list 3 7 5, inserting 4 after the 7 and then deleting the node after the 4, with the list printed by a run after every change.
You need a singly linked list, in which each node's next refers to the node after it, and which keeps head and tail references to its first and last nodes. Call the node holding 7 seven: the program already holds it, from a search or from an earlier step. The goal is to end with 3 7 4 and a tail that refers to the 4. In the printed states, new is the node being inserted and null marks the end.
Insert 4 after 7, then delete the node after 4
Create the new node
Make a node holding 4. Its next is null and nothing in the list refers to it, so the list is unchanged.
head -> [3] -> [7] -> [5] -> null
new -> [4] -> null
tail -> [5]Point the new node at 7's next: new.next = seven.next
The new node now refers to the 5, so the rest of the list can be reached from it as well as from the 7. The list itself still reads 3 7 5.
head -> [3] -> [7] -> [5] -> null
new -> [4] -> [5] -> null
tail -> [5]Point 7 at the new node: seven.next = new
The 7 refers to the 4, which already refers to the 5, so a walk from the head now passes through the 4. The tail still refers to the 5, which is still last.
head -> [3] -> [7] -> [4] -> [5] -> null
tail -> [5]Unlink the node after 4: four.next = five.next
Deleting the node after the 4 copies that node's next into the 4. The 5's next is null, so the 4 now ends the list, and only the tail still refers to the 5.
head -> [3] -> [7] -> [4] -> null
tail -> [5]Move the tail back: tail = four
The deleted node was the last one, so the tail moves to the node before it. Without this change, the next append would attach to a node outside the list.
head -> [3] -> [7] -> [4] -> null
tail -> [4]A list is consistent when a walk from the head ends at the node the tail refers to, and that node's next is null. The run checked both after each operation, and printed check: 4 nodes from head, tail.next is null after the insert and check: 3 nodes from head, tail.next is null after the delete.
Making the two insert changes in the other order breaks the list.
Before the run: what happens if 7 is pointed at the new node first, and the new node is then pointed at 7's next?
The 5 is lost at the first change, because the 7 was the only node that referred to it. The second change reads 7's next, which is now the new node itself, so the 4 points at itself and a walk from the head never ends.
The same run made the two changes in the wrong order, cutting each walk off after six nodes:
after seven.next = new:
head -> [3] -> [7] -> [4] -> null
after new.next = seven.next:
head -> [3] -> [7] -> [4] -> [4] -> [4] -> [4] -> ...So the rule is to link the new node to what follows before anything links to the new node: every node stays reachable at every step. Deleting needs one change to unlink and a second only when the node removed was the tail, and leaving that second change out is a mistake of its own.
← → move through sections and cards