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 boolean isEmpty() {
  63     return size == 0;
  64   }
  65
  66   public Object clone() {
  67     System.out.println( "LinkedList.clone() not implemented." );
  68     System.exit(-1);
  69   }
  70
  71   public boolean contains( Object o ) {
  72     LinkedListElement e = head;
  73     while( e != null ) {
  74       if( e.element == o ) {
  75         return true;
  76       }
  77       e = e.next;
  78     }
  79     return false;
  80   }
  81
  82   public Object getFirst() {
  83     if( head == null ) {
  84       return null;
  85     }
  86     return head.element;
  87   }
  88
  89   public Object getLast() {
  90     if( tail == null ) {
  91       return null;
  92     }
  93     return tail.element;
  94   }
  95
  96   public Object element() {
  97     getFirst();
  98   }
  99
 100   public Object peek() {
 101     getFirst();
 102   }
 103
 104   public Object peekFirst() {
 105     getFirst();
 106   }
 107
 108   public Object peekLast() {
 109     getLast();
 110   }
 111
 112   public Object removeFirst() {
 113     if( head == null ) {
 114       System.out.println( "LinkedList: illegal removeFirst()" );
 115       System.exit(-1);
 116     }
 117     Object o = head.element;
 118     head = head.next;
 119     if( head != null ) {
 120       head.prev = null;
 121     } else {
 122       tail = null;
 123     }
 124     size--;
 125     return o;
 126   }
 127
 128   public Object removeLast() {
 129     if( tail == null ) {
 130       System.out.println( "LinkedList: illegal removeLast()" );
 131       System.exit(-1);
 132     }
 133     Object o = tail.element;
 134     tail = tail.prev;
 135     if( tail != null ) {
 136       tail.next = null;
 137     } else {
 138       head = null;
 139     }
 140     size--;
 141     return o;
 142   }
 143
 144   public void remove( Object o ) {
 145     if( head == null ) {
 146       System.out.println( "LinkedList: illegal remove( Object o )" );
 147       System.exit(-1);
 148     }
 149     LinkedListElement e = head;
 150     while( e != null ) {
 151       if( e.element == o ) {
 152         if( e.prev != null ) {
 153           e.prev.next = e.next;
 154         }
 155         if( e.next != null ) {
 156           e.next.prev = e.prev;
 157         }
 158         size--;
 159         return;
 160       }
 161       e = e.next;
 162     }
 163     System.out.println( "LinkedList: illegal remove( Object o ), "+o+" not found" );
 164     System.exit(-1);
 165   }
 166
 167   public Object pop() {
 168     Object o = getFirst();
 169     removeFirst();
 170     return o;
 171   }
 172
 173   public void push( Object o ) {
 174     addFirst( o );
 175   }
 176
 177   public Iterator iterator() {
 178     return new LinkedListIterator( this );
 179   }
 180 }
 181
 182 public class LinkedListIterator extends Iterator {
 183   LinkedList ll;
 184   LinkedListElement itr;
 185   Object removeable;
 186
 187   public LinkedListIterator( LinkedList ll ) {
 188     this.ll = ll;
 189     itr = ll.head;
 190     removeable = null;
 191   }
 192
 193   public boolean hasNext() {
 194     return itr != null;
 195   }
 196
 197   public Object next() {
 198     if( itr == null ) {
 199       System.out.println( "LinkedListIterator: illegal next()" );
 200       System.exit(-1);
 201     }
 202     removeable = itr.element;
 203     itr = itr.next;
 204     return removeable;
 205   }
 206
 207   public void remove() {
 208     if( removeable == null ) {
 209       System.out.println( "LinkedListIterator: illegal remove()" );
 210       System.exit(-1);
 211     }
 212     ll.remove( removeable );
 213     removeable = null;
 214   }
 215 }