Ordered Linked List

The methods of the this chapter's 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 start on the LinkedList class that contains a pointer to the first node of a chain of nodes.

The constructor is not really needed since the default constructor would be enough, but is included here to emphasize that headPtr starts out as null.

// OrderedLinkedList
//
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 ); // toString method used here
      else
        System.out.print( ", " + current );
      
      current = current.getNext();
    }
  }
  
  // Insert one Node containing data  
  // into the list in ascending order.
  // Duplicates are allowed.
  public void insertInOrder( int data )
  {
    Node newNode = new Node( data );
    newNode.setNext( null );
    
    // . . .  more work to be done . . .
  }
}

Answer:

Ordered Linked List

QUESTION 2: