while ( data > next.getValue() )
{
current = next;
next = next.getNext();
}
newNode.setNext( next );
current.setNext( newNode );
Here is the class, including the complete first attempt at insertInOrder();
// OrderedLinkedList.java
//
public class OrderedLinkedList
{
private Node headPtr = null;
// The constructor creates an empty list
public OrderedLinkedList()
{
headPtr = null;
}
// Determine if the List is empty
public boolean isEmpty()
{
return headPtr == null;
}
// Clear the list
public void clear()
{
headPtr = null;
}
// Insert one Node containing data
// into the list in ascending order
public void insertInOrder( int data )
{
// create a new node to go into the list
Node newNode = new Node( data );
newNode.setNext( null );
// CASE 1: insert into an empty list
if ( headPtr==null )
{
headPtr = newNode;
return;
}
// CASE 2: if data is less than current first node
else if ( data < headPtr.getValue() )
{
newNode.setNext( headPtr ); // current first becomes second
headPtr = newNode; // newNode becomes first
return;
}
// CASE 3: data goes at end of the list
Node current = headPtr;
while ( current.getNext() != null ) // advance current to last node
{
current = current.getNext();
}
if ( current.getValue() < data ) // check if new node should follow
{
current.setNext( newNode ); // link it in, if so
return;
}
// CASE 4: data goes between two nodes
current = headPtr;
Node next = headPtr.getNext();
while ( data > next.getValue() ) // search for the proper gap
{
current = next;
next = next.getNext();
}
newNode.setNext( next ); // link in the new node
current.setNext( newNode );
}
// Traverse the list printing out each Node
public void traverse()
{
Node current = headPtr;
while ( current != null )
{
if ( current == headPtr )
System.out.print( current );
else
System.out.print( ", " + current );
current = current.getNext();
}
}
}
What would be a good way to test this class?