// CASE 2: if data is less than in current first node
else if ( data < headPtr.getValue() )
{
newNode.setNext( headPtr ); // current first becomes second
headPtr = newNode; // newNode becomes first
return;
}
Case 3 is adding a node to the end of the list.
The next few pages show a first attempt at handling case 3. Later on case 3 and case 4 will be combined into a better method. But for now, let's look at case 3 in isolation.
Case 3: The newNode contains a value that should go at the end of the list.
headPtr, as always, points to the head of the list.
To detect case 3, move a pointer (called current)
to the end of the list and then decide if the new node should go there.
public class OrderedLinkedList
{
private Node headPtr = null;
// The constructor creates an empty list
public OrderedLinkedList()
{
headPtr = null;
}
// various methods left out
// Insert one Node containing data
// into the list in ascending order.
// Duplicates are allowed.
public void insertInOrder( int data )
{
// Create the node to be inserted
Node newNode = new Node( data );
newNode.setNext( null );
// CASE 1: insert into an empty list
// CASE 2: if data is less than current first
// CASE 3: data goes at end of the list
// First, advance current to the current end of the list.
Node current = headPtr;
while ( )
{
current = current.getNext(); // advance the pointer
}
// current now points at the last node.
// determine if the new node should follow it.
if ( )
{
current.setNext( newNode ); // link the node to the end
}
return;
// CASE 4:
}
}
Pick from the following statements to fill the blanks:
current.getNext() != nullcurrent != nullcurrent.getNext().getValue() < data current.getValue() < data