libjava/java/util/LinkedList.java

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