About 1 insertion in 10,000.
If the 10,000 nodes already in the list are a representative sample of data, a new node will be inserted at the end about once in 10,000 times. Most insertions will be somewhere in the middle (case IV). But for every one of them, case III will move a pointer completely through the list, but then do nothing. This is a great waste of time!
A better idea is to arrange for the gap-search loop to look for the situation where the node after the current node holds a value greater than the node we are inserting, OR does not exist.
In both of these cases, the current node is linked to the new node,
and the new node gets the pointer in next (which might be null.)
The picture shows this:
Here is the code that advances the current pointer until it finds the gap or the end.
// initialize the pointers
Node current = headPtr;
Node next = headPtr.getNext();
// search for the end or a gap
while ( next!=null && data > next.getValue() )
{
current = next;
next = next.getNext();
}
// link in the new node
newNode.setNext( next );
current.setNext( newNode );
Notice the condition in the while:
next!=null && data > next.getValue()
This uses short-circuit evaluation (see chapter 18).
If next is equal to null,
the whole expression immediately evaluates to false
without evaluating the subexpression following the &&.
If next is not equal to null,
then the second subexpression tests if data is greater that
the value in the node following the current one.
Moving two pointers through the list is awkward. Could the gap search be written with just one pointer?