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

Print this page
rev 6845 : 80111200: (coll) Optimize empty HashMap and ArrayList
Reviewed-by: mduigou, alanb, bchristi, martin
Contributed-by: Sergey Linetskiy <sergey.linetskiy@oracle.com>, John Rose <john.r.rose@oracle.com>, Mike Duigou <mike.duigou@oracle.com>
   1 /*
   2  * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  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


  88  *
  89  * <p>This class is a member of the
  90  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  91  * Java Collections Framework</a>.
  92  *
  93  * @author  Josh Bloch
  94  * @author  Neal Gafter
  95  * @see     Collection
  96  * @see     List
  97  * @see     LinkedList
  98  * @see     Vector
  99  * @since   1.2
 100  */
 101 
 102 public class ArrayList<E> extends AbstractList<E>
 103         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 104 {
 105     private static final long serialVersionUID = 8683452581122892189L;
 106 
 107     /**










 108      * The array buffer into which the elements of the ArrayList are stored.
 109      * The capacity of the ArrayList is the length of this array buffer.


 110      */
 111     private transient Object[] elementData;
 112 
 113     /**
 114      * The size of the ArrayList (the number of elements it contains).
 115      *
 116      * @serial
 117      */
 118     private int size;
 119 
 120     /**
 121      * Constructs an empty list with the specified initial capacity.
 122      *
 123      * @param  initialCapacity  the initial capacity of the list
 124      * @throws IllegalArgumentException if the specified initial capacity
 125      *         is negative
 126      */
 127     public ArrayList(int initialCapacity) {
 128         super();
 129         if (initialCapacity < 0)
 130             throw new IllegalArgumentException("Illegal Capacity: "+
 131                                                initialCapacity);
 132         this.elementData = new Object[initialCapacity];
 133     }
 134 
 135     /**
 136      * Constructs an empty list with an initial capacity of ten.
 137      */
 138     public ArrayList() {
 139         this(10);

 140     }
 141 
 142     /**
 143      * Constructs a list containing the elements of the specified
 144      * collection, in the order they are returned by the collection's
 145      * iterator.
 146      *
 147      * @param c the collection whose elements are to be placed into this list
 148      * @throws NullPointerException if the specified collection is null
 149      */
 150     public ArrayList(Collection<? extends E> c) {
 151         elementData = c.toArray();
 152         size = elementData.length;
 153         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 154         if (elementData.getClass() != Object[].class)
 155             elementData = Arrays.copyOf(elementData, size, Object[].class);
 156     }
 157 
 158     /**
 159      * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 160      * list's current size.  An application can use this operation to minimize
 161      * the storage of an <tt>ArrayList</tt> instance.
 162      */
 163     public void trimToSize() {
 164         modCount++;
 165         int oldCapacity = elementData.length;
 166         if (size < oldCapacity) {
 167             elementData = Arrays.copyOf(elementData, size);
 168         }
 169     }
 170 
 171     /**
 172      * Increases the capacity of this <tt>ArrayList</tt> instance, if
 173      * necessary, to ensure that it can hold at least the number of elements
 174      * specified by the minimum capacity argument.
 175      *
 176      * @param   minCapacity   the desired minimum capacity
 177      */
 178     public void ensureCapacity(int minCapacity) {
 179         if (minCapacity > 0)
 180             ensureCapacityInternal(minCapacity);








 181     }
 182 
 183     private void ensureCapacityInternal(int minCapacity) {








 184         modCount++;

 185         // overflow-conscious code
 186         if (minCapacity - elementData.length > 0)
 187             grow(minCapacity);
 188     }
 189 
 190     /**
 191      * The maximum size of array to allocate.
 192      * Some VMs reserve some header words in an array.
 193      * Attempts to allocate larger arrays may result in
 194      * OutOfMemoryError: Requested array size exceeds VM limit
 195      */
 196     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 197 
 198     /**
 199      * Increases the capacity to ensure that it can hold at least the
 200      * number of elements specified by the minimum capacity argument.
 201      *
 202      * @param minCapacity the desired minimum capacity
 203      */
 204     private void grow(int minCapacity) {


 433 
 434     /**
 435      * Removes the element at the specified position in this list.
 436      * Shifts any subsequent elements to the left (subtracts one from their
 437      * indices).
 438      *
 439      * @param index the index of the element to be removed
 440      * @return the element that was removed from the list
 441      * @throws IndexOutOfBoundsException {@inheritDoc}
 442      */
 443     public E remove(int index) {
 444         rangeCheck(index);
 445 
 446         modCount++;
 447         E oldValue = elementData(index);
 448 
 449         int numMoved = size - index - 1;
 450         if (numMoved > 0)
 451             System.arraycopy(elementData, index+1, elementData, index,
 452                              numMoved);
 453         elementData[--size] = null; // Let gc do its work
 454 
 455         return oldValue;
 456     }
 457 
 458     /**
 459      * Removes the first occurrence of the specified element from this list,
 460      * if it is present.  If the list does not contain the element, it is
 461      * unchanged.  More formally, removes the element with the lowest index
 462      * <tt>i</tt> such that
 463      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 464      * (if such an element exists).  Returns <tt>true</tt> if this list
 465      * contained the specified element (or equivalently, if this list
 466      * changed as a result of the call).
 467      *
 468      * @param o element to be removed from this list, if present
 469      * @return <tt>true</tt> if this list contained the specified element
 470      */
 471     public boolean remove(Object o) {
 472         if (o == null) {
 473             for (int index = 0; index < size; index++)


 478         } else {
 479             for (int index = 0; index < size; index++)
 480                 if (o.equals(elementData[index])) {
 481                     fastRemove(index);
 482                     return true;
 483                 }
 484         }
 485         return false;
 486     }
 487 
 488     /*
 489      * Private remove method that skips bounds checking and does not
 490      * return the value removed.
 491      */
 492     private void fastRemove(int index) {
 493         modCount++;
 494         int numMoved = size - index - 1;
 495         if (numMoved > 0)
 496             System.arraycopy(elementData, index+1, elementData, index,
 497                              numMoved);
 498         elementData[--size] = null; // Let gc do its work
 499     }
 500 
 501     /**
 502      * Removes all of the elements from this list.  The list will
 503      * be empty after this call returns.
 504      */
 505     public void clear() {
 506         modCount++;
 507 
 508         // Let gc do its work
 509         for (int i = 0; i < size; i++)
 510             elementData[i] = null;
 511 
 512         size = 0;
 513     }
 514 
 515     /**
 516      * Appends all of the elements in the specified collection to the end of
 517      * this list, in the order that they are returned by the
 518      * specified collection's Iterator.  The behavior of this operation is
 519      * undefined if the specified collection is modified while the operation
 520      * is in progress.  (This implies that the behavior of this call is
 521      * undefined if the specified collection is this list, and this
 522      * list is nonempty.)
 523      *
 524      * @param c collection containing elements to be added to this list
 525      * @return <tt>true</tt> if this list changed as a result of the call
 526      * @throws NullPointerException if the specified collection is null
 527      */
 528     public boolean addAll(Collection<? extends E> c) {


 569     /**
 570      * Removes from this list all of the elements whose index is between
 571      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 572      * Shifts any succeeding elements to the left (reduces their index).
 573      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 574      * (If {@code toIndex==fromIndex}, this operation has no effect.)
 575      *
 576      * @throws IndexOutOfBoundsException if {@code fromIndex} or
 577      *         {@code toIndex} is out of range
 578      *         ({@code fromIndex < 0 ||
 579      *          fromIndex >= size() ||
 580      *          toIndex > size() ||
 581      *          toIndex < fromIndex})
 582      */
 583     protected void removeRange(int fromIndex, int toIndex) {
 584         modCount++;
 585         int numMoved = size - toIndex;
 586         System.arraycopy(elementData, toIndex, elementData, fromIndex,
 587                          numMoved);
 588 
 589         // Let gc do its work
 590         int newSize = size - (toIndex-fromIndex);
 591         while (size != newSize)
 592             elementData[--size] = null;


 593     }
 594 
 595     /**
 596      * Checks if the given index is in range.  If not, throws an appropriate
 597      * runtime exception.  This method does *not* check if the index is
 598      * negative: It is always used immediately prior to an array access,
 599      * which throws an ArrayIndexOutOfBoundsException if index is negative.
 600      */
 601     private void rangeCheck(int index) {
 602         if (index >= size)
 603             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 604     }
 605 
 606     /**
 607      * A version of rangeCheck used by add and addAll.
 608      */
 609     private void rangeCheckForAdd(int index) {
 610         if (index > size || index < 0)
 611             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 612     }


 660     }
 661 
 662     private boolean batchRemove(Collection<?> c, boolean complement) {
 663         final Object[] elementData = this.elementData;
 664         int r = 0, w = 0;
 665         boolean modified = false;
 666         try {
 667             for (; r < size; r++)
 668                 if (c.contains(elementData[r]) == complement)
 669                     elementData[w++] = elementData[r];
 670         } finally {
 671             // Preserve behavioral compatibility with AbstractCollection,
 672             // even if c.contains() throws.
 673             if (r != size) {
 674                 System.arraycopy(elementData, r,
 675                                  elementData, w,
 676                                  size - r);
 677                 w += size - r;
 678             }
 679             if (w != size) {

 680                 for (int i = w; i < size; i++)
 681                     elementData[i] = null;
 682                 modCount += size - w;
 683                 size = w;
 684                 modified = true;
 685             }
 686         }
 687         return modified;
 688     }
 689 
 690     /**
 691      * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 692      * is, serialize it).
 693      *
 694      * @serialData The length of the array backing the <tt>ArrayList</tt>
 695      *             instance is emitted (int), followed by all of its elements
 696      *             (each an <tt>Object</tt>) in the proper order.
 697      */
 698     private void writeObject(java.io.ObjectOutputStream s)
 699         throws java.io.IOException{
 700         // Write out element count, and any hidden stuff
 701         int expectedModCount = modCount;
 702         s.defaultWriteObject();
 703 
 704         // Write out array length
 705         s.writeInt(elementData.length);
 706 
 707         // Write out all elements in the proper order.
 708         for (int i=0; i<size; i++)
 709             s.writeObject(elementData[i]);

 710 
 711         if (modCount != expectedModCount) {
 712             throw new ConcurrentModificationException();
 713         }
 714 
 715     }
 716 
 717     /**
 718      * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 719      * deserialize it).
 720      */
 721     private void readObject(java.io.ObjectInputStream s)
 722         throws java.io.IOException, ClassNotFoundException {


 723         // Read in size, and any hidden stuff
 724         s.defaultReadObject();
 725 
 726         // Read in array length and allocate array
 727         int arrayLength = s.readInt();
 728         Object[] a = elementData = new Object[arrayLength];



 729 

 730         // Read in all elements in the proper order.
 731         for (int i=0; i<size; i++)
 732             a[i] = s.readObject();


 733     }
 734 
 735     /**
 736      * Returns a list iterator over the elements in this list (in proper
 737      * sequence), starting at the specified position in the list.
 738      * The specified index indicates the first element that would be
 739      * returned by an initial call to {@link ListIterator#next next}.
 740      * An initial call to {@link ListIterator#previous previous} would
 741      * return the element with the specified index minus one.
 742      *
 743      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 744      *
 745      * @throws IndexOutOfBoundsException {@inheritDoc}
 746      */
 747     public ListIterator<E> listIterator(int index) {
 748         if (index < 0 || index > size)
 749             throw new IndexOutOfBoundsException("Index: "+index);
 750         return new ListItr(index);
 751     }
 752 


   1 /*
   2  * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  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


  88  *
  89  * <p>This class is a member of the
  90  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  91  * Java Collections Framework</a>.
  92  *
  93  * @author  Josh Bloch
  94  * @author  Neal Gafter
  95  * @see     Collection
  96  * @see     List
  97  * @see     LinkedList
  98  * @see     Vector
  99  * @since   1.2
 100  */
 101 
 102 public class ArrayList<E> extends AbstractList<E>
 103         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 104 {
 105     private static final long serialVersionUID = 8683452581122892189L;
 106 
 107     /**
 108      * Default initial capacity.
 109      */
 110     private static final int DEFAULT_CAPACITY= 10;
 111 
 112     /**
 113      * Shared empty array instance used for empty instances.
 114      */
 115     private static final Object[] EMPTY_ELEMENTDATA = {};
 116 
 117     /**
 118      * The array buffer into which the elements of the ArrayList are stored.
 119      * The capacity of the ArrayList is the length of this array buffer. Any
 120      * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 121      * DEFAULT_CAPACITY when the first element is added.
 122      */
 123     private transient Object[] elementData;
 124 
 125     /**
 126      * The size of the ArrayList (the number of elements it contains).
 127      *
 128      * @serial
 129      */
 130     private int size;
 131 
 132     /**
 133      * Constructs an empty list with the specified initial capacity.
 134      *
 135      * @param  initialCapacity  the initial capacity of the list
 136      * @throws IllegalArgumentException if the specified initial capacity
 137      *         is negative
 138      */
 139     public ArrayList(int initialCapacity) {
 140         super();
 141         if (initialCapacity < 0)
 142             throw new IllegalArgumentException("Illegal Capacity: "+
 143                                                initialCapacity);
 144         this.elementData = new Object[initialCapacity];
 145     }
 146 
 147     /**
 148      * Constructs an empty list with an initial capacity of ten.
 149      */
 150     public ArrayList() {
 151         super();
 152         this.elementData = EMPTY_ELEMENTDATA;
 153     }
 154 
 155     /**
 156      * Constructs a list containing the elements of the specified
 157      * collection, in the order they are returned by the collection's
 158      * iterator.
 159      *
 160      * @param c the collection whose elements are to be placed into this list
 161      * @throws NullPointerException if the specified collection is null
 162      */
 163     public ArrayList(Collection<? extends E> c) {
 164         elementData = c.toArray();
 165         size = elementData.length;
 166         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 167         if (elementData.getClass() != Object[].class)
 168             elementData = Arrays.copyOf(elementData, size, Object[].class);
 169     }
 170 
 171     /**
 172      * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 173      * list's current size.  An application can use this operation to minimize
 174      * the storage of an <tt>ArrayList</tt> instance.
 175      */
 176     public void trimToSize() {
 177         modCount++;
 178         if (size < elementData.length) {

 179             elementData = Arrays.copyOf(elementData, size);
 180         }
 181     }
 182 
 183     /**
 184      * Increases the capacity of this <tt>ArrayList</tt> instance, if
 185      * necessary, to ensure that it can hold at least the number of elements
 186      * specified by the minimum capacity argument.
 187      *
 188      * @param   minCapacity   the desired minimum capacity
 189      */
 190     public void ensureCapacity(int minCapacity) {
 191         int minExpand = (elementData != EMPTY_ELEMENTDATA)
 192             // any size if real element table
 193             ? 0
 194             // larger than default for empty table. It's already supposed to be
 195             // at default size.
 196             : DEFAULT_CAPACITY;
 197 
 198         if (minCapacity > minExpand) {
 199             ensureExplicitCapacity(minCapacity);
 200         }
 201     }
 202 
 203     private void ensureCapacityInternal(int minCapacity) {
 204         if (elementData == EMPTY_ELEMENTDATA) {
 205             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 206         }
 207 
 208         ensureExplicitCapacity(minCapacity);
 209     }
 210 
 211     private void ensureExplicitCapacity(int minCapacity) {
 212         modCount++;
 213 
 214         // overflow-conscious code
 215         if (minCapacity - elementData.length > 0)
 216             grow(minCapacity);
 217     }
 218 
 219     /**
 220      * The maximum size of array to allocate.
 221      * Some VMs reserve some header words in an array.
 222      * Attempts to allocate larger arrays may result in
 223      * OutOfMemoryError: Requested array size exceeds VM limit
 224      */
 225     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 226 
 227     /**
 228      * Increases the capacity to ensure that it can hold at least the
 229      * number of elements specified by the minimum capacity argument.
 230      *
 231      * @param minCapacity the desired minimum capacity
 232      */
 233     private void grow(int minCapacity) {


 462 
 463     /**
 464      * Removes the element at the specified position in this list.
 465      * Shifts any subsequent elements to the left (subtracts one from their
 466      * indices).
 467      *
 468      * @param index the index of the element to be removed
 469      * @return the element that was removed from the list
 470      * @throws IndexOutOfBoundsException {@inheritDoc}
 471      */
 472     public E remove(int index) {
 473         rangeCheck(index);
 474 
 475         modCount++;
 476         E oldValue = elementData(index);
 477 
 478         int numMoved = size - index - 1;
 479         if (numMoved > 0)
 480             System.arraycopy(elementData, index+1, elementData, index,
 481                              numMoved);
 482         elementData[--size] = null; // clear to let GC do its work
 483 
 484         return oldValue;
 485     }
 486 
 487     /**
 488      * Removes the first occurrence of the specified element from this list,
 489      * if it is present.  If the list does not contain the element, it is
 490      * unchanged.  More formally, removes the element with the lowest index
 491      * <tt>i</tt> such that
 492      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 493      * (if such an element exists).  Returns <tt>true</tt> if this list
 494      * contained the specified element (or equivalently, if this list
 495      * changed as a result of the call).
 496      *
 497      * @param o element to be removed from this list, if present
 498      * @return <tt>true</tt> if this list contained the specified element
 499      */
 500     public boolean remove(Object o) {
 501         if (o == null) {
 502             for (int index = 0; index < size; index++)


 507         } else {
 508             for (int index = 0; index < size; index++)
 509                 if (o.equals(elementData[index])) {
 510                     fastRemove(index);
 511                     return true;
 512                 }
 513         }
 514         return false;
 515     }
 516 
 517     /*
 518      * Private remove method that skips bounds checking and does not
 519      * return the value removed.
 520      */
 521     private void fastRemove(int index) {
 522         modCount++;
 523         int numMoved = size - index - 1;
 524         if (numMoved > 0)
 525             System.arraycopy(elementData, index+1, elementData, index,
 526                              numMoved);
 527         elementData[--size] = null; // clear to let GC do its work
 528     }
 529 
 530     /**
 531      * Removes all of the elements from this list.  The list will
 532      * be empty after this call returns.
 533      */
 534     public void clear() {
 535         modCount++;
 536 
 537         // clear to let GC do its work
 538         for (int i = 0; i < size; i++)
 539             elementData[i] = null;
 540 
 541         size = 0;
 542     }
 543 
 544     /**
 545      * Appends all of the elements in the specified collection to the end of
 546      * this list, in the order that they are returned by the
 547      * specified collection's Iterator.  The behavior of this operation is
 548      * undefined if the specified collection is modified while the operation
 549      * is in progress.  (This implies that the behavior of this call is
 550      * undefined if the specified collection is this list, and this
 551      * list is nonempty.)
 552      *
 553      * @param c collection containing elements to be added to this list
 554      * @return <tt>true</tt> if this list changed as a result of the call
 555      * @throws NullPointerException if the specified collection is null
 556      */
 557     public boolean addAll(Collection<? extends E> c) {


 598     /**
 599      * Removes from this list all of the elements whose index is between
 600      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 601      * Shifts any succeeding elements to the left (reduces their index).
 602      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 603      * (If {@code toIndex==fromIndex}, this operation has no effect.)
 604      *
 605      * @throws IndexOutOfBoundsException if {@code fromIndex} or
 606      *         {@code toIndex} is out of range
 607      *         ({@code fromIndex < 0 ||
 608      *          fromIndex >= size() ||
 609      *          toIndex > size() ||
 610      *          toIndex < fromIndex})
 611      */
 612     protected void removeRange(int fromIndex, int toIndex) {
 613         modCount++;
 614         int numMoved = size - toIndex;
 615         System.arraycopy(elementData, toIndex, elementData, fromIndex,
 616                          numMoved);
 617 
 618         // clear to let GC do its work
 619         int newSize = size - (toIndex-fromIndex);
 620         for (int i = newSize; i < size; i++) {
 621             elementData[i] = null;
 622         }
 623         size = newSize;
 624     }
 625 
 626     /**
 627      * Checks if the given index is in range.  If not, throws an appropriate
 628      * runtime exception.  This method does *not* check if the index is
 629      * negative: It is always used immediately prior to an array access,
 630      * which throws an ArrayIndexOutOfBoundsException if index is negative.
 631      */
 632     private void rangeCheck(int index) {
 633         if (index >= size)
 634             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 635     }
 636 
 637     /**
 638      * A version of rangeCheck used by add and addAll.
 639      */
 640     private void rangeCheckForAdd(int index) {
 641         if (index > size || index < 0)
 642             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 643     }


 691     }
 692 
 693     private boolean batchRemove(Collection<?> c, boolean complement) {
 694         final Object[] elementData = this.elementData;
 695         int r = 0, w = 0;
 696         boolean modified = false;
 697         try {
 698             for (; r < size; r++)
 699                 if (c.contains(elementData[r]) == complement)
 700                     elementData[w++] = elementData[r];
 701         } finally {
 702             // Preserve behavioral compatibility with AbstractCollection,
 703             // even if c.contains() throws.
 704             if (r != size) {
 705                 System.arraycopy(elementData, r,
 706                                  elementData, w,
 707                                  size - r);
 708                 w += size - r;
 709             }
 710             if (w != size) {
 711                 // clear to let GC do its work
 712                 for (int i = w; i < size; i++)
 713                     elementData[i] = null;
 714                 modCount += size - w;
 715                 size = w;
 716                 modified = true;
 717             }
 718         }
 719         return modified;
 720     }
 721 
 722     /**
 723      * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 724      * is, serialize it).
 725      *
 726      * @serialData The length of the array backing the <tt>ArrayList</tt>
 727      *             instance is emitted (int), followed by all of its elements
 728      *             (each an <tt>Object</tt>) in the proper order.
 729      */
 730     private void writeObject(java.io.ObjectOutputStream s)
 731         throws java.io.IOException{
 732         // Write out element count, and any hidden stuff
 733         int expectedModCount = modCount;
 734         s.defaultWriteObject();
 735 
 736         // Write out size as capacity for behavioural compatibility with clone()
 737         s.writeInt(size);
 738 
 739         // Write out all elements in the proper order.
 740         for (int i=0; i<size; i++) {
 741             s.writeObject(elementData[i]);
 742         }
 743 
 744         if (modCount != expectedModCount) {
 745             throw new ConcurrentModificationException();
 746         }

 747     }
 748 
 749     /**
 750      * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 751      * deserialize it).
 752      */
 753     private void readObject(java.io.ObjectInputStream s)
 754         throws java.io.IOException, ClassNotFoundException {
 755          elementData = EMPTY_ELEMENTDATA;
 756 
 757         // Read in size, and any hidden stuff
 758         s.defaultReadObject();
 759 
 760         // Read in capacity
 761         s.readInt(); // ignored
 762 
 763         if (size > 0) {
 764             // be like clone(), allocate array based upon size not capacity
 765             ensureCapacityInternal(size);
 766 
 767             Object[] a = elementData;
 768             // Read in all elements in the proper order.
 769             for (int i=0; i<size; i++) {
 770                 a[i] = s.readObject();
 771             }
 772         }
 773     }
 774 
 775     /**
 776      * Returns a list iterator over the elements in this list (in proper
 777      * sequence), starting at the specified position in the list.
 778      * The specified index indicates the first element that would be
 779      * returned by an initial call to {@link ListIterator#next next}.
 780      * An initial call to {@link ListIterator#previous previous} would
 781      * return the element with the specified index minus one.
 782      *
 783      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 784      *
 785      * @throws IndexOutOfBoundsException {@inheritDoc}
 786      */
 787     public ListIterator<E> listIterator(int index) {
 788         if (index < 0 || index > size)
 789             throw new IndexOutOfBoundsException("Index: "+index);
 790         return new ListItr(index);
 791     }
 792