Sorted Lists - Data Structures and Abstractions with Java - page 414

A high-level algorithm that describes our strategy follows:
Algorithm add(newEntry)
// Adds a new entry to the sorted list.
Allocate a new node containing newEntry
Search the chain until either you find a node containing newEntry or you pass the point
where it should be
Let nodeBefore reference the node before the insertion point
if ( the chain is empty or the new node belongs at the beginning of the chain )
Add the new node to the beginning of the chain
else
Insert the new node after the node referenced by nodeBefore

Increment the length of the sorted list

16.10

An iterative implementation of add . A Java implementation of the previous algorithm follows. We
use a private method, getNodeBefore , to search the chain for the node before the insertion point.

public void add(T newEntry)
{

Node newNode = new Node(newEntry);
Node nodeBefore = getNodeBefore(newEntry);
if (isEmpty() || (nodeBefore == null )) // add at beginning
{

newNode.setNextNode(firstNode);
firstNode = newNode;

}
else // add after nodeBefore

{

Node nodeAfter = nodeBefore.getNextNode();
newNode.setNextNode(nodeAfter);
nodeBefore.setNextNode(newNode);
} // end if
numberOfEntries++;
} // end add

16.11

The private method getNodeBefore . We still need to implement the private method getNodeBefore .
We will need two references as we traverse the list. Clearly we need a reference to the current node so
we can compare its entry to the desired entry. But we also must retain a reference to the previous node,
because it is this reference that the method returns. In the following implementation, these references are
currentNode and nodeBefore :

/** Finds the node that is before the node that should or does
contain a given entry.
@param anEntry the object to be located
@return either a reference to the node that is before the node
that contains or should contain anEntry, or null if
no prior node exists (that is, if anEntry belongs at
the beginning of the list) */
private Node getNodeBefore(T anEntry)
{

Node currentNode = firstNode;
Node nodeBefore = null ;
while ( (currentNode != null ) &&
(anEntry.compareTo(currentNode.getData()) > 0) )