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

Let's first look at the general case of adding a value to the middle of a list.
Suppose that the list currently stores the values [2, 5, 12]:

data
2

next data

5

next data

12

next
/ front

Now suppose that you call the addSorted method and pass it the value 10 . How do
you add the value 10 to this list to preserve sorted order? First you need to find the right
spot to insert it. It belongs between the 5 and 12 , because it is larger than 5 and smaller
than 12 . And how do you write that as a loop? You have to compare the value against
the various data values stored in the list, starting with the first value. The new node
doesn't belong in front of the node with 2 in it because 2 is less than 10 . Likewise, it
doesn't belong in front of the node with 5 in it because 5 is less than 10 . But it does
belong in front of the node with 12 in it, because 12 is not less than 10 . Your first
attempt at writing the code might look like the following:

ListNode current = front;
while (current.data < value) {
current = current.next;

}

This code has the core of the right idea, but it has many problems. First of all, it
ends up positioning you in the wrong spot. You want to stop one position early in
order to add something to the list, just as you did with the two add methods.
Remember that there are only two ways to change the structure of a linked list: Either
change front , or change one of the next fields of one of the nodes.
In this case, you want to change the next field of the node that has 5 in it. So you
don't want your variable current to end up referring to the node that has 12 in it. You
want current to point to the node that has 5 in it. You have to modify the code to stop
one position early. You can do this by changing the test to involve current.next
instead of current :

ListNode current = front;
while (current.next.data < value) {
current = current.next;

}

In effect, your test now says, “While the value of the data one position to the right
of my current position is less than value , keep advancing current .” This loop theo-
retically stops when current refers to the node with 5 in it, which means that you
can link in the new node by changing current.next . This new node should have a
data value of value ( 10 in our example). To what should its next link refer? It should
refer to the node that has 12 in it, which is stored in current.next . So you'll want
to construct the node in the following way:

new ListNode(value, current.next)