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