Linked Lists - Building Java Programs: A Back to Basics Approach - page 958

The first two cases are handled by the if branch of the code:

if (front == null || front.data >= value)

empty list front of list

The second two cases are handled inside the else branch of the code:

while (current.next != null && current.next.data < value)

back of list middle of list

Inchworm Approach
Some people find it confusing to write code that involves expressions like
current.next.data . Another approach is to use a pair of pointers that keep track of
a current and a previous position in the list. In effect, the pointers keep track of a two-
element window on the list, as in the following diagram:

prev current

data
2

next data

5

next data

12

next
/

list

As an analogy, consider an inchworm that is two nodes in length. When the inch-
worm stretches out, its back half is on one node and the front half is on another node.
To move forward, it scoots its back half up to where the front half is, then scoots the
front half onto the next node. This is exactly analogous to the code you'd use to move
this pair of variables forward one spot:

prev = current;
current = current.next;

Here is a solution to the addSorted problem using this approach:

public void addSorted(int value) {
if (front == null || front.data >= value) {
front = new ListNode(value, front);
} else {
ListNode prev = front;
ListNode current = front.next;
while (current != null && current.data < value) {
prev = current;