go to previous page   go to home page   go to next page

Answer:

    while ( data > next.getValue() )
    {
      current = next;
      next = next.getNext();
    }
    newNode.setNext( next );
    current.setNext( newNode );

Complete First Attempt

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();
    }
  }

}

QUESTION 9:

What would be a good way to test this class?


go to previous page   go to home page   go to next page