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?