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

class OrderedList  {
   private int value;
   private OrderedList next;

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

   public OrderedList 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 OrderedList searchBefore(int x) { // Locate node containing X
       OrderedList n = this;
       while (true) {
          if (n.next==null) return n;
          if (n.next.value >= x) 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=x.

   public boolean inList(int x) {
       OrderedList n = searchBefore(x);
       return n.next != null && n.next.value == x; }

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

   public void delete(int x) {
       OrderedList n = searchBefore(x);
       if (n.next != null && n.next.value == x)
          n.next = n.next.next;
      }



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

   public static void main(String[] args) {
      OrderedList l = new OrderedList();
      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());
}
}