List.java

public class List {

  /**************************************************/  
  class Node {
    String data;
    Node next;
    
    public Node(String d, Node n) { data = d; next = n; }
    public Node(String d)         { this(d, null); }

    @Override
    public String toString() { return "('"+data+"', "+next+")"; }
  }
  /**************************************************/  

  Node head = null;

  public boolean  isEmpty()             { return head == null; }
  public void     print()               { System.out.println(head); }
  public Node     tail(Node n)          { return (n.next == null) ? n : tail(n.next); }
  public Node     tail()                { return isEmpty() ? null : tail(head); }
  public void     prepend(String data)  { prepend(new Node(data)); }
  public void     prepend(Node n)       { n.next = head; head = n; }
  public void     append(Node n)        { if (isEmpty()) { prepend(n); } else { insert_after(tail(), n); } }
  public void     append(String data)   { append(new Node(data)); }
  public void     insert_after(Node target, Node n) { n.next = target.next; target.next = n; }
  public void     insert_ordered(String data) {
    Node p = head;
    while (p != null) {
      if (p.next != null && data.compareTo(p.next.data) < 0) { // n comes after p
        insert_after(p, new Node(data));
        return;
      }
      p = p.next;
    }

    append(data);
  }


 /**************************************************
  * Lazytests
  **************************************************/
 public static void main(String[] args) {
    List l = new List();
    l.print();
    l.append("hello");
    l.print();
    l.insert_ordered("there");
    l.print();
    l.append("world");
    l.print();
    l.insert_ordered("!!!");
    l.print();
    l.insert_ordered("zzzzzzzzzzzzzzz");
    l.print();
  }
}