import ListNode;

public class List {

  private ListNode front;                // first node in list
  private ListNode tail;                 // last node in list

  /* 
   * insert a new node into the tail if the list
   */
  public void insert( ListNode node ) {

    if ( isEmpty() ) {
       front = node;
       tail = node;
    }
    else {
       tail.setNext( node );
       tail = node;
    }
  }
 
  /*
   * aInsert
   *
   * insert the new node in ascending order
   */
  public void aInsert( ListNode node ) {

     if ( isEmpty() ) {
   
        insert( node );
        return;
      }

     int nodeValue = ( (Integer) node.getElement() ).intValue();
     int frontValue = ( (Integer) front.getElement() ).intValue();
     int tailValue = ( (Integer) tail.getElement() ).intValue();


     if ( nodeValue < frontValue ) {
       // place node at front
        node.setNext( front );
        front = node;      
     }
     else if ( nodeValue >= tailValue ) {
       // place at tail
        insert( node );
     }
     else {
       // place in appropriate position in middle of the list
       ListNode current = front;
       ListNode last = front;
       int currentValue;

       while( current.getNext() != null ) {

         currentValue = ( (Integer) current.getElement() ).intValue();

         if ( nodeValue < currentValue ) {
            break;
         }
   
         last = current;
         current = current.getNext();
        }

        node.setNext( last.getNext() );
        last.setNext( node );
     }
     
  }



  /*
   * remove current node from list
   */
  public void remove( ListNode current ) {
  
    if ( current == front ) {
       front = current.getNext();
    }
    else {
 
      // find the node before current
      ListNode node = front;

      while( current != node.getNext() ) {
           node = node.getNext();
      }
 
      node.setNext( current.getNext() );

      if ( current == tail ) {
          tail = node;
      }
    }
  }

  /* 
   * return true if list is empty
   */
  public boolean isEmpty() {
       
    return front == null;
  }

  /*
   * getFront
   */
  public ListNode getFront() {

     return front;
  }

  public ListNode getTail() {
    
     return tail;
  }


}