// file OrderedList.java
//  Singly linked list with header.


class GOrderedList<T extends Comparable<? super T>>  {
   private T value;
   private GOrderedList<T> next;

// Note: No setValue() method or setNext() methods are provided, 
// since those could require reordering the list.
  
   public T getValue() {
       return value; }

   public GOrderedList<T> getNext() {
       return next; }

// If X is in the list, returns the previous node.
// If X is not in the list, returns the node for the greatest element less 
// than  X.

   public GOrderedList<T> searchBefore(T x) { // Locate node containing x
       GOrderedList<T> n = this;
       while (true) {
          if (n.next==null) return n;
          if (n.next.value.compareTo(x) >= 0) return n;
          n = n.next;
         } 
      }

// Is element x in the list. Note the use of the left to right evaluation of 
// && (if the condition n.net != null is false, then the conjunction returns
// false without evaluating n.next.value.equals(x).

   public boolean inList(T x) {
       GOrderedList<T> n = searchBefore(x);
       return n.next != null && n.next.value.equals(x); }

// Adds x to the ordered list, if it is not already there.
   public void add(T x) {
       GOrderedList<T> n = searchBefore(x);
       if (n.next == null || !(n.next.value.equals(x))) {
           GOrderedList<T> newNode = new GOrderedList<T>();
           newNode.value = x;
           newNode.next = n.next;
           n.next = newNode;
         }
     }
       
// Deletes x from the ordered list, if it is there.

   public void delete(T x) {
       GOrderedList<T> n = searchBefore(x);
       if (n.next != null && n.next.value.equals(x))
          n.next = n.next.next;
      }



   public String toString() {
          GOrderedList<T> a = next;
          String s = "[";
          while (a != null) {
             s = s + a.value.toString() + " ";
             a = a.next;
           }
         return s+ "]";
         }

   public static void main(String[] args) {
      GOrderedList<Integer> l = new GOrderedList<Integer>();
      l.add(31);
      l.add(41);
      l.add(59);
      l.add(26);
      l.add(53);
      l.add(58);
      l.add(37);
      l.delete(53);
      System.out.println(l.toString());
}
}