/** Linked list of integers. 
 *  Traditional programming exercise. */
public class List
{
  /** Start of list. */
  private ListNode head;

  /** Access the start of the list. */
  private ListNode headGet()
    { return head; }

  /** Empty list. */
  public List()
    { head = null; }

  /** Add to the start of the list. */
  public void addToHead(int data)
  {
    if (head==null)
      head = new ListNode(data,null);
    else
    {
      ListNode x = new ListNode(data,head);
      head = x;
    }
  }

  /** Add in order, O(N) time. */
  public void addInOrder(int data)
  {
    if (head==null)
    {
      addToHead(data);
      return;
    }

    if (data<head.dataGet())
    {
      addToHead(data);
      return;
    }

    ListNode i0 = headGet();
    for (ListNode i = i0.nextGet();
      i!=null; i=i.nextGet() )
    { 
      // Have I found the insertion point?
      if( data<i.dataGet())
      {
        ListNode x = new ListNode(data,i);
        i0.nextSet(x);
        return;
      } 

      i0 = i;
    }  

    // Must add data to the end of the list.
    ListNode x = new ListNode(data,null);
    i0.nextSet(x);
  }

  /** Print each integer on its own line to the console. */ 
  public void print()
  {
    for (ListNode i = headGet();
      i!=null; i=i.nextGet() )
      System.out.println(i.dataGet());
  }

  /** Removes the first element of the list. */
  void removeHead()
  {
    if (head==null)
      return;

    ListNode x = head.nextGet();
    head = x;
  }

  /** Removes all occurences of the element. */
  void removeAll(int data)
  {
    if (head==null)
      return;

    ListNode i = head.nextGet();
    for ( ; i.nextGet()!=null; )
    {
      if (i.nextGet().dataGet()==data)
        i.nextDelete();

      i = i.nextGet();
      if (i==null)
        break;
    }

    if (head.dataGet()==data)
      removeHead();
  }
    

}