src/share/classes/java/util/ArrayList.java

Print this page
rev 9490 : 8035584: ArrayList(c) should avoid inflation if c is empty
Reviewed-by: martin


  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.util.function.Consumer;
  29 import java.util.function.Predicate;
  30 import java.util.function.UnaryOperator;
  31 
  32 /**
  33  * Resizable-array implementation of the <tt>List</tt> interface.  Implements
  34  * all optional list operations, and permits all elements, including
  35  * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
  36  * this class provides methods to manipulate the size of the array that is
  37  * used internally to store the list.  (This class is roughly equivalent to
  38  * <tt>Vector</tt>, except that it is unsynchronized.)
  39  *
  40  * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
  41  * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
  42  * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
  43  * that is, adding n elements requires O(n) time.  All of the other operations
  44  * run in linear time (roughly speaking).  The constant factor is low compared
  45  * to that for the <tt>LinkedList</tt> implementation.
  46  *
  47  * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
  48  * the size of the array used to store the elements in the list.  It is always
  49  * at least as large as the list size.  As elements are added to an ArrayList,
  50  * its capacity grows automatically.  The details of the growth policy are not
  51  * specified beyond the fact that adding an element has constant amortized
  52  * time cost.
  53  *
  54  * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
  55  * before adding a large number of elements using the <tt>ensureCapacity</tt>
  56  * operation.  This may reduce the amount of incremental reallocation.
  57  *
  58  * <p><strong>Note that this implementation is not synchronized.</strong>
  59  * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
  60  * and at least one of the threads modifies the list structurally, it
  61  * <i>must</i> be synchronized externally.  (A structural modification is
  62  * any operation that adds or deletes one or more elements, or explicitly
  63  * resizes the backing array; merely setting the value of an element is not
  64  * a structural modification.)  This is typically accomplished by
  65  * synchronizing on some object that naturally encapsulates the list.
  66  *
  67  * If no such object exists, the list should be "wrapped" using the
  68  * {@link Collections#synchronizedList Collections.synchronizedList}
  69  * method.  This is best done at creation time, to prevent accidental
  70  * unsynchronized access to the list:<pre>
  71  *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
  72  *
  73  * <p><a name="fail-fast">
  74  * The iterators returned by this class's {@link #iterator() iterator} and
  75  * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
  76  * if the list is structurally modified at any time after the iterator is
  77  * created, in any way except through the iterator's own
  78  * {@link ListIterator#remove() remove} or
  79  * {@link ListIterator#add(Object) add} methods, the iterator will throw a
  80  * {@link ConcurrentModificationException}.  Thus, in the face of
  81  * concurrent modification, the iterator fails quickly and cleanly, rather
  82  * than risking arbitrary, non-deterministic behavior at an undetermined
  83  * time in the future.
  84  *
  85  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  86  * as it is, generally speaking, impossible to make any hard guarantees in the
  87  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  88  * throw {@code ConcurrentModificationException} on a best-effort basis.
  89  * Therefore, it would be wrong to write a program that depended on this
  90  * exception for its correctness:  <i>the fail-fast behavior of iterators
  91  * should be used only to detect bugs.</i>
  92  *
  93  * <p>This class is a member of the
  94  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  95  * Java Collections Framework</a>.
  96  *


  97  * @author  Josh Bloch
  98  * @author  Neal Gafter
  99  * @see     Collection
 100  * @see     List
 101  * @see     LinkedList
 102  * @see     Vector
 103  * @since   1.2
 104  */
 105 
 106 public class ArrayList<E> extends AbstractList<E>
 107         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 108 {
 109     private static final long serialVersionUID = 8683452581122892189L;
 110 
 111     /**
 112      * Default initial capacity.
 113      */
 114     private static final int DEFAULT_CAPACITY = 10;
 115 
 116     /**


 124      * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 125      * DEFAULT_CAPACITY when the first element is added.
 126      */
 127     transient Object[] elementData; // non-private to simplify nested class access
 128 
 129     /**
 130      * The size of the ArrayList (the number of elements it contains).
 131      *
 132      * @serial
 133      */
 134     private int size;
 135 
 136     /**
 137      * Constructs an empty list with the specified initial capacity.
 138      *
 139      * @param  initialCapacity  the initial capacity of the list
 140      * @throws IllegalArgumentException if the specified initial capacity
 141      *         is negative
 142      */
 143     public ArrayList(int initialCapacity) {
 144         super();
 145         if (initialCapacity < 0)



 146             throw new IllegalArgumentException("Illegal Capacity: "+
 147                                                initialCapacity);
 148         this.elementData = new Object[initialCapacity];
 149     }
 150 
 151     /**
 152      * Constructs an empty list with an initial capacity of ten.
 153      */
 154     public ArrayList() {
 155         super();
 156         this.elementData = EMPTY_ELEMENTDATA;
 157     }
 158 
 159     /**
 160      * Constructs a list containing the elements of the specified
 161      * collection, in the order they are returned by the collection's
 162      * iterator.
 163      *
 164      * @param c the collection whose elements are to be placed into this list
 165      * @throws NullPointerException if the specified collection is null
 166      */
 167     public ArrayList(Collection<? extends E> c) {

 168         elementData = c.toArray();
 169         size = elementData.length;
 170         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 171         if (elementData.getClass() != Object[].class)
 172             elementData = Arrays.copyOf(elementData, size, Object[].class);



 173     }
 174 
 175     /**
 176      * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 177      * list's current size.  An application can use this operation to minimize
 178      * the storage of an <tt>ArrayList</tt> instance.
 179      */
 180     public void trimToSize() {
 181         modCount++;
 182         if (size < elementData.length) {
 183             elementData = Arrays.copyOf(elementData, size);
 184         }
 185     }
 186 
 187     /**
 188      * Increases the capacity of this <tt>ArrayList</tt> instance, if
 189      * necessary, to ensure that it can hold at least the number of elements
 190      * specified by the minimum capacity argument.
 191      *
 192      * @param   minCapacity   the desired minimum capacity
 193      */
 194     public void ensureCapacity(int minCapacity) {
 195         int minExpand = (elementData != EMPTY_ELEMENTDATA)
 196             // any size if real element table
 197             ? 0
 198             // larger than default for empty table. It's already supposed to be
 199             // at default size.
 200             : DEFAULT_CAPACITY;
 201 
 202         if (minCapacity > minExpand) {
 203             ensureExplicitCapacity(minCapacity);
 204         }
 205     }
 206 
 207     private void ensureCapacityInternal(int minCapacity) {
 208         if (elementData == EMPTY_ELEMENTDATA) {


 247     }
 248 
 249     private static int hugeCapacity(int minCapacity) {
 250         if (minCapacity < 0) // overflow
 251             throw new OutOfMemoryError();
 252         return (minCapacity > MAX_ARRAY_SIZE) ?
 253             Integer.MAX_VALUE :
 254             MAX_ARRAY_SIZE;
 255     }
 256 
 257     /**
 258      * Returns the number of elements in this list.
 259      *
 260      * @return the number of elements in this list
 261      */
 262     public int size() {
 263         return size;
 264     }
 265 
 266     /**
 267      * Returns <tt>true</tt> if this list contains no elements.
 268      *
 269      * @return <tt>true</tt> if this list contains no elements
 270      */
 271     public boolean isEmpty() {
 272         return size == 0;
 273     }
 274 
 275     /**
 276      * Returns <tt>true</tt> if this list contains the specified element.
 277      * More formally, returns <tt>true</tt> if and only if this list contains
 278      * at least one element <tt>e</tt> such that
 279      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 280      *
 281      * @param o element whose presence in this list is to be tested
 282      * @return <tt>true</tt> if this list contains the specified element
 283      */
 284     public boolean contains(Object o) {
 285         return indexOf(o) >= 0;
 286     }
 287 
 288     /**
 289      * Returns the index of the first occurrence of the specified element
 290      * in this list, or -1 if this list does not contain the element.
 291      * More formally, returns the lowest index <tt>i</tt> such that
 292      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 293      * or -1 if there is no such index.
 294      */
 295     public int indexOf(Object o) {
 296         if (o == null) {
 297             for (int i = 0; i < size; i++)
 298                 if (elementData[i]==null)
 299                     return i;
 300         } else {
 301             for (int i = 0; i < size; i++)
 302                 if (o.equals(elementData[i]))
 303                     return i;
 304         }
 305         return -1;
 306     }
 307 
 308     /**
 309      * Returns the index of the last occurrence of the specified element
 310      * in this list, or -1 if this list does not contain the element.
 311      * More formally, returns the highest index <tt>i</tt> such that
 312      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 313      * or -1 if there is no such index.
 314      */
 315     public int lastIndexOf(Object o) {
 316         if (o == null) {
 317             for (int i = size-1; i >= 0; i--)
 318                 if (elementData[i]==null)
 319                     return i;
 320         } else {
 321             for (int i = size-1; i >= 0; i--)
 322                 if (o.equals(elementData[i]))
 323                     return i;
 324         }
 325         return -1;
 326     }
 327 
 328     /**
 329      * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
 330      * elements themselves are not copied.)
 331      *
 332      * @return a clone of this <tt>ArrayList</tt> instance
 333      */
 334     public Object clone() {
 335         try {
 336             ArrayList<?> v = (ArrayList<?>) super.clone();
 337             v.elementData = Arrays.copyOf(elementData, size);
 338             v.modCount = 0;
 339             return v;
 340         } catch (CloneNotSupportedException e) {
 341             // this shouldn't happen, since we are Cloneable
 342             throw new InternalError(e);
 343         }
 344     }
 345 
 346     /**
 347      * Returns an array containing all of the elements in this list
 348      * in proper sequence (from first to last element).
 349      *
 350      * <p>The returned array will be "safe" in that no references to it are
 351      * maintained by this list.  (In other words, this method must allocate
 352      * a new array).  The caller is thus free to modify the returned array.


 355      * APIs.
 356      *
 357      * @return an array containing all of the elements in this list in
 358      *         proper sequence
 359      */
 360     public Object[] toArray() {
 361         return Arrays.copyOf(elementData, size);
 362     }
 363 
 364     /**
 365      * Returns an array containing all of the elements in this list in proper
 366      * sequence (from first to last element); the runtime type of the returned
 367      * array is that of the specified array.  If the list fits in the
 368      * specified array, it is returned therein.  Otherwise, a new array is
 369      * allocated with the runtime type of the specified array and the size of
 370      * this list.
 371      *
 372      * <p>If the list fits in the specified array with room to spare
 373      * (i.e., the array has more elements than the list), the element in
 374      * the array immediately following the end of the collection is set to
 375      * <tt>null</tt>.  (This is useful in determining the length of the
 376      * list <i>only</i> if the caller knows that the list does not contain
 377      * any null elements.)
 378      *
 379      * @param a the array into which the elements of the list are to
 380      *          be stored, if it is big enough; otherwise, a new array of the
 381      *          same runtime type is allocated for this purpose.
 382      * @return an array containing the elements of the list
 383      * @throws ArrayStoreException if the runtime type of the specified array
 384      *         is not a supertype of the runtime type of every element in
 385      *         this list
 386      * @throws NullPointerException if the specified array is null
 387      */
 388     @SuppressWarnings("unchecked")
 389     public <T> T[] toArray(T[] a) {
 390         if (a.length < size)
 391             // Make a new array of a's runtime type, but my contents:
 392             return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 393         System.arraycopy(elementData, 0, a, 0, size);
 394         if (a.length > size)
 395             a[size] = null;


 420      * Replaces the element at the specified position in this list with
 421      * the specified element.
 422      *
 423      * @param index index of the element to replace
 424      * @param element element to be stored at the specified position
 425      * @return the element previously at the specified position
 426      * @throws IndexOutOfBoundsException {@inheritDoc}
 427      */
 428     public E set(int index, E element) {
 429         rangeCheck(index);
 430 
 431         E oldValue = elementData(index);
 432         elementData[index] = element;
 433         return oldValue;
 434     }
 435 
 436     /**
 437      * Appends the specified element to the end of this list.
 438      *
 439      * @param e element to be appended to this list
 440      * @return <tt>true</tt> (as specified by {@link Collection#add})
 441      */
 442     public boolean add(E e) {
 443         ensureCapacityInternal(size + 1);  // Increments modCount!!
 444         elementData[size++] = e;
 445         return true;
 446     }
 447 
 448     /**
 449      * Inserts the specified element at the specified position in this
 450      * list. Shifts the element currently at that position (if any) and
 451      * any subsequent elements to the right (adds one to their indices).
 452      *
 453      * @param index index at which the specified element is to be inserted
 454      * @param element element to be inserted
 455      * @throws IndexOutOfBoundsException {@inheritDoc}
 456      */
 457     public void add(int index, E element) {
 458         rangeCheckForAdd(index);
 459 
 460         ensureCapacityInternal(size + 1);  // Increments modCount!!


 475      */
 476     public E remove(int index) {
 477         rangeCheck(index);
 478 
 479         modCount++;
 480         E oldValue = elementData(index);
 481 
 482         int numMoved = size - index - 1;
 483         if (numMoved > 0)
 484             System.arraycopy(elementData, index+1, elementData, index,
 485                              numMoved);
 486         elementData[--size] = null; // clear to let GC do its work
 487 
 488         return oldValue;
 489     }
 490 
 491     /**
 492      * Removes the first occurrence of the specified element from this list,
 493      * if it is present.  If the list does not contain the element, it is
 494      * unchanged.  More formally, removes the element with the lowest index
 495      * <tt>i</tt> such that
 496      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 497      * (if such an element exists).  Returns <tt>true</tt> if this list
 498      * contained the specified element (or equivalently, if this list
 499      * changed as a result of the call).
 500      *
 501      * @param o element to be removed from this list, if present
 502      * @return <tt>true</tt> if this list contained the specified element
 503      */
 504     public boolean remove(Object o) {
 505         if (o == null) {
 506             for (int index = 0; index < size; index++)
 507                 if (elementData[index] == null) {
 508                     fastRemove(index);
 509                     return true;
 510                 }
 511         } else {
 512             for (int index = 0; index < size; index++)
 513                 if (o.equals(elementData[index])) {
 514                     fastRemove(index);
 515                     return true;
 516                 }
 517         }
 518         return false;
 519     }
 520 
 521     /*
 522      * Private remove method that skips bounds checking and does not


 538     public void clear() {
 539         modCount++;
 540 
 541         // clear to let GC do its work
 542         for (int i = 0; i < size; i++)
 543             elementData[i] = null;
 544 
 545         size = 0;
 546     }
 547 
 548     /**
 549      * Appends all of the elements in the specified collection to the end of
 550      * this list, in the order that they are returned by the
 551      * specified collection's Iterator.  The behavior of this operation is
 552      * undefined if the specified collection is modified while the operation
 553      * is in progress.  (This implies that the behavior of this call is
 554      * undefined if the specified collection is this list, and this
 555      * list is nonempty.)
 556      *
 557      * @param c collection containing elements to be added to this list
 558      * @return <tt>true</tt> if this list changed as a result of the call
 559      * @throws NullPointerException if the specified collection is null
 560      */
 561     public boolean addAll(Collection<? extends E> c) {
 562         Object[] a = c.toArray();
 563         int numNew = a.length;
 564         ensureCapacityInternal(size + numNew);  // Increments modCount
 565         System.arraycopy(a, 0, elementData, size, numNew);
 566         size += numNew;
 567         return numNew != 0;
 568     }
 569 
 570     /**
 571      * Inserts all of the elements in the specified collection into this
 572      * list, starting at the specified position.  Shifts the element
 573      * currently at that position (if any) and any subsequent elements to
 574      * the right (increases their indices).  The new elements will appear
 575      * in the list in the order that they are returned by the
 576      * specified collection's iterator.
 577      *
 578      * @param index index at which to insert the first element from the
 579      *              specified collection
 580      * @param c collection containing elements to be added to this list
 581      * @return <tt>true</tt> if this list changed as a result of the call
 582      * @throws IndexOutOfBoundsException {@inheritDoc}
 583      * @throws NullPointerException if the specified collection is null
 584      */
 585     public boolean addAll(int index, Collection<? extends E> c) {
 586         rangeCheckForAdd(index);
 587 
 588         Object[] a = c.toArray();
 589         int numNew = a.length;
 590         ensureCapacityInternal(size + numNew);  // Increments modCount
 591 
 592         int numMoved = size - index;
 593         if (numMoved > 0)
 594             System.arraycopy(elementData, index, elementData, index + numNew,
 595                              numMoved);
 596 
 597         System.arraycopy(a, 0, elementData, index, numNew);
 598         size += numNew;
 599         return numNew != 0;
 600     }
 601 


 709             // even if c.contains() throws.
 710             if (r != size) {
 711                 System.arraycopy(elementData, r,
 712                                  elementData, w,
 713                                  size - r);
 714                 w += size - r;
 715             }
 716             if (w != size) {
 717                 // clear to let GC do its work
 718                 for (int i = w; i < size; i++)
 719                     elementData[i] = null;
 720                 modCount += size - w;
 721                 size = w;
 722                 modified = true;
 723             }
 724         }
 725         return modified;
 726     }
 727 
 728     /**
 729      * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 730      * is, serialize it).
 731      *
 732      * @serialData The length of the array backing the <tt>ArrayList</tt>
 733      *             instance is emitted (int), followed by all of its elements
 734      *             (each an <tt>Object</tt>) in the proper order.
 735      */
 736     private void writeObject(java.io.ObjectOutputStream s)
 737         throws java.io.IOException{
 738         // Write out element count, and any hidden stuff
 739         int expectedModCount = modCount;
 740         s.defaultWriteObject();
 741 
 742         // Write out size as capacity for behavioural compatibility with clone()
 743         s.writeInt(size);
 744 
 745         // Write out all elements in the proper order.
 746         for (int i=0; i<size; i++) {
 747             s.writeObject(elementData[i]);
 748         }
 749 
 750         if (modCount != expectedModCount) {
 751             throw new ConcurrentModificationException();
 752         }
 753     }
 754 
 755     /**
 756      * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 757      * deserialize it).
 758      */
 759     private void readObject(java.io.ObjectInputStream s)
 760         throws java.io.IOException, ClassNotFoundException {
 761         elementData = EMPTY_ELEMENTDATA;
 762 
 763         // Read in size, and any hidden stuff
 764         s.defaultReadObject();
 765 
 766         // Read in capacity
 767         s.readInt(); // ignored
 768 
 769         if (size > 0) {
 770             // be like clone(), allocate array based upon size not capacity
 771             ensureCapacityInternal(size);
 772 
 773             Object[] a = elementData;
 774             // Read in all elements in the proper order.
 775             for (int i=0; i<size; i++) {
 776                 a[i] = s.readObject();




  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.util.function.Consumer;
  29 import java.util.function.Predicate;
  30 import java.util.function.UnaryOperator;
  31 
  32 /**
  33  * Resizable-array implementation of the {@code List} interface.  Implements
  34  * all optional list operations, and permits all elements, including
  35  * {@code null}.  In addition to implementing the {@code List} interface,
  36  * this class provides methods to manipulate the size of the array that is
  37  * used internally to store the list.  (This class is roughly equivalent to
  38  * {@code Vector}, except that it is unsynchronized.)
  39  *
  40  * <p>The {@code size}, {@code isEmpty}, {@code get}, {@code set},
  41  * {@code iterator}, and {@code listIterator} operations run in constant
  42  * time.  The {@code add} operation runs in <i>amortized constant time</i>,
  43  * that is, adding n elements requires O(n) time.  All of the other operations
  44  * run in linear time (roughly speaking).  The constant factor is low compared
  45  * to that for the {@code LinkedList} implementation.
  46  *
  47  * <p>Each {@code ArrayList} instance has a <i>capacity</i>.  The capacity is
  48  * the size of the array used to store the elements in the list.  It is always
  49  * at least as large as the list size.  As elements are added to an ArrayList,
  50  * its capacity grows automatically.  The details of the growth policy are not
  51  * specified beyond the fact that adding an element has constant amortized
  52  * time cost.
  53  *
  54  * <p>An application can increase the capacity of an {@code ArrayList} instance
  55  * before adding a large number of elements using the {@code ensureCapacity}
  56  * operation.  This may reduce the amount of incremental reallocation.
  57  *
  58  * <p><strong>Note that this implementation is not synchronized.</strong>
  59  * If multiple threads access an {@code ArrayList} instance concurrently,
  60  * and at least one of the threads modifies the list structurally, it
  61  * <i>must</i> be synchronized externally.  (A structural modification is
  62  * any operation that adds or deletes one or more elements, or explicitly
  63  * resizes the backing array; merely setting the value of an element is not
  64  * a structural modification.)  This is typically accomplished by
  65  * synchronizing on some object that naturally encapsulates the list.
  66  *
  67  * If no such object exists, the list should be "wrapped" using the
  68  * {@link Collections#synchronizedList Collections.synchronizedList}
  69  * method.  This is best done at creation time, to prevent accidental
  70  * unsynchronized access to the list:<pre>
  71  *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
  72  *
  73  * <p><a name="fail-fast">
  74  * The iterators returned by this class's {@link #iterator() iterator} and
  75  * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
  76  * if the list is structurally modified at any time after the iterator is
  77  * created, in any way except through the iterator's own
  78  * {@link ListIterator#remove() remove} or
  79  * {@link ListIterator#add(Object) add} methods, the iterator will throw a
  80  * {@link ConcurrentModificationException}.  Thus, in the face of
  81  * concurrent modification, the iterator fails quickly and cleanly, rather
  82  * than risking arbitrary, non-deterministic behavior at an undetermined
  83  * time in the future.
  84  *
  85  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  86  * as it is, generally speaking, impossible to make any hard guarantees in the
  87  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  88  * throw {@code ConcurrentModificationException} on a best-effort basis.
  89  * Therefore, it would be wrong to write a program that depended on this
  90  * exception for its correctness:  <i>the fail-fast behavior of iterators
  91  * should be used only to detect bugs.</i>
  92  *
  93  * <p>This class is a member of the
  94  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  95  * Java Collections Framework</a>.
  96  *
  97  * @param <E> the type of elements in this list
  98  *
  99  * @author  Josh Bloch
 100  * @author  Neal Gafter
 101  * @see     Collection
 102  * @see     List
 103  * @see     LinkedList
 104  * @see     Vector
 105  * @since   1.2
 106  */
 107 
 108 public class ArrayList<E> extends AbstractList<E>
 109         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 110 {
 111     private static final long serialVersionUID = 8683452581122892189L;
 112 
 113     /**
 114      * Default initial capacity.
 115      */
 116     private static final int DEFAULT_CAPACITY = 10;
 117 
 118     /**


 126      * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 127      * DEFAULT_CAPACITY when the first element is added.
 128      */
 129     transient Object[] elementData; // non-private to simplify nested class access
 130 
 131     /**
 132      * The size of the ArrayList (the number of elements it contains).
 133      *
 134      * @serial
 135      */
 136     private int size;
 137 
 138     /**
 139      * Constructs an empty list with the specified initial capacity.
 140      *
 141      * @param  initialCapacity  the initial capacity of the list
 142      * @throws IllegalArgumentException if the specified initial capacity
 143      *         is negative
 144      */
 145     public ArrayList(int initialCapacity) {
 146         if (initialCapacity > 0) {
 147             this.elementData = new Object[initialCapacity];
 148         } else if (initialCapacity == 0) {
 149             this.elementData = EMPTY_ELEMENTDATA;
 150         } else {
 151             throw new IllegalArgumentException("Illegal Capacity: "+
 152                                                initialCapacity);
 153         }
 154     }
 155 
 156     /**
 157      * Constructs an empty list with an initial capacity of ten.
 158      */
 159     public ArrayList() {

 160         this.elementData = EMPTY_ELEMENTDATA;
 161     }
 162 
 163     /**
 164      * Constructs a list containing the elements of the specified
 165      * collection, in the order they are returned by the collection's
 166      * iterator.
 167      *
 168      * @param c the collection whose elements are to be placed into this list
 169      * @throws NullPointerException if the specified collection is null
 170      */
 171     public ArrayList(Collection<? extends E> c) {
 172         if (!c.isEmpty()) {
 173             elementData = c.toArray();
 174             size = elementData.length;
 175             // c.toArray might (incorrectly) not return Object[] (see 6260652)
 176             if (elementData.getClass() != Object[].class)
 177                 elementData = Arrays.copyOf(elementData, size, Object[].class);
 178         } else {
 179             this.elementData = EMPTY_ELEMENTDATA;
 180         }
 181     }
 182 
 183     /**
 184      * Trims the capacity of this {@code ArrayList} instance to be the
 185      * list's current size.  An application can use this operation to minimize
 186      * the storage of an {@code ArrayList} instance.
 187      */
 188     public void trimToSize() {
 189         modCount++;
 190         if (size < elementData.length) {
 191             elementData = Arrays.copyOf(elementData, size);
 192         }
 193     }
 194 
 195     /**
 196      * Increases the capacity of this {@code ArrayList} instance, if
 197      * necessary, to ensure that it can hold at least the number of elements
 198      * specified by the minimum capacity argument.
 199      *
 200      * @param   minCapacity   the desired minimum capacity
 201      */
 202     public void ensureCapacity(int minCapacity) {
 203         int minExpand = (elementData != EMPTY_ELEMENTDATA)
 204             // any size if real element table
 205             ? 0
 206             // larger than default for empty table. It's already supposed to be
 207             // at default size.
 208             : DEFAULT_CAPACITY;
 209 
 210         if (minCapacity > minExpand) {
 211             ensureExplicitCapacity(minCapacity);
 212         }
 213     }
 214 
 215     private void ensureCapacityInternal(int minCapacity) {
 216         if (elementData == EMPTY_ELEMENTDATA) {


 255     }
 256 
 257     private static int hugeCapacity(int minCapacity) {
 258         if (minCapacity < 0) // overflow
 259             throw new OutOfMemoryError();
 260         return (minCapacity > MAX_ARRAY_SIZE) ?
 261             Integer.MAX_VALUE :
 262             MAX_ARRAY_SIZE;
 263     }
 264 
 265     /**
 266      * Returns the number of elements in this list.
 267      *
 268      * @return the number of elements in this list
 269      */
 270     public int size() {
 271         return size;
 272     }
 273 
 274     /**
 275      * Returns {@code true} if this list contains no elements.
 276      *
 277      * @return {@code true} if this list contains no elements
 278      */
 279     public boolean isEmpty() {
 280         return size == 0;
 281     }
 282 
 283     /**
 284      * Returns {@code true} if this list contains the specified element.
 285      * More formally, returns {@code true} if and only if this list contains
 286      * at least one element {@code e} such that
 287      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 288      *
 289      * @param o element whose presence in this list is to be tested
 290      * @return {@code true} if this list contains the specified element
 291      */
 292     public boolean contains(Object o) {
 293         return indexOf(o) >= 0;
 294     }
 295 
 296     /**
 297      * Returns the index of the first occurrence of the specified element
 298      * in this list, or -1 if this list does not contain the element.
 299      * More formally, returns the lowest index {@code i} such that
 300      * {@code (o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))},
 301      * or -1 if there is no such index.
 302      */
 303     public int indexOf(Object o) {
 304         if (o == null) {
 305             for (int i = 0; i < size; i++)
 306                 if (elementData[i]==null)
 307                     return i;
 308         } else {
 309             for (int i = 0; i < size; i++)
 310                 if (o.equals(elementData[i]))
 311                     return i;
 312         }
 313         return -1;
 314     }
 315 
 316     /**
 317      * Returns the index of the last occurrence of the specified element
 318      * in this list, or -1 if this list does not contain the element.
 319      * More formally, returns the highest index {@code i} such that
 320      * {@code (o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))},
 321      * or -1 if there is no such index.
 322      */
 323     public int lastIndexOf(Object o) {
 324         if (o == null) {
 325             for (int i = size-1; i >= 0; i--)
 326                 if (elementData[i]==null)
 327                     return i;
 328         } else {
 329             for (int i = size-1; i >= 0; i--)
 330                 if (o.equals(elementData[i]))
 331                     return i;
 332         }
 333         return -1;
 334     }
 335 
 336     /**
 337      * Returns a shallow copy of this {@code ArrayList} instance.  (The
 338      * elements themselves are not copied.)
 339      *
 340      * @return a clone of this {@code ArrayList} instance
 341      */
 342     public Object clone() {
 343         try {
 344             ArrayList<?> v = (ArrayList<?>) super.clone();
 345             v.elementData = Arrays.copyOf(elementData, size);
 346             v.modCount = 0;
 347             return v;
 348         } catch (CloneNotSupportedException e) {
 349             // this shouldn't happen, since we are Cloneable
 350             throw new InternalError(e);
 351         }
 352     }
 353 
 354     /**
 355      * Returns an array containing all of the elements in this list
 356      * in proper sequence (from first to last element).
 357      *
 358      * <p>The returned array will be "safe" in that no references to it are
 359      * maintained by this list.  (In other words, this method must allocate
 360      * a new array).  The caller is thus free to modify the returned array.


 363      * APIs.
 364      *
 365      * @return an array containing all of the elements in this list in
 366      *         proper sequence
 367      */
 368     public Object[] toArray() {
 369         return Arrays.copyOf(elementData, size);
 370     }
 371 
 372     /**
 373      * Returns an array containing all of the elements in this list in proper
 374      * sequence (from first to last element); the runtime type of the returned
 375      * array is that of the specified array.  If the list fits in the
 376      * specified array, it is returned therein.  Otherwise, a new array is
 377      * allocated with the runtime type of the specified array and the size of
 378      * this list.
 379      *
 380      * <p>If the list fits in the specified array with room to spare
 381      * (i.e., the array has more elements than the list), the element in
 382      * the array immediately following the end of the collection is set to
 383      * {@code null}.  (This is useful in determining the length of the
 384      * list <i>only</i> if the caller knows that the list does not contain
 385      * any null elements.)
 386      *
 387      * @param a the array into which the elements of the list are to
 388      *          be stored, if it is big enough; otherwise, a new array of the
 389      *          same runtime type is allocated for this purpose.
 390      * @return an array containing the elements of the list
 391      * @throws ArrayStoreException if the runtime type of the specified array
 392      *         is not a supertype of the runtime type of every element in
 393      *         this list
 394      * @throws NullPointerException if the specified array is null
 395      */
 396     @SuppressWarnings("unchecked")
 397     public <T> T[] toArray(T[] a) {
 398         if (a.length < size)
 399             // Make a new array of a's runtime type, but my contents:
 400             return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 401         System.arraycopy(elementData, 0, a, 0, size);
 402         if (a.length > size)
 403             a[size] = null;


 428      * Replaces the element at the specified position in this list with
 429      * the specified element.
 430      *
 431      * @param index index of the element to replace
 432      * @param element element to be stored at the specified position
 433      * @return the element previously at the specified position
 434      * @throws IndexOutOfBoundsException {@inheritDoc}
 435      */
 436     public E set(int index, E element) {
 437         rangeCheck(index);
 438 
 439         E oldValue = elementData(index);
 440         elementData[index] = element;
 441         return oldValue;
 442     }
 443 
 444     /**
 445      * Appends the specified element to the end of this list.
 446      *
 447      * @param e element to be appended to this list
 448      * @return {@code true} (as specified by {@link Collection#add})
 449      */
 450     public boolean add(E e) {
 451         ensureCapacityInternal(size + 1);  // Increments modCount!!
 452         elementData[size++] = e;
 453         return true;
 454     }
 455 
 456     /**
 457      * Inserts the specified element at the specified position in this
 458      * list. Shifts the element currently at that position (if any) and
 459      * any subsequent elements to the right (adds one to their indices).
 460      *
 461      * @param index index at which the specified element is to be inserted
 462      * @param element element to be inserted
 463      * @throws IndexOutOfBoundsException {@inheritDoc}
 464      */
 465     public void add(int index, E element) {
 466         rangeCheckForAdd(index);
 467 
 468         ensureCapacityInternal(size + 1);  // Increments modCount!!


 483      */
 484     public E remove(int index) {
 485         rangeCheck(index);
 486 
 487         modCount++;
 488         E oldValue = elementData(index);
 489 
 490         int numMoved = size - index - 1;
 491         if (numMoved > 0)
 492             System.arraycopy(elementData, index+1, elementData, index,
 493                              numMoved);
 494         elementData[--size] = null; // clear to let GC do its work
 495 
 496         return oldValue;
 497     }
 498 
 499     /**
 500      * Removes the first occurrence of the specified element from this list,
 501      * if it is present.  If the list does not contain the element, it is
 502      * unchanged.  More formally, removes the element with the lowest index
 503      * {@code i} such that
 504      * {@code (o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))}
 505      * (if such an element exists).  Returns {@code true} if this list
 506      * contained the specified element (or equivalently, if this list
 507      * changed as a result of the call).
 508      *
 509      * @param o element to be removed from this list, if present
 510      * @return {@code true} if this list contained the specified element
 511      */
 512     public boolean remove(Object o) {
 513         if (o == null) {
 514             for (int index = 0; index < size; index++)
 515                 if (elementData[index] == null) {
 516                     fastRemove(index);
 517                     return true;
 518                 }
 519         } else {
 520             for (int index = 0; index < size; index++)
 521                 if (o.equals(elementData[index])) {
 522                     fastRemove(index);
 523                     return true;
 524                 }
 525         }
 526         return false;
 527     }
 528 
 529     /*
 530      * Private remove method that skips bounds checking and does not


 546     public void clear() {
 547         modCount++;
 548 
 549         // clear to let GC do its work
 550         for (int i = 0; i < size; i++)
 551             elementData[i] = null;
 552 
 553         size = 0;
 554     }
 555 
 556     /**
 557      * Appends all of the elements in the specified collection to the end of
 558      * this list, in the order that they are returned by the
 559      * specified collection's Iterator.  The behavior of this operation is
 560      * undefined if the specified collection is modified while the operation
 561      * is in progress.  (This implies that the behavior of this call is
 562      * undefined if the specified collection is this list, and this
 563      * list is nonempty.)
 564      *
 565      * @param c collection containing elements to be added to this list
 566      * @return {@code true} if this list changed as a result of the call
 567      * @throws NullPointerException if the specified collection is null
 568      */
 569     public boolean addAll(Collection<? extends E> c) {
 570         Object[] a = c.toArray();
 571         int numNew = a.length;
 572         ensureCapacityInternal(size + numNew);  // Increments modCount
 573         System.arraycopy(a, 0, elementData, size, numNew);
 574         size += numNew;
 575         return numNew != 0;
 576     }
 577 
 578     /**
 579      * Inserts all of the elements in the specified collection into this
 580      * list, starting at the specified position.  Shifts the element
 581      * currently at that position (if any) and any subsequent elements to
 582      * the right (increases their indices).  The new elements will appear
 583      * in the list in the order that they are returned by the
 584      * specified collection's iterator.
 585      *
 586      * @param index index at which to insert the first element from the
 587      *              specified collection
 588      * @param c collection containing elements to be added to this list
 589      * @return {@code true} if this list changed as a result of the call
 590      * @throws IndexOutOfBoundsException {@inheritDoc}
 591      * @throws NullPointerException if the specified collection is null
 592      */
 593     public boolean addAll(int index, Collection<? extends E> c) {
 594         rangeCheckForAdd(index);
 595 
 596         Object[] a = c.toArray();
 597         int numNew = a.length;
 598         ensureCapacityInternal(size + numNew);  // Increments modCount
 599 
 600         int numMoved = size - index;
 601         if (numMoved > 0)
 602             System.arraycopy(elementData, index, elementData, index + numNew,
 603                              numMoved);
 604 
 605         System.arraycopy(a, 0, elementData, index, numNew);
 606         size += numNew;
 607         return numNew != 0;
 608     }
 609 


 717             // even if c.contains() throws.
 718             if (r != size) {
 719                 System.arraycopy(elementData, r,
 720                                  elementData, w,
 721                                  size - r);
 722                 w += size - r;
 723             }
 724             if (w != size) {
 725                 // clear to let GC do its work
 726                 for (int i = w; i < size; i++)
 727                     elementData[i] = null;
 728                 modCount += size - w;
 729                 size = w;
 730                 modified = true;
 731             }
 732         }
 733         return modified;
 734     }
 735 
 736     /**
 737      * Save the state of the {@code ArrayList} instance to a stream (that
 738      * is, serialize it).
 739      *
 740      * @serialData The length of the array backing the {@code ArrayList}
 741      *             instance is emitted (int), followed by all of its elements
 742      *             (each an {@code Object}) in the proper order.
 743      */
 744     private void writeObject(java.io.ObjectOutputStream s)
 745         throws java.io.IOException{
 746         // Write out element count, and any hidden stuff
 747         int expectedModCount = modCount;
 748         s.defaultWriteObject();
 749 
 750         // Write out size as capacity for behavioural compatibility with clone()
 751         s.writeInt(size);
 752 
 753         // Write out all elements in the proper order.
 754         for (int i=0; i<size; i++) {
 755             s.writeObject(elementData[i]);
 756         }
 757 
 758         if (modCount != expectedModCount) {
 759             throw new ConcurrentModificationException();
 760         }
 761     }
 762 
 763     /**
 764      * Reconstitute the {@code ArrayList} instance from a stream (that is,
 765      * deserialize it).
 766      */
 767     private void readObject(java.io.ObjectInputStream s)
 768         throws java.io.IOException, ClassNotFoundException {
 769         elementData = EMPTY_ELEMENTDATA;
 770 
 771         // Read in size, and any hidden stuff
 772         s.defaultReadObject();
 773 
 774         // Read in capacity
 775         s.readInt(); // ignored
 776 
 777         if (size > 0) {
 778             // be like clone(), allocate array based upon size not capacity
 779             ensureCapacityInternal(size);
 780 
 781             Object[] a = elementData;
 782             // Read in all elements in the proper order.
 783             for (int i=0; i<size; i++) {
 784                 a[i] = s.readObject();