libjava/java/util/LinkedList.java

   1 /* LinkedList.java -- Linked list implementation of the List interface
   2    Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 USA.
  20
  21 As a special exception, if you link this library with other files to
  22 produce an executable, this library does not by itself cause the
  23 resulting executable to be covered by the GNU General Public License.
  24 This exception does not however invalidate any other reasons why the
  25 executable file might be covered by the GNU General Public License. */
  26
  27
  28 package java.util;
  29 import java.io.Serializable;
  30 import java.io.ObjectOutputStream;
  31 import java.io.ObjectInputStream;
  32 import java.io.IOException;
  33 import java.lang.reflect.Array;
  34
  35 /**
  36  * Linked list implementation of the List interface. In addition to the
  37  * methods of the List interface, this class provides access to the first
  38  * and last list elements in O(1) time for easy stack, queue, or double-ended
  39  * queue (deque) creation. The list is doubly-linked, with traversal to a
  40  * given index starting from the end closest to the element.<p>
  41  *
  42  * LinkedList is not synchronized, so if you need multi-threaded access,
  43  * consider using:<br>
  44  * <code>List l = Collections.synchronizedList(new LinkedList(...));</code>
  45  * <p>
  46  *
  47  * The iterators are <i>fail-fast</i>, meaning that any structural
  48  * modification, except for <code>remove()</code> called on the iterator
  49  * itself, cause the iterator to throw a
  50  * {@link ConcurrentModificationException} rather than exhibit
  51  * non-deterministic behavior.
  52  *
  53  * @author Original author unknown
  54  * @author Bryce McKinlay
  55  * @author Eric Blake <ebb9@email.byu.edu>
  56  * @see List
  57  * @see ArrayList
  58  * @see Vector
  59  * @see Collections#synchronizedList(List)
  60  * @since 1.2
  61  * @status missing javadoc, but complete to 1.4
  62  */
  63 public class LinkedList extends AbstractSequentialList
  64   implements List, Cloneable, Serializable
  65 {
  66   /**
  67    * Compatible with JDK 1.2.
  68    */
  69   private static final long serialVersionUID = 876323262645176354L;
  70
  71   /**
  72    * The first element in the list.
  73    */
  74   transient Entry first;
  75
  76   /**
  77    * The last element in the list.
  78    */
  79   transient Entry last;
  80
  81   /**
  82    * The current length of the list.
  83    */
  84   transient int size = 0;
  85
  86   /**
  87    * Class to represent an entry in the list. Holds a single element.
  88    */
  89   private static final class Entry
  90   {
  91     /** The element in the list. */
  92     Object data;
  93
  94     /** The next list entry, null if this is last. */
  95     Entry next;
  96
  97     /** The previous list entry, null if this is first. */
  98     Entry previous;
  99
 100     /**
 101      * Construct an entry.
 102      * @param data the list element
 103      */
 104     Entry(Object data)
 105     {
 106       this.data = data;
 107     }
 108   } // class Entry
 109
 110   /**
 111    * Obtain the Entry at a given position in a list. This method of course
 112    * takes linear time, but it is intelligent enough to take the shorter of the
 113    * paths to get to the Entry required. This implies that the first or last
 114    * entry in the list is obtained in constant time, which is a very desirable
 115    * property.
 116    * For speed and flexibility, range checking is not done in this method:
 117    * Incorrect values will be returned if (n < 0) or (n >= size).
 118    *
 119    * @param n the number of the entry to get
 120    * @return the entry at position n
 121    */
 122   private Entry getEntry(int n)
 123   {
 124     Entry e;
 125     if (n < size / 2)
 126       {
 127         e = first;
 128         // n less than size/2, iterate from start
 129         while (n-- > 0)
 130           e = e.next;
 131       }
 132     else
 133       {
 134         e = last;
 135         // n greater than size/2, iterate from end
 136         while (++n < size)
 137           e = e.previous;
 138       }
 139     return e;
 140   }
 141
 142   /**
 143    * Remove an entry from the list. This will adjust size and deal with
 144    *  `first' and  `last' appropriatly.
 145    *
 146    * @param e the entry to remove
 147    */
 148   private void removeEntry(Entry e)
 149   {
 150     modCount++;
 151     size--;
 152     if (size == 0)
 153       first = last = null;
 154     else
 155       {
 156         if (e == first)
 157           {
 158             first = e.next;
 159             e.next.previous = null;
 160           }
 161         else if (e == last)
 162           {
 163             last = e.previous;
 164             e.previous.next = null;
 165           }
 166         else
 167           {
 168             e.next.previous = e.previous;
 169             e.previous.next = e.next;
 170           }
 171       }
 172   }
 173
 174   /**
 175    * Checks that the index is in the range of possible elements (inclusive).
 176    *
 177    * @param index the index to check
 178    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size
 179    */
 180   private void checkBoundsInclusive(int index)
 181   {
 182     if (index < 0 || index > size)
 183       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 184                                           + size);
 185   }
 186
 187   /**
 188    * Checks that the index is in the range of existing elements (exclusive).
 189    *
 190    * @param index the index to check
 191    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size
 192    */
 193   private void checkBoundsExclusive(int index)
 194   {
 195     if (index < 0 || index >= size)
 196       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 197                                           + size);
 198   }
 199
 200   /**
 201    * Create an empty linked list.
 202    */
 203   public LinkedList()
 204   {
 205   }
 206
 207   /**
 208    * Create a linked list containing the elements, in order, of a given
 209    * collection.
 210    *
 211    * @param c the collection to populate this list from
 212    * @throws NullPointerException if c is null
 213    */
 214   public LinkedList(Collection c)
 215   {
 216     addAll(c);
 217   }
 218
 219   /**
 220    * Returns the first element in the list.
 221    *
 222    * @return the first list element
 223    * @throws NoSuchElementException if the list is empty
 224    */
 225   public Object getFirst()
 226   {
 227     if (size == 0)
 228       throw new NoSuchElementException();
 229     return first.data;
 230   }
 231
 232   /**
 233    * Returns the last element in the list.
 234    *
 235    * @return the last list element
 236    * @throws NoSuchElementException if the list is empty
 237    */
 238   public Object getLast()
 239   {
 240     if (size == 0)
 241       throw new NoSuchElementException();
 242     return last.data;
 243   }
 244
 245   /**
 246    * Remove and return the first element in the list.
 247    *
 248    * @return the former first element in the list
 249    * @throws NoSuchElementException if the list is empty
 250    */
 251   public Object removeFirst()
 252   {
 253     if (size == 0)
 254       throw new NoSuchElementException();
 255     modCount++;
 256     size--;
 257     Object r = first.data;
 258
 259     if (first.next != null)
 260       first.next.previous = null;
 261     else
 262       last = null;
 263
 264     first = first.next;
 265
 266     return r;
 267   }
 268
 269   /**
 270    * Remove and return the last element in the list.
 271    *
 272    * @return the former last element in the list
 273    * @throws NoSuchElementException if the list is empty
 274    */
 275   public Object removeLast()
 276   {
 277     if (size == 0)
 278       throw new NoSuchElementException();
 279     modCount++;
 280     size--;
 281     Object r = last.data;
 282
 283     if (last.previous != null)
 284       last.previous.next = null;
 285     else
 286       first = null;
 287
 288     last = last.previous;
 289
 290     return r;
 291   }
 292
 293   /**
 294    * Insert an element at the first of the list.
 295    *
 296    * @param o the element to insert
 297    */
 298   public void addFirst(Object o)
 299   {
 300     Entry e = new Entry(o);
 301
 302     modCount++;
 303     if (size == 0)
 304       first = last = e;
 305     else
 306       {
 307         e.next = first;
 308         first.previous = e;
 309         first = e;
 310       }
 311     size++;
 312   }
 313
 314   /**
 315    * Insert an element at the last of the list.
 316    *
 317    * @param o the element to insert
 318    */
 319   public void addLast(Object o)
 320   {
 321     addLastEntry(new Entry(o));
 322   }
 323
 324   /**
 325    * Inserts an element at the end of the list.
 326    *
 327    * @param e the entry to add
 328    */
 329   private void addLastEntry(Entry e)
 330   {
 331     modCount++;
 332     if (size == 0)
 333       first = last = e;
 334     else
 335       {
 336         e.previous = last;
 337         last.next = e;
 338         last = e;
 339       }
 340     size++;
 341   }
 342
 343   /**
 344    * Returns true if the list contains the given object. Comparison is done by
 345    * <code>o == null ? e = null : o.equals(e)</code>.
 346    *
 347    * @param o the element to look for
 348    * @return true if it is found
 349    */
 350   public boolean contains(Object o)
 351   {
 352     Entry e = first;
 353     while (e != null)
 354       {
 355         if (equals(o, e.data))
 356           return true;
 357         e = e.next;
 358       }
 359     return false;
 360   }
 361
 362   /**
 363    * Returns the size of the list.
 364    *
 365    * @return the list size
 366    */
 367   public int size()
 368   {
 369     return size;
 370   }
 371
 372   /**
 373    * Adds an element to the end of the list.
 374    *
 375    * @param e the entry to add
 376    * @return true, as it always succeeds
 377    */
 378   public boolean add(Object o)
 379   {
 380     addLastEntry(new Entry(o));
 381     return true;
 382   }
 383
 384   /**
 385    * Removes the entry at the lowest index in the list that matches the given
 386    * object, comparing by <code>o == null ? e = null : o.equals(e)</code>.
 387    *
 388    * @param o the object to remove
 389    * @return true if an instance of the object was removed
 390    */
 391   public boolean remove(Object o)
 392   {
 393     Entry e = first;
 394     while (e != null)
 395       {
 396         if (equals(o, e.data))
 397           {
 398             removeEntry(e);
 399             return true;
 400           }
 401         e = e.next;
 402       }
 403     return false;
 404   }
 405
 406   /**
 407    * Append the elements of the collection in iteration order to the end of
 408    * this list. If this list is modified externally (for example, if this
 409    * list is the collection), behavior is unspecified.
 410    *
 411    * @param c the collection to append
 412    * @return true if the list was modified
 413    * @throws NullPointerException if c is null
 414    */
 415   public boolean addAll(Collection c)
 416   {
 417     return addAll(size, c);
 418   }
 419
 420   /**
 421    * Insert the elements of the collection in iteration order at the given
 422    * index of this list. If this list is modified externally (for example,
 423    * if this list is the collection), behavior is unspecified.
 424    *
 425    * @param c the collection to append
 426    * @return true if the list was modified
 427    * @throws NullPointerException if c is null
 428    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 429    */
 430   public boolean addAll(int index, Collection c)
 431   {
 432     checkBoundsInclusive(index);
 433     int csize = c.size();
 434
 435     if (csize == 0)
 436       return false;
 437
 438     Iterator itr = c.iterator();
 439
 440     // Get the entries just before and after index. If index is at the start
 441     // of the list, BEFORE is null. If index is at the end of the list, AFTER
 442     // is null. If the list is empty, both are null.
 443     Entry after = null;
 444     Entry before = null;
 445     if (index != size)
 446       {
 447         after = getEntry(index);
 448         before = after.previous;
 449       }
 450     else
 451       before = last;
 452
 453     // Create the first new entry. We do not yet set the link from `before'
 454     // to the first entry, in order to deal with the case where (c == this).
 455     // [Actually, we don't have to handle this case to fufill the
 456     // contract for addAll(), but Sun's implementation appears to.]
 457     Entry e = new Entry(itr.next());
 458     e.previous = before;
 459     Entry prev = e;
 460     Entry firstNew = e;
 461
 462     // Create and link all the remaining entries.
 463     for (int pos = 1; pos < csize; pos++)
 464       {
 465         e = new Entry(itr.next());
 466         e.previous = prev;
 467         prev.next = e;
 468         prev = e;
 469       }
 470
 471     // Link the new chain of entries into the list.
 472     modCount++;
 473     size += csize;
 474     prev.next = after;
 475     if (after != null)
 476       after.previous = e;
 477     else
 478       last = e;
 479
 480     if (before != null)
 481       before.next = firstNew;
 482     else
 483       first = firstNew;
 484     return true;
 485   }
 486
 487   /**
 488    * Remove all elements from this list.
 489    */
 490   public void clear()
 491   {
 492     if (size > 0)
 493       {
 494         modCount++;
 495         first = null;
 496         last = null;
 497         size = 0;
 498       }
 499   }
 500
 501   /**
 502    * Return the element at index.
 503    *
 504    * @param index the place to look
 505    * @return the element at index
 506    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 507    */
 508   public Object get(int index)
 509   {
 510     checkBoundsExclusive(index);
 511     return getEntry(index).data;
 512   }
 513
 514   /**
 515    * Replace the element at the given location in the list.
 516    *
 517    * @param index which index to change
 518    * @param o the new element
 519    * @return the prior element
 520    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 521    */
 522   public Object set(int index, Object o)
 523   {
 524     checkBoundsExclusive(index);
 525     Entry e = getEntry(index);
 526     Object old = e.data;
 527     e.data = o;
 528     return old;
 529   }
 530
 531   /**
 532    * Inserts an element in the given position in the list.
 533    *
 534    * @param index where to insert the element
 535    * @param o the element to insert
 536    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 537    */
 538   public void add(int index, Object o)
 539   {
 540     checkBoundsInclusive(index);
 541     Entry e = new Entry(o);
 542
 543     if (index < size)
 544       {
 545         modCount++;
 546         Entry after = getEntry(index);
 547         e.next = after;
 548         e.previous = after.previous;
 549         if (after.previous == null)
 550           first = e;
 551         else
 552           after.previous.next = e;
 553         after.previous = e;
 554         size++;
 555       }
 556     else
 557       addLastEntry(e);
 558   }
 559
 560   /**
 561    * Removes the element at the given position from the list.
 562    *
 563    * @param index the location of the element to remove
 564    * @return the removed element
 565    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 566    */
 567   public Object remove(int index)
 568   {
 569     checkBoundsExclusive(index);
 570     Entry e = getEntry(index);
 571     removeEntry(e);
 572     return e.data;
 573   }
 574
 575   /**
 576    * Returns the first index where the element is located in the list, or -1.
 577    *
 578    * @param o the element to look for
 579    * @return its position, or -1 if not found
 580    */
 581   public int indexOf(Object o)
 582   {
 583     int index = 0;
 584     Entry e = first;
 585     while (e != null)
 586       {
 587         if (equals(o, e.data))
 588           return index;
 589         index++;
 590         e = e.next;
 591       }
 592     return -1;
 593   }
 594
 595   /**
 596    * Returns the last index where the element is located in the list, or -1.
 597    *
 598    * @param o the element to look for
 599    * @return its position, or -1 if not found
 600    */
 601   public int lastIndexOf(Object o)
 602   {
 603     int index = size - 1;
 604     Entry e = last;
 605     while (e != null)
 606       {
 607         if (equals(o, e.data))
 608           return index;
 609         index--;
 610         e = e.previous;
 611       }
 612     return -1;
 613   }
 614
 615   /**
 616    * Obtain a ListIterator over this list, starting at a given index. The
 617    * ListIterator returned by this method supports the add, remove and set
 618    * methods.
 619    *
 620    * @param index the index of the element to be returned by the first call to
 621    *        next(), or size() to be initially positioned at the end of the list
 622    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 623    */
 624   public ListIterator listIterator(int index)
 625   {
 626     checkBoundsInclusive(index);
 627     return new LinkedListItr(index);
 628   }
 629
 630   /**
 631    * Create a shallow copy of this LinkedList (the elements are not cloned).
 632    *
 633    * @return an object of the same class as this object, containing the
 634    *         same elements in the same order
 635    */
 636   public Object clone()
 637   {
 638     LinkedList copy = null;
 639     try
 640       {
 641         copy = (LinkedList) super.clone();
 642       }
 643     catch (CloneNotSupportedException ex)
 644       {
 645       }
 646     copy.clear();
 647     copy.addAll(this);
 648     return copy;
 649   }
 650
 651   /**
 652    * Returns an array which contains the elements of the list in order.
 653    *
 654    * @return an array containing the list elements
 655    */
 656   public Object[] toArray()
 657   {
 658     Object[] array = new Object[size];
 659     Entry e = first;
 660     for (int i = 0; i < size; i++)
 661       {
 662         array[i] = e.data;
 663         e = e.next;
 664       }
 665     return array;
 666   }
 667
 668   /**
 669    * Returns an Array whose component type is the runtime component type of
 670    * the passed-in Array.  The returned Array is populated with all of the
 671    * elements in this LinkedList.  If the passed-in Array is not large enough
 672    * to store all of the elements in this List, a new Array will be created
 673    * and returned; if the passed-in Array is <i>larger</i> than the size
 674    * of this List, then size() index will be set to null.
 675    *
 676    * @param a the passed-in Array
 677    * @return an array representation of this list
 678    * @throws ArrayStoreException if the runtime type of a does not allow
 679    *         an element in this list
 680    * @throws NullPointerException if a is null
 681    */
 682   public Object[] toArray(Object[] a)
 683   {
 684     if (a.length < size)
 685       a = (Object[]) Array.newInstance(a.getClass().getComponentType(), size);
 686     else if (a.length > size)
 687       a[size] = null;
 688     Entry e = first;
 689     for (int i = 0; i < size; i++)
 690       {
 691         a[i] = e.data;
 692         e = e.next;
 693       }
 694     return a;
 695   }
 696
 697   /**
 698    * Serializes this object to the given stream.
 699    *
 700    * @param s the stream to write to
 701    * @throws IOException if the underlying stream fails
 702    * @serialData the size of the list (int), followed by all the elements
 703    *             (Object) in proper order
 704    */
 705   private void writeObject(ObjectOutputStream s) throws IOException
 706   {
 707     s.defaultWriteObject();
 708     s.writeInt(size);
 709     Entry e = first;
 710     while (e != null)
 711       {
 712         s.writeObject(e.data);
 713         e = e.next;
 714       }
 715   }
 716
 717   /**
 718    * Deserializes this object from the given stream.
 719    *
 720    * @param s the stream to read from
 721    * @throws ClassNotFoundException if the underlying stream fails
 722    * @throws IOException if the underlying stream fails
 723    * @serialData the size of the list (int), followed by all the elements
 724    *             (Object) in proper order
 725    */
 726   private void readObject(ObjectInputStream s)
 727     throws IOException, ClassNotFoundException
 728   {
 729     s.defaultReadObject();
 730     int i = s.readInt();
 731     while (--i >= 0)
 732       addLastEntry(new Entry(s.readObject()));
 733   }
 734
 735   /**
 736    * A ListIterator over the list. This class keeps track of its
 737    * position in the list and the two list entries it is between.
 738    *
 739    * @author Original author unknown
 740    * @author Eric Blake <ebb9@email.byu.edu>
 741    */
 742   private final class LinkedListItr implements ListIterator
 743   {
 744     /** Number of modifications we know about. */
 745     private int knownMod = modCount;
 746
 747     /** Entry that will be returned by next(). */
 748     private Entry next;
 749
 750     /** Entry that will be returned by previous(). */
 751     private Entry previous;
 752
 753     /** Entry that will be affected by remove() or set(). */
 754     private Entry lastReturned;
 755
 756     /** Index of `next'. */
 757     private int position;
 758
 759     /**
 760      * Initialize the iterator.
 761      *
 762      * @param index the initial index
 763      */
 764     LinkedListItr(int index)
 765     {
 766       if (index == size)
 767         {
 768           next = null;
 769           previous = last;
 770         }
 771       else
 772         {
 773           next = getEntry(index);
 774           previous = next.previous;
 775         }
 776       position = index;
 777     }
 778
 779     /**
 780      * Checks for iterator consistency.
 781      *
 782      * @throws ConcurrentModificationException if the list was modified
 783      */
 784     private void checkMod()
 785     {
 786       if (knownMod != modCount)
 787         throw new ConcurrentModificationException();
 788     }
 789
 790     /**
 791      * Returns the index of the next element.
 792      *
 793      * @return the next index
 794      * @throws ConcurrentModificationException if the list was modified
 795      */
 796     public int nextIndex()
 797     {
 798       checkMod();
 799       return position;
 800     }
 801
 802     /**
 803      * Returns the index of the previous element.
 804      *
 805      * @return the previous index
 806      * @throws ConcurrentModificationException if the list was modified
 807      */
 808     public int previousIndex()
 809     {
 810       checkMod();
 811       return position - 1;
 812     }
 813
 814     /**
 815      * Returns true if more elements exist via next.
 816      *
 817      * @return true if next will succeed
 818      * @throws ConcurrentModificationException if the list was modified
 819      */
 820     public boolean hasNext()
 821     {
 822       checkMod();
 823       return (next != null);
 824     }
 825
 826     /**
 827      * Returns true if more elements exist via previous.
 828      *
 829      * @return true if previous will succeed
 830      * @throws ConcurrentModificationException if the list was modified
 831      */
 832     public boolean hasPrevious()
 833     {
 834       checkMod();
 835       return (previous != null);
 836     }
 837
 838     /**
 839      * Returns the next element.
 840      *
 841      * @return the next element
 842      * @throws ConcurrentModificationException if the list was modified
 843      * @throws NoSuchElementException if there is no next
 844      */
 845     public Object next()
 846     {
 847       checkMod();
 848       if (next == null)
 849         throw new NoSuchElementException();
 850       position++;
 851       lastReturned = previous = next;
 852       next = lastReturned.next;
 853       return lastReturned.data;
 854     }
 855
 856     /**
 857      * Returns the previous element.
 858      *
 859      * @return the previous element
 860      * @throws ConcurrentModificationException if the list was modified
 861      * @throws NoSuchElementException if there is no previous
 862      */
 863     public Object previous()
 864     {
 865       checkMod();
 866       if (previous == null)
 867         throw new NoSuchElementException();
 868       position--;
 869       lastReturned = next = previous;
 870       previous = lastReturned.previous;
 871       return lastReturned.data;
 872     }
 873
 874     /**
 875      * Remove the most recently returned element from the list.
 876      *
 877      * @throws ConcurrentModificationException if the list was modified
 878      * @throws IllegalStateException if there was no last element
 879      */
 880     public void remove()
 881     {
 882       checkMod();
 883       if (lastReturned == null)
 884         throw new IllegalStateException();
 885
 886       // Adjust the position to before the removed element, if the element
 887       // being removed is behind the cursor.
 888       if (lastReturned == previous)
 889         position--;
 890
 891       next = lastReturned.next;
 892       previous = lastReturned.previous;
 893       removeEntry(lastReturned);
 894       knownMod++;
 895
 896       lastReturned = null;
 897     }
 898
 899     /**
 900      * Adds an element between the previous and next, and advance to the next.
 901      *
 902      * @param o the element to add
 903      * @throws ConcurrentModificationException if the list was modified
 904      */
 905     public void add(Object o)
 906     {
 907       checkMod();
 908       modCount++;
 909       knownMod++;
 910       size++;
 911       position++;
 912       Entry e = new Entry(o);
 913       e.previous = previous;
 914       e.next = next;
 915
 916       if (previous != null)
 917         previous.next = e;
 918       else
 919         first = e;
 920
 921       if (next != null)
 922         next.previous = e;
 923       else
 924         last = e;
 925
 926       previous = e;
 927       lastReturned = null;
 928     }
 929
 930     /**
 931      * Changes the contents of the element most recently returned.
 932      *
 933      * @param o the new element
 934      * @throws ConcurrentModificationException if the list was modified
 935      * @throws IllegalStateException if there was no last element
 936      */
 937     public void set(Object o)
 938     {
 939       checkMod();
 940       if (lastReturned == null)
 941         throw new IllegalStateException();
 942       lastReturned.data = o;
 943     }
 944   } // class LinkedListItr
 945 }