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 boolean remove(Object o) {
 155     if( head == null ) {
 156 //      System.out.println("LinkedList: illegal remove( Object o )");
 157 //      System.exit(-1);
 158       return false;
 159     }
 160     LinkedListElement e = head;
 161     while (e != null) {
 162       if (e.element == o) {
 163         if (e.prev != null) {
 164           e.prev.next = e.next;
 165         }
 166         if (e.next != null) {
 167           e.next.prev = e.prev;
 168         }
 169         size--;
 170         return true;
 171       }
 172       e = e.next;
 173     }
 174 //    System.out.println("LinkedList: illegal remove( Object o ), "+o+" not found");
 175 //    System.exit(-1);
 176     return false;
 177   }
 178
 179   public Object pop() {
 180     Object o = getFirst();
 181     removeFirst();
 182     return o;
 183   }
 184
 185   public void push(Object o) {
 186     addFirst(o);
 187   }
 188
 189   public Iterator iterator() {
 190     return new LinkedListIterator(this);
 191   }
 192 }
 193
 194 public class LinkedListIterator extends Iterator {
 195   LinkedList ll;
 196   LinkedListElement itr;
 197   Object removeable;
 198
 199   public LinkedListIterator(LinkedList ll) {
 200     this.ll = ll;
 201     itr = ll.head;
 202     removeable = null;
 203   }
 204
 205   public boolean hasNext() {
 206     return itr != null;
 207   }
 208
 209   public Object next() {
 210     if( itr == null ) {
 211       System.out.println("LinkedListIterator: illegal next()");
 212       System.exit(-1);
 213     }
 214     removeable = itr.element;
 215     itr = itr.next;
 216     return removeable;
 217   }
 218
 219   public void remove() {
 220     if( removeable == null ) {
 221       System.out.println("LinkedListIterator: illegal remove()");
 222       System.exit(-1);
 223     }
 224     ll.remove(removeable);
 225     removeable = null;
 226   }
 227 }