Robust/src/ClassLibrary/LinkedList.java

   1 public class LinkedListElement {
   2   public LinkedListElement next;
   3   public LinkedListElement prev;
   4   public Object element;
   5
   6   public LinkedListElement( Object e,
   7                             LinkedListElement n,
   8                             LinkedListElement p ) {
   9     element = e;
  10     next = n;
  11     prev = p;
  12   }
  13 }
  14
  15 public class LinkedList {
  16   LinkedListElement head;
  17   LinkedListElement tail;
  18   int size;
  19
  20   public LinkedList() {
  21     clear();
  22   }
  23
  24   public add( Object o ) {
  25     if( tail == null ) {
  26       head = new LinkedListElement( o, null, null );
  27       tail = head;
  28
  29     } else {
  30       tail.next = new LinkedListElement( o, null, tail );
  31       tail = tail.next;
  32     }
  33     size++;
  34   }
  35
  36   public addFirst( Object o ) {
  37     if( head == null ) {
  38       head = new LinkedListElement( o, null, null );
  39       tail = head;
  40
  41     } else {
  42       head.prev = new LinkedListElement( o, head, null );
  43       head = head.prev;
  44     }
  45     size++;
  46   }
  47
  48   public addLast( Object o ) {
  49     add( o );
  50   }
  51
  52   public clear() {
  53     head = null;
  54     tail = null;
  55     size = 0;
  56   }
  57
  58   public int size() {
  59     return size;
  60   }
  61
  62   public Object clone() {
  63     System.out.println( "LinkedList.clone() not implemented." );
  64     System.exit(-1);
  65   }
  66
  67   public boolean contains( Object o ) {
  68     LinkedListElement e = head;
  69     while( e != null ) {
  70       if( e.element == o ) {
  71         return true;
  72       }
  73       e = e.next;
  74     }
  75     return false;
  76   }
  77
  78   public Object getFirst() {
  79     if( head == null ) {
  80       return null;
  81     }
  82     return head.element;
  83   }
  84
  85   public Object getLast() {
  86     if( tail == null ) {
  87       return null;
  88     }
  89     return tail.element;
  90   }
  91
  92   public Object element() {
  93     getFirst();
  94   }
  95
  96   public Object peek() {
  97     getFirst();
  98   }
  99
 100   public Object peekFirst() {
 101     getFirst();
 102   }
 103
 104   public Object peekLast() {
 105     getLast();
 106   }
 107
 108   public void removeFirst() {
 109     if( head == null ) {
 110       System.out.println( "LinkedList: illegal removeFirst()" );
 111       System.exit(-1);
 112     }
 113     head = head.next;
 114     if( head != null ) {
 115       head.prev = null;
 116     }
 117     size--;
 118   }
 119
 120   public void removeLast() {
 121     if( tail == null ) {
 122       System.out.println( "LinkedList: illegal removeLast()" );
 123       System.exit(-1);
 124     }
 125     tail = tail.prev;
 126     if( tail != null ) {
 127       tail.next = null;
 128     }
 129     size--;
 130   }
 131
 132   public void remove( Object o ) {
 133     if( head == null ) {
 134       System.out.println( "LinkedList: illegal remove( Object o )" );
 135       System.exit(-1);
 136     }
 137     LinkedListElement e = head;
 138     while( e != null ) {
 139       if( e.element == o ) {
 140         if( e.prev != null ) {
 141           e.prev.next = e.next;
 142         }
 143         if( e.next != null ) {
 144           e.next.prev = e.prev;
 145         }
 146         size--;
 147         return;
 148       }
 149       e = e.next;
 150     }
 151     System.out.println( "LinkedList: illegal remove( Object o ), "+o+" not found" );
 152     System.exit(-1);
 153   }
 154
 155   public Object pop() {
 156     Object o = getFirst();
 157     removeFirst();
 158     return o;
 159   }
 160
 161   public void push( Object o ) {
 162     addFirst( o );
 163   }
 164
 165   public Iterator iterator() {
 166     return new LinkedListIterator( this );
 167   }
 168 }
 169
 170 public class LinkedListIterator extends Iterator {
 171   LinkedListElement itr;
 172
 173   public LinkedListIterator( LinkedList ll ) {
 174     itr = ll.head;
 175   }
 176
 177   boolean hasNext() {
 178     return itr != null;
 179   }
 180
 181   Object next() {
 182     if( itr == null ) {
 183       System.out.println( "LinkedListIterator: illegal next()" );
 184       System.exit(-1);
 185     }
 186     Object o = itr.element;
 187     itr = itr.next;
 188     return o;
 189   }
 190 }