public class LL<T extends Comparable<T>>
{
  ListElement<T> head;
  ListElement<T> tail;
  ListElement<T> latest;

  public LL()
  {
    head = new ListElement<T>();
    tail = head;
    latest = head;
  }

  public void insertAtHead(T value)
  {
    head.link = new ListElement<T>(value, head.link);
  }

  public boolean hasNext()
  {
    return latest.link != null;
  }

  public void reset()
  {
    latest = head;
  }

  public T getNext()
  {
    T retval = latest.link.value;
    latest = latest.link;
    return retval;
  }

  public void insertAtTail(T value)
  {
    tail.link = new ListElement<T>(value, tail.link);
    tail = tail.link;
  }
  
  public T removeFromHead() throws LLException
  {
    if(this.isEmpty())
      throw new LLException("LL underflow");
    ListElement<T> next = head.link;
    T retval = next.value;
    next = next.link;
    head.link= next;
    return retval;
  }

  public void insertSorted(T value)
  {
    head.link = insertSorted(head.link, value);
  }

  private ListElement<T> insertSorted(ListElement<T> where, T value)
  {
    if(where == null)
    {
      where = new ListElement<T>(value);
    }
    else if (where.value.compareTo(value) == 0)
    {
      where.value = value;
    }
    else if (where.value.compareTo(value) > 0)
    {
      where = new ListElement<T>(value, where);
    }
    else
    {
      where.link = insertSorted(where.link, value);
    }
    return where;
  }
      

  public boolean isEmpty()
  {
    return head.link == null;
  }

  public void traverse()
  {
    traverse(this.head.link);
  }

  public String toString()
  {
    String retval = "";
    if(head.link == null)
    {
      retval += "Empty";
    }
    else
    {
      ListElement where = head.link;
      while(where != null)
      {
        retval += where.value + "\n";
        where = where.link;
      }
      
    }
    return retval;
  }
  
  public void traverse(ListElement<T> h)
  {
    if(h == null)
      return;
    else
    {
      System.out.println(h.value);
      traverse(h.link);
    }
  }

  public static void main(String args[])
  {
    LL<Integer> myList = new LL<Integer>(); 
    for(int i = 0; i < 10; i++)
    {
      System.out.println("Inserting " + i);
      myList.insertAtHead(i);
    }

    myList.traverse();
  }
}

class ListElement<R>
{
  public R value;
  public ListElement<R> link;

  public ListElement(R value, ListElement<R> link)
  {
    this.value = value;
    this.link = link;
  }

  public ListElement(R value)
  {
    this(value, null);
  }
  
  public ListElement()
  {
    this(null, null);
  }
}