Answer:

The current pointer could be moved along the list until it finds the node with a value greater than the new value or becomes null. But then the previous node must be modified to insert the new node, but there is no longer a pointer to the previous node. So this does not work.

Another idea is for each node to point both to its successor and to its predecessor. This is called a doubly-linked list and is another way to implement a linked list.

New Improved OrderedLinkedList

Here is the class which combines handling of case III and case IV. Some other small changes have been made:

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 )
  {
    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
    else if ( data < headPtr.getValue() )
    {
      newNode.setNext( headPtr ); // current first becomes second
      headPtr = newNode;          // newNode becomes first 
      return;      
    }
    
    // CASE 3 and 4: data goes in a gap or at end of the list
    //               
    Node current = headPtr;      // initialize the pointers
    Node next = headPtr.getNext();

    // search for the end or a gap
    while ( next!=null && data > next.getValue() )
    {
      current = next;
      next = next.getNext();
    }

    // link in the new node        
    newNode.setNext( next );
    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();
    }
  }

}

Answer:

New Improved OrderedLinkedList

QUESTION 12: