Forgetting to Update the Tail

Deleting the last node leaves the tail pointing at a node that is no longer in the list.

A singly linked list that keeps a tail reference, to its last node, has to move that reference whenever the last node changes, and a delete that forgets breaks the append after it. This card covers the symptom, why it happens, what it costs and the line that prevents it.

The symptom shows up one operation late. A list holds 3 7 5. A delete removes the 5 by setting the 7's next to null, the marker for no next node, and does not touch the tail. Then 8 is appended.

Before the run: what does the list print from the head after the 8 is appended?

Only 3 7. The 8 is attached, but to the deleted 5, which the list no longer reaches.

A run printed the list from the head and from the tail after each operation:

Without the fix: the delete leaves the tail behind

Start

The head reaches all three nodes, and the tail refers to the last of them.

text

head -> [3] -> [7] -> [5] -> null
tail -> [5] -> null

Delete 5 without moving the tail

The walk from the head now stops at the 7, and the tail still refers to the 5.

text

head -> [3] -> [7] -> null
tail -> [5] -> null

Append 8

Append sets the tail's next to the new node and moves the tail to it. The 8 lands after the 5, outside the list.

text

head -> [3] -> [7] -> null
tail -> [8] -> null
node 5 -> [5] -> [8] -> null

The trigger is the delete, and the mechanism is append's trust in the tail: it never walks from the head, so it cannot notice that the tail is stale. Nothing fails at the moment of the mistake. Every later append vanishes in the same way, the head and the tail now describe two different chains, and the bug surfaces far from the delete that caused it, as data that is silently missing.

The remedy is a rule: every operation that can change the last node also moves the tail. Deleting the last node moves it to the node before; inserting after the tail moves it to the new node; deleting the only node sets both head and tail to null. The same run with the fix:

text

after delete 5, with the tail moved to the 7:
head -> [3] -> [7] -> null
tail -> [7] -> null

after append 8:
head -> [3] -> [7] -> [8] -> null
tail -> [8] -> null

To check a list in a test, walk from the head and confirm that the walk ends at the node the tail refers to.

On the Data Structures cheatsheet

← → move through sections and cards