Ordered Linked List

The methods of the class OrderedLinkedList ensure that the nodes are linked into ascending order. The Node class is the same as before. The picture shows a possible ordered linked list.

Here for review is the Node class, unchanged from the previous chapter:

public class Node
{
  private int  value;
  private Node next;
  
  public Node ( int val )
  {
    value = val;
    next = null;
  }
  
  public int  getValue() { return value; }
  public Node getNext()  { return next; }
  
  public void setValue( int val ) { value = val; }
  public void setNext( Node nxt ) { next = nxt; } 
  
  public String toString() { return "" + value ; }
}

Here is a sketch of a the LinkedList class that contains a pointer to the first node of a chain of nodes:

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;
  }
  
  // Traverse the list, printing each node
  // (Slightly improved from previous version.)
  public void traverse()
  {
    Node current = headPtr;
    while ( current != null )
    {
      if ( current == headPtr )
        System.out.print( current );
      else
        System.out.print( ", " + current );
      
      current = current.getNext();
    }
  }
  
  // Insert one Node containing data  
  // into the list in ascending order
  public void insertInOrder( int data )
  {
    Node newNode = new Node( data );
    newNode.setNext( null );
    
    // . . .  more work to be done . . .
  }
}

The constructor is not really needed since the default constructor would be enough, but is included here to emphasize the initial conditions.