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 }