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     } else {
 117       tail = null;
 118     }
 119     size--;
 120   }
 121
 122   public void removeLast() {
 123     if( tail == null ) {
 124       System.out.println( "LinkedList: illegal removeLast()" );
 125       System.exit(-1);
 126     }
 127     tail = tail.prev;
 128     if( tail != null ) {
 129       tail.next = null;
 130     } else {
 131       head = null;
 132     }
 133     size--;
 134   }
 135
 136   public void remove( Object o ) {
 137     if( head == null ) {
 138       System.out.println( "LinkedList: illegal remove( Object o )" );
 139       System.exit(-1);
 140     }
 141     LinkedListElement e = head;
 142     while( e != null ) {
 143       if( e.element == o ) {
 144         if( e.prev != null ) {
 145           e.prev.next = e.next;
 146         }
 147         if( e.next != null ) {
 148           e.next.prev = e.prev;
 149         }
 150         size--;
 151         return;
 152       }
 153       e = e.next;
 154     }
 155     System.out.println( "LinkedList: illegal remove( Object o ), "+o+" not found" );
 156     System.exit(-1);
 157   }
 158
 159   public Object pop() {
 160     Object o = getFirst();
 161     removeFirst();
 162     return o;
 163   }
 164
 165   public void push( Object o ) {
 166     addFirst( o );
 167   }
 168
 169   public Iterator iterator() {
 170     return new LinkedListIterator( this );
 171   }
 172 }
 173
 174 public class LinkedListIterator extends Iterator {
 175   LinkedList ll;
 176   LinkedListElement itr;
 177   Object removeable;
 178
 179   public LinkedListIterator( LinkedList ll ) {
 180     this.ll = ll;
 181     itr = ll.head;
 182     removeable = null;
 183   }
 184
 185   public boolean hasNext() {
 186     return itr != null;
 187   }
 188
 189   public Object next() {
 190     if( itr == null ) {
 191       System.out.println( "LinkedListIterator: illegal next()" );
 192       System.exit(-1);
 193     }
 194     removeable = itr.element;
 195     itr = itr.next;
 196     return removeable;
 197   }
 198
 199   public void remove() {
 200     if( removeable == null ) {
 201       System.out.println( "LinkedListIterator: illegal remove()" );
 202       System.exit(-1);
 203     }
 204     ll.remove( removeable );
 205     removeable = null;
 206   }
 207 }