Traversing a Linked List

This article starts from code rather than from a definition. A linked list is a chain of nodes, where each node holds an item and a next reference to the following node. The list itself is reached through a variable called head. Deleting an item from a linked list is a close cousin of inserting one, but it is simpler, because you only rewire existing references rather than create new nodes. The hard part is making sure the rewiring happens in the right order and in the right places, and that is where most bugs in this operation come from.

Keep the delete method in mind as you read. Its job is to remove only the first node whose item matches the target. It returns true when it finds and deletes the item, and false when no match exists. Read it line by line and keep track of which node each variable refers to. Predicting what a line does before reading the explanation is the fastest way to find the lines that matter.

The first node is special because the list is reached through head. Nothing comes before the first node, so there is no previous node whose next field could be rewired. The only thing that can change is the reference held by head. The source describes this case as setting head = head.next. Because head.next refers to the second node, the new head is the old second node. Everything else in the list stays the same, and the old first node is no longer reachable from the list.

When the node to be deleted sits inside the list, head does not need to move. Instead, you need a reference to the node just before the target. The source uses two references for this. runner points to the node being deleted, and previous points to the node that precedes it. Once both are in place, the statement previous.next = runner.next removes the node. The next field of the previous node now skips over the deleted node and goes straight to the one after it.

After the rewiring, the node holding B has no live reference leading to it. The source notes that such a node will be garbage collected, so the program is free to reclaim its memory. You do not need to clear the deleted node's own next field to make this happen. The important point is that no live reference should still lead to it. The source also encourages you to draw this operation yourself, because the arrows are easy to lose track of when you read only text.

The delete method does not know in advance where the item is, so it searches first. The loop moves runner forward one node at a time, and previous follows one step behind. The loop stops either when runner finds the item or when runner runs off the end of the list. Keeping previous one step behind runner lets the method reach the node before the target without ever going backward. Only after the search finishes does the method decide which of the two cases applies. The following sketch follows the same logic as the textbook's delete method for a linked list.

The javadoc for the textbook's method says that if several copies of the item are present, only the first one in the list is deleted. This follows directly from the loop. Because the search stops at the first match, later copies are never reached.

Most delete bugs come from a single line that works for a middle node but fails for another case. In the sketch above, the line previous.next = runner.next is the one that diverges from expectation when the target is the first node. In that case previous is still null, because nothing was ever placed behind the first node. Following a null reference to change its next field cannot work. The branch that tests previous == null exists to send the first-node case to head = head.next instead.

Suppose you need to print every item in a linked list. A natural first attempt is to use head itself as the moving pointer. You keep stepping head forward to the next node, print the item along the way, and stop when head becomes null. The loop looks clean and seems to do exactly what you want. The problem is what it does to the list.

Advancing head during a walk leaves the program with no way to reach the list afterward. The standard approach avoids this with three moving parts. First, a runner variable receives a copy of head, so both variables refer to the first node at the start. Second, the loop repeatedly processes the item in the node that runner currently refers to. Third, at the end of each pass, runner is advanced by following its next pointer. The loop stops when runner becomes null, which marks the end of the list. head is never changed during the walk, so it still points to the first node when the walk is done.

The same pattern becomes concrete when the processing step is printing. The following code prints every string stored in a list of Strings. As you read it, ask which variable is allowed to change and which variable must not.

The output assumes a generated list whose three nodes hold the strings A, B, and C in that order. The loop visits nodes in list order, so the strings print in the same order they appear in the list. An execution trace would show runner moving node by node while head keeps its original value throughout.