ArrayList源码解读

喜欢ヅ旅行 2022-10-02 04:48 215阅读 0赞

### ArrayList源码解读 ###

*   *  读前须知
     *  源码

## 读前须知 ##

这两个方法在源码中频繁使用，所以一定要先深刻理解

/**数组扩容，原来数组的值不会改变。当original.length>newLength，数组多出来的部分会被丢弃，当*original.length<=newLength，数组其它没数据的会设置值为null. *original：数组对象 *newLength：扩容后的长度 **/
 Arrays.copyOf(T[] original, int newLength);
 
 /** *数组拷贝： *src:源数组，srcPos：源数组目标位置 *dest:目标数组，destPos:目标数组位置 *length:拷贝源数组到目标数组的长度 **/
 System.arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

## 源码 ##

下面是有注释的源码：

package test.list;
 
 import java.util.*;
 
 
 public class ExtArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 { 
 private static final long serialVersionUID = 8683452581122892189L;
 
 /** * 缺省的list容量。 */
 private static final int DEFAULT_CAPACITY = 10;
 
 /** * 当构造时传入的容量为零时，elementData=EMPTY_ELEMENTDATA={}。 */
 private static final Object[] EMPTY_ELEMENTDATA = { };
 
 /** * 当创建一个长度可变的数组时，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA。 */
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
 
 /** * 存储ArrayList元素的数组缓冲区. * ArrayList的容量是这个数组缓冲区的长度. 当添加第一个元素时，空的ArrayList都将扩展为默认容量。 */
 transient Object[] elementData; // non-private to simplify nested class access
 
 
 private int size;
 
 /** * 初始化容量的构造方法 */
 public ExtArrayList(int initialCapacity) { 
 if (initialCapacity > 0) { 
 this.elementData = new Object[initialCapacity];
 } else if (initialCapacity == 0) { 
 this.elementData = EMPTY_ELEMENTDATA;
 } else { 
 throw new IllegalArgumentException("Illegal Capacity: "+
 initialCapacity);
 }
 }
 
 /** * 空参构造函数默认容量为10,没有进行初始化. */
 public ExtArrayList() { 
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }
 
 /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */
 public ExtArrayList(Collection<? extends E> c) { 
 elementData = c.toArray();
 if ((size = elementData.length) != 0) { 
 // c.toArray might (incorrectly) not return Object[] (see 6260652)
 if (elementData.getClass() != Object[].class)
 elementData = Arrays.copyOf(elementData, size, Object[].class);
 } else { 
 // replace with empty array.
 this.elementData = EMPTY_ELEMENTDATA;
 }
 }
 /** * Trims the capacity of this <tt>ArrayList</tt> instance to be the * list's current size. An application can use this operation to minimize * the storage of an <tt>ArrayList</tt> instance. */
 public void trimToSize() { 
 modCount++;
 if (size < elementData.length) { 
 elementData = (size == 0)
 ? EMPTY_ELEMENTDATA
 : Arrays.copyOf(elementData, size);
 }
 }
 
 /** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */
 public void ensureCapacity(int minCapacity) { 
 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
 // any size if not default element table
 ? 0
 // larger than default for default empty table. It's already
 // supposed to be at default size.
 : DEFAULT_CAPACITY;
 
 if (minCapacity > minExpand) { 
 ensureExplicitCapacity(minCapacity);
 }
 }
 
 /** * 选出最小容量 * @param elementData * @param minCapacity * @return */
 private static int calculateCapacity(Object[] elementData, int minCapacity) { 
 	//如果elementData为空
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
 	//返回数组缺省值和传进来最小容量的最大值
 return Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 return minCapacity;
 }
 
 /** * 判断elementData数组是否需要扩容 * @param minCapacity */
 private void ensureCapacityInternal(int minCapacity) { 
 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 }
 
 private void ensureExplicitCapacity(int minCapacity) { 
 modCount++;
 //如果需要的最小容量大于elementData数组的最大容量则进行扩容
 if (minCapacity - elementData.length > 0)
 grow(minCapacity);
 }
 
 /** * 要分配的数组的最大大小。 * 一些vm在数组中保留一些头信息。 * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
 /** * 进行数组1.5倍扩容 * 注意问题当elementData数组的长度为1是时 */
 private void grow(int minCapacity) { 
 int oldCapacity = elementData.length;
 //数组扩容，注意问题当elementData数组的长度为1是时，该算法结束后newCapacity的结果依然为1，起不了扩容效果
 int newCapacity = oldCapacity + (oldCapacity >> 1);
 //此判断解决上面问题
 if (newCapacity - minCapacity < 0)
 newCapacity = minCapacity;
 if (newCapacity - MAX_ARRAY_SIZE > 0)
 newCapacity = hugeCapacity(minCapacity);
 //数组扩容
 elementData = Arrays.copyOf(elementData, newCapacity);
 }
 
 private static int hugeCapacity(int minCapacity) { 
 if (minCapacity < 0) // overflow
 throw new OutOfMemoryError();
 return (minCapacity > MAX_ARRAY_SIZE) ?
 Integer.MAX_VALUE :
 MAX_ARRAY_SIZE;
 }
 
 /** * Returns the number of elements in this list. * * @return the number of elements in this list */
 public int size() { 
 return size;
 }
 
 /** * Returns <tt>true</tt> if this list contains no elements. * * @return <tt>true</tt> if this list contains no elements */
 public boolean isEmpty() { 
 return size == 0;
 }
 
 /** *是否包含某个元素，查到下标>=0就返回true，否则返回false. */
 public boolean contains(Object o) { 
 return indexOf(o) >= 0;
 }
 
 /** *查找元素，查到就返回所在下标，找不到就返回-1 */
 public int indexOf(Object o) { 
 if (o == null) { 
 for (int i = 0; i < size; i++)
 if (elementData[i]==null)
 return i;
 } else { 
 for (int i = 0; i < size; i++)
 if (o.equals(elementData[i]))
 return i;
 }
 return -1;
 }
 
 /** *查找最后出现元素下标，倒叙查找，差不到返回-1. */
 public int lastIndexOf(Object o) { 
 if (o == null) { 
 for (int i = size-1; i >= 0; i--)
 if (elementData[i]==null)
 return i;
 } else { 
 for (int i = size-1; i >= 0; i--)
 if (o.equals(elementData[i]))
 return i;
 }
 return -1;
 }
 
 /** * 返回此ArrayList实例的浅副本。(对副本的操作不会影响到原数据) * * @return a clone of this <tt>ArrayList</tt> instance */
 public Object clone() { 
 try { 
 ExtArrayList<?> v = (ExtArrayList<?>) super.clone();
 v.elementData = Arrays.copyOf(elementData, size);
 v.modCount = 0;
 return v;
 } catch (CloneNotSupportedException e) { 
 // this shouldn't happen, since we are Cloneable
 throw new InternalError(e);
 }
 }
 
 /** * Returns an array containing all of the elements in this list * in proper sequence (from first to last element). * * The returned array will be "safe" in that no references to it are * maintained by this list. (In other words, this method must allocate * a new array). The caller is thus free to modify the returned array. * * This method acts as bridge between array-based and collection-based * APIs. * * @return an array containing all of the elements in this list in * proper sequence */
 public Object[] toArray() { 
 return Arrays.copyOf(elementData, size);
 }
 
 /** * Returns an array containing all of the elements in this list in proper * sequence (from first to last element); the runtime type of the returned * array is that of the specified array. If the list fits in the * specified array, it is returned therein. Otherwise, a new array is * allocated with the runtime type of the specified array and the size of * this list. * * If the list fits in the specified array with room to spare * (i.e., the array has more elements than the list), the element in * the array immediately following the end of the collection is set to * <tt>null</tt>. (This is useful in determining the length of the * list only if the caller knows that the list does not contain * any null elements.) * * @param a the array into which the elements of the list are to * be stored, if it is big enough; otherwise, a new array of the * same runtime type is allocated for this purpose. * @return an array containing the elements of the list * @throws ArrayStoreException if the runtime type of the specified array * is not a supertype of the runtime type of every element in * this list * @throws NullPointerException if the specified array is null */
 @SuppressWarnings("unchecked")
 public <T> T[] toArray(T[] a) { 
 if (a.length < size)
 // Make a new array of a's runtime type, but my contents:
 return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 System.arraycopy(elementData, 0, a, 0, size);
 if (a.length > size)
 a[size] = null;
 return a;
 }
 
 // Positional Access Operations
 
 @SuppressWarnings("unchecked")
 E elementData(int index) { 
 return (E) elementData[index];
 }
 
 public E get(int index) { 
 rangeCheck(index);
 
 return elementData(index);
 }
 
 
 public E set(int index, E element) { 
 rangeCheck(index);
 
 E oldValue = elementData(index);
 elementData[index] = element;
 return oldValue;
 }
 
 /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
 public boolean add(E e) { 
 ensureCapacityInternal(size + 1); // Increments modCount!!
 elementData[size++] = e;
 return true;
 }
 
 /** * 在指定位置插入元素 */
 public void add(int index, E element) { 
 rangeCheckForAdd(index);
 ensureCapacityInternal(size + 1);
 //数组拷贝
 System.arraycopy(elementData, index, elementData, index + 1,
 size - index);
 elementData[index] = element;
 size++;
 }
 
 
 public E remove(int index) { 
 rangeCheck(index);
 
 modCount++;
 E oldValue = elementData(index);
 //numMoved表示为index是第几个元素后的长度
 //例：当size=10,index=4;则numMoved=5;表示后面还有5个元素不动，需要前移
 int numMoved = size - index - 1;
 if (numMoved > 0)
 System.arraycopy(elementData, index+1, elementData, index,
 numMoved);
 elementData[--size] = null; // clear to let GC do its work
 
 return oldValue;
 }
 
 
 public boolean remove(Object o) { 
 if (o == null) { 
 for (int index = 0; index < size; index++)
 if (elementData[index] == null) { 
 fastRemove(index);
 return true;
 }
 } else { 
 for (int index = 0; index < size; index++)
 if (o.equals(elementData[index])) { 
 fastRemove(index);
 return true;
 }
 }
 return false;
 }
 /** * 移除首个在数组中出现的元素 * @param index */
 void fastRemove(int index) { 
 modCount++;
 int numMoved = size - index - 1;
 if (numMoved > 0)
 System.arraycopy(elementData, index+1, elementData, index,
 numMoved);
 elementData[--size] = null; // clear to let GC do its work
 }
 
 /** * 清空数组，size置为0，但数组长度不变 */
 public void clear() { 
 modCount++;
 
 // clear to let GC do its work
 for (int i = 0; i < size; i++)
 elementData[i] = null;
 
 size = 0;
 }
 
 /** * 添加一个集合的所有元素到数组 * * @param 添加的集合 */
 public boolean addAll(Collection<? extends E> c) { 
 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacityInternal(size + numNew); // Increments modCount
 System.arraycopy(a, 0, elementData, size, numNew);
 size += numNew;
 return numNew != 0;
 }
 
 /** * 添加一个集合到指定位置 * * @param index index at which to insert the first element from the * specified collection * @param c collection containing elements to be added to this list */
 public boolean addAll(int index, Collection<? extends E> c) { 
 rangeCheckForAdd(index);
 
 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacityInternal(size + numNew); // Increments modCount
 
 int numMoved = size - index;
 if (numMoved > 0)
 System.arraycopy(elementData, index, elementData, index + numNew,
 numMoved);
 
 System.arraycopy(a, 0, elementData, index, numNew);
 size += numNew;
 return numNew != 0;
 }
 
 /** *移除一个数组中指定范围的所有元素 */
 protected void removeRange(int fromIndex, int toIndex) { 
 modCount++;
 int numMoved = size - toIndex;
 System.arraycopy(elementData, toIndex, elementData, fromIndex,
 numMoved);
 
 // clear to let GC do its work
 int newSize = size - (toIndex-fromIndex);
 for (int i = newSize; i < size; i++) { 
 elementData[i] = null;
 }
 size = newSize;
 }
 
 /** * 检查下标 */
 private void rangeCheck(int index) { 
 if (index >= size)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 }
 
 /** * A version of rangeCheck used by add and addAll. */
 private void rangeCheckForAdd(int index) { 
 if (index > size || index < 0)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 }
 
 
 
 /** * 到此基本原理已经结束，有兴趣的可以继续向下阅读 */
 
 
 
 /** * Constructs an IndexOutOfBoundsException detail message. * Of the many possible refactorings of the error handling code, * this "outlining" performs best with both server and client VMs. */
 private String outOfBoundsMsg(int index) { 
 return "Index: "+index+", Size: "+size;
 }
 
 /** * Removes from this list all of its elements that are contained in the * specified collection. * * @param c collection containing elements to be removed from this list * @return {@code true} if this list changed as a result of the call * @throws ClassCastException if the class of an element of this list * is incompatible with the specified collection * (<a href="Collection.html#optional-restrictions">optional</a>) * @throws NullPointerException if this list contains a null element and the * specified collection does not permit null elements * (<a href="Collection.html#optional-restrictions">optional</a>), * or if the specified collection is null * @see Collection#contains(Object) */
 public boolean removeAll(Collection<?> c) { 
 Objects.requireNonNull(c);
 return batchRemove(c, false);
 }
 
 /** * Retains only the elements in this list that are contained in the * specified collection. In other words, removes from this list all * of its elements that are not contained in the specified collection. * * @param c collection containing elements to be retained in this list * @return {@code true} if this list changed as a result of the call * @throws ClassCastException if the class of an element of this list * is incompatible with the specified collection * (<a href="Collection.html#optional-restrictions">optional</a>) * @throws NullPointerException if this list contains a null element and the * specified collection does not permit null elements * (<a href="Collection.html#optional-restrictions">optional</a>), * or if the specified collection is null * @see Collection#contains(Object) */
 public boolean retainAll(Collection<?> c) { 
 Objects.requireNonNull(c);
 return batchRemove(c, true);
 }
 
 private boolean batchRemove(Collection<?> c, boolean complement) { 
 final Object[] elementData = this.elementData;
 int r = 0, w = 0;
 boolean modified = false;
 try { 
 for (; r < size; r++)
 if (c.contains(elementData[r]) == complement)
 elementData[w++] = elementData[r];
 } finally { 
 // Preserve behavioral compatibility with AbstractCollection,
 // even if c.contains() throws.
 if (r != size) { 
 System.arraycopy(elementData, r,
 elementData, w,
 size - r);
 w += size - r;
 }
 if (w != size) { 
 // clear to let GC do its work
 for (int i = w; i < size; i++)
 elementData[i] = null;
 modCount += size - w;
 size = w;
 modified = true;
 }
 }
 return modified;
 }
 
 /** * Save the state of the <tt>ArrayList</tt> instance to a stream (that * is, serialize it). * * @serialData The length of the array backing the <tt>ArrayList</tt> * instance is emitted (int), followed by all of its elements * (each an <tt>Object</tt>) in the proper order. */
 private void writeObject(java.io.ObjectOutputStream s)
 throws java.io.IOException{ 
 // Write out element count, and any hidden stuff
 int expectedModCount = modCount;
 s.defaultWriteObject();
 
 // Write out size as capacity for behavioural compatibility with clone()
 s.writeInt(size);
 
 // Write out all elements in the proper order.
 for (int i=0; i<size; i++) { 
 s.writeObject(elementData[i]);
 }
 
 if (modCount != expectedModCount) { 
 throw new ConcurrentModificationException();
 }
 }
 
 /** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */
 private void readObject(java.io.ObjectInputStream s)
 throws java.io.IOException, ClassNotFoundException { 
 elementData = EMPTY_ELEMENTDATA;
 
 // Read in size, and any hidden stuff
 s.defaultReadObject();
 
 // Read in capacity
 s.readInt(); // ignored
 
 if (size > 0) { 
 // be like clone(), allocate array based upon size not capacity
 int capacity = calculateCapacity(elementData, size);
 //SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
 ensureCapacityInternal(size);
 
 Object[] a = elementData;
 // Read in all elements in the proper order.
 for (int i=0; i<size; i++) { 
 a[i] = s.readObject();
 }
 }
 }
 
 /** * Returns a list iterator over the elements in this list (in proper * sequence), starting at the specified position in the list. * The specified index indicates the first element that would be * returned by an initial call to {@link ListIterator#next next}. * An initial call to {@link ListIterator#previous previous} would * return the element with the specified index minus one. * * The returned list iterator is <a href="#fail-fast">fail-fast</a>. * * @throws IndexOutOfBoundsException {@inheritDoc} */
 public ListIterator<E> listIterator(int index) { 
 if (index < 0 || index > size)
 throw new IndexOutOfBoundsException("Index: "+index);
 return new ListItr(index);
 }
 
 /** * Returns a list iterator over the elements in this list (in proper * sequence). * * The returned list iterator is <a href="#fail-fast">fail-fast</a>. * * @see #listIterator(int) */
 public ListIterator<E> listIterator() { 
 return new ListItr(0);
 }
 
 /** * Returns an iterator over the elements in this list in proper sequence. * * The returned iterator is <a href="#fail-fast">fail-fast</a>. * * @return an iterator over the elements in this list in proper sequence */
 public Iterator<E> iterator() { 
 return new Itr();
 }
 
 /** * An optimized version of AbstractList.Itr */
 private class Itr implements Iterator<E> { 
 int cursor; // index of next element to return
 int lastRet = -1; // index of last element returned; -1 if no such
 int expectedModCount = modCount;
 
 Itr() { }
 
 public boolean hasNext() { 
 return cursor != size;
 }
 
 @SuppressWarnings("unchecked")
 public E next() { 
 checkForComodification();
 int i = cursor;
 if (i >= size)
 throw new NoSuchElementException();
 Object[] elementData = ExtArrayList.this.elementData;
 if (i >= elementData.length)
 throw new ConcurrentModificationException();
 cursor = i + 1;
 return (E) elementData[lastRet = i];
 }
 
 public void remove() { 
 if (lastRet < 0)
 throw new IllegalStateException();
 checkForComodification();
 
 try { 
 ExtArrayList.this.remove(lastRet);
 cursor = lastRet;
 lastRet = -1;
 expectedModCount = modCount;
 } catch (IndexOutOfBoundsException ex) { 
 throw new ConcurrentModificationException();
 }
 }
 
 @Override
 @SuppressWarnings("unchecked")
 public void forEachRemaining(Consumer<? super E> consumer) { 
 Objects.requireNonNull(consumer);
 final int size = ExtArrayList.this.size;
 int i = cursor;
 if (i >= size) { 
 return;
 }
 final Object[] elementData = ExtArrayList.this.elementData;
 if (i >= elementData.length) { 
 throw new ConcurrentModificationException();
 }
 while (i != size && modCount == expectedModCount) { 
 consumer.accept((E) elementData[i++]);
 }
 // update once at end of iteration to reduce heap write traffic
 cursor = i;
 lastRet = i - 1;
 checkForComodification();
 }
 
 final void checkForComodification() { 
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }
 }
 
 /** * An optimized version of AbstractList.ListItr */
 private class ListItr extends Itr implements ListIterator<E> { 
 ListItr(int index) { 
 super();
 cursor = index;
 }
 
 public boolean hasPrevious() { 
 return cursor != 0;
 }
 
 public int nextIndex() { 
 return cursor;
 }
 
 public int previousIndex() { 
 return cursor - 1;
 }
 
 @SuppressWarnings("unchecked")
 public E previous() { 
 checkForComodification();
 int i = cursor - 1;
 if (i < 0)
 throw new NoSuchElementException();
 Object[] elementData = ExtArrayList.this.elementData;
 if (i >= elementData.length)
 throw new ConcurrentModificationException();
 cursor = i;
 return (E) elementData[lastRet = i];
 }
 
 public void set(E e) { 
 if (lastRet < 0)
 throw new IllegalStateException();
 checkForComodification();
 
 try { 
 ExtArrayList.this.set(lastRet, e);
 } catch (IndexOutOfBoundsException ex) { 
 throw new ConcurrentModificationException();
 }
 }
 
 public void add(E e) { 
 checkForComodification();
 
 try { 
 int i = cursor;
 ExtArrayList.this.add(i, e);
 cursor = i + 1;
 lastRet = -1;
 expectedModCount = modCount;
 } catch (IndexOutOfBoundsException ex) { 
 throw new ConcurrentModificationException();
 }
 }
 }
 
 /** * Returns a view of the portion of this list between the specified * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If * {@code fromIndex} and {@code toIndex} are equal, the returned list is * empty.) The returned list is backed by this list, so non-structural * changes in the returned list are reflected in this list, and vice-versa. * The returned list supports all of the optional list operations. * * This method eliminates the need for explicit range operations (of * the sort that commonly exist for arrays). Any operation that expects * a list can be used as a range operation by passing a subList view * instead of a whole list. For example, the following idiom * removes a range of elements from a list: * <pre> * list.subList(from, to).clear(); * </pre> * Similar idioms may be constructed for {@link #indexOf(Object)} and * {@link #lastIndexOf(Object)}, and all of the algorithms in the * {@link Collections} class can be applied to a subList. * * The semantics of the list returned by this method become undefined if * the backing list (i.e., this list) is structurally modified in * any way other than via the returned list. (Structural modifications are * those that change the size of this list, or otherwise perturb it in such * a fashion that iterations in progress may yield incorrect results.) * * @throws IndexOutOfBoundsException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */
 public List<E> subList(int fromIndex, int toIndex) { 
 subListRangeCheck(fromIndex, toIndex, size);
 return new SubList(this, 0, fromIndex, toIndex);
 }
 
 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 
 if (fromIndex < 0)
 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 if (toIndex > size)
 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 if (fromIndex > toIndex)
 throw new IllegalArgumentException("fromIndex(" + fromIndex +
 ") > toIndex(" + toIndex + ")");
 }
 
 private class SubList extends AbstractList<E> implements RandomAccess { 
 private final AbstractList<E> parent;
 private final int parentOffset;
 private final int offset;
 int size;
 
 SubList(AbstractList<E> parent,
 int offset, int fromIndex, int toIndex) { 
 this.parent = parent;
 this.parentOffset = fromIndex;
 this.offset = offset + fromIndex;
 this.size = toIndex - fromIndex;
 this.modCount = ExtArrayList.this.modCount;
 }
 
 public E set(int index, E e) { 
 rangeCheck(index);
 checkForComodification();
 E oldValue = ExtArrayList.this.elementData(offset + index);
 ExtArrayList.this.elementData[offset + index] = e;
 return oldValue;
 }
 
 public E get(int index) { 
 rangeCheck(index);
 checkForComodification();
 return ExtArrayList.this.elementData(offset + index);
 }
 
 public int size() { 
 checkForComodification();
 return this.size;
 }
 
 public void add(int index, E e) { 
 rangeCheckForAdd(index);
 checkForComodification();
 parent.add(parentOffset + index, e);
 // this.modCount = parent.modCount;
 this.size++;
 }
 
 public E remove(int index) { 
 rangeCheck(index);
 checkForComodification();
 E result = parent.remove(parentOffset + index);
 // this.modCount = parent.modCount;
 this.size--;
 return result;
 }
 
 protected void removeRange(int fromIndex, int toIndex) { 
 checkForComodification();
 // parent.removeRange(parentOffset + fromIndex,
 // parentOffset + toIndex);
 //this.modCount = parent.modCount;
 this.size -= toIndex - fromIndex;
 }
 
 public boolean addAll(Collection<? extends E> c) { 
 return addAll(this.size, c);
 }
 
 public boolean addAll(int index, Collection<? extends E> c) { 
 rangeCheckForAdd(index);
 int cSize = c.size();
 if (cSize==0)
 return false;
 
 checkForComodification();
 parent.addAll(parentOffset + index, c);
 // this.modCount = parent.modCount;
 this.size += cSize;
 return true;
 }
 
 public Iterator<E> iterator() { 
 return listIterator();
 }
 
 public ListIterator<E> listIterator(final int index) { 
 checkForComodification();
 rangeCheckForAdd(index);
 final int offset = this.offset;
 
 return new ListIterator<E>() { 
 int cursor = index;
 int lastRet = -1;
 int expectedModCount = ExtArrayList.this.modCount;
 
 public boolean hasNext() { 
 return cursor != SubList.this.size;
 }
 
 @SuppressWarnings("unchecked")
 public E next() { 
 checkForComodification();
 int i = cursor;
 if (i >= SubList.this.size)
 throw new NoSuchElementException();
 Object[] elementData = ExtArrayList.this.elementData;
 if (offset + i >= elementData.length)
 throw new ConcurrentModificationException();
 cursor = i + 1;
 return (E) elementData[offset + (lastRet = i)];
 }
 
 public boolean hasPrevious() { 
 return cursor != 0;
 }
 
 @SuppressWarnings("unchecked")
 public E previous() { 
 checkForComodification();
 int i = cursor - 1;
 if (i < 0)
 throw new NoSuchElementException();
 Object[] elementData = ExtArrayList.this.elementData;
 if (offset + i >= elementData.length)
 throw new ConcurrentModificationException();
 cursor = i;
 return (E) elementData[offset + (lastRet = i)];
 }
 
 @SuppressWarnings("unchecked")
 public void forEachRemaining(Consumer<? super E> consumer) { 
 Objects.requireNonNull(consumer);
 final int size = SubList.this.size;
 int i = cursor;
 if (i >= size) { 
 return;
 }
 final Object[] elementData = ExtArrayList.this.elementData;
 if (offset + i >= elementData.length) { 
 throw new ConcurrentModificationException();
 }
 while (i != size && modCount == expectedModCount) { 
 consumer.accept((E) elementData[offset + (i++)]);
 }
 // update once at end of iteration to reduce heap write traffic
 lastRet = cursor = i;
 checkForComodification();
 }
 
 public int nextIndex() { 
 return cursor;
 }
 
 public int previousIndex() { 
 return cursor - 1;
 }
 
 public void remove() { 
 if (lastRet < 0)
 throw new IllegalStateException();
 checkForComodification();
 
 try { 
 SubList.this.remove(lastRet);
 cursor = lastRet;
 lastRet = -1;
 expectedModCount = ExtArrayList.this.modCount;
 } catch (IndexOutOfBoundsException ex) { 
 throw new ConcurrentModificationException();
 }
 }
 
 public void set(E e) { 
 if (lastRet < 0)
 throw new IllegalStateException();
 checkForComodification();
 
 try { 
 ExtArrayList.this.set(offset + lastRet, e);
 } catch (IndexOutOfBoundsException ex) { 
 throw new ConcurrentModificationException();
 }
 }
 
 public void add(E e) { 
 checkForComodification();
 
 try { 
 int i = cursor;
 SubList.this.add(i, e);
 cursor = i + 1;
 lastRet = -1;
 expectedModCount = ExtArrayList.this.modCount;
 } catch (IndexOutOfBoundsException ex) { 
 throw new ConcurrentModificationException();
 }
 }
 
 final void checkForComodification() { 
 if (expectedModCount != ExtArrayList.this.modCount)
 throw new ConcurrentModificationException();
 }
 };
 }
 
 public List<E> subList(int fromIndex, int toIndex) { 
 subListRangeCheck(fromIndex, toIndex, size);
 return new SubList(this, offset, fromIndex, toIndex);
 }
 
 private void rangeCheck(int index) { 
 if (index < 0 || index >= this.size)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 }
 
 private void rangeCheckForAdd(int index) { 
 if (index < 0 || index > this.size)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 }
 
 private String outOfBoundsMsg(int index) { 
 return "Index: "+index+", Size: "+this.size;
 }
 
 private void checkForComodification() { 
 if (ExtArrayList.this.modCount != this.modCount)
 throw new ConcurrentModificationException();
 }
 
 public Spliterator<E> spliterator() { 
 checkForComodification();
 return new ArrayListSpliterator<E>(ExtArrayList.this, offset,
 offset + this.size, this.modCount);
 }
 }
 
 @Override
 public void forEach(Consumer<? super E> action) { 
 Objects.requireNonNull(action);
 final int expectedModCount = modCount;
 @SuppressWarnings("unchecked")
 final E[] elementData = (E[]) this.elementData;
 final int size = this.size;
 for (int i=0; modCount == expectedModCount && i < size; i++) { 
 action.accept(elementData[i]);
 }
 if (modCount != expectedModCount) { 
 throw new ConcurrentModificationException();
 }
 }
 
 /** * Creates a <a href="Spliterator.html#binding">late-binding</a> * and fail-fast {@link Spliterator} over the elements in this * list. * * The {@code Spliterator} reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}. * Overriding implementations should document the reporting of additional * characteristic values. * * @return a {@code Spliterator} over the elements in this list * @since 1.8 */
 @Override
 public Spliterator<E> spliterator() { 
 return new ArrayListSpliterator<>(this, 0, -1, 0);
 }
 
 /** Index-based split-by-two, lazily initialized Spliterator */
 static final class ArrayListSpliterator<E> implements Spliterator<E> { 
 
 /* * If ArrayLists were immutable, or structurally immutable (no * adds, removes, etc), we could implement their spliterators * with Arrays.spliterator. Instead we detect as much * interference during traversal as practical without * sacrificing much performance. We rely primarily on * modCounts. These are not guaranteed to detect concurrency * violations, and are sometimes overly conservative about * within-thread interference, but detect enough problems to * be worthwhile in practice. To carry this out, we (1) lazily * initialize fence and expectedModCount until the latest * point that we need to commit to the state we are checking * against; thus improving precision. (This doesn't apply to * SubLists, that create spliterators with current non-lazy * values). (2) We perform only a single * ConcurrentModificationException check at the end of forEach * (the most performance-sensitive method). When using forEach * (as opposed to iterators), we can normally only detect * interference after actions, not before. Further * CME-triggering checks apply to all other possible * violations of assumptions for example null or too-small * elementData array given its size(), that could only have * occurred due to interference. This allows the inner loop * of forEach to run without any further checks, and * simplifies lambda-resolution. While this does entail a * number of checks, note that in the common case of * list.stream().forEach(a), no checks or other computation * occur anywhere other than inside forEach itself. The other * less-often-used methods cannot take advantage of most of * these streamlinings. */
 
 private final ExtArrayList<E> list;
 private int index; // current index, modified on advance/split
 private int fence; // -1 until used; then one past last index
 private int expectedModCount; // initialized when fence set
 
 /** Create new spliterator covering the given range */
 ArrayListSpliterator(ExtArrayList<E> list, int origin, int fence,
 int expectedModCount) { 
 this.list = list; // OK if null unless traversed
 this.index = origin;
 this.fence = fence;
 this.expectedModCount = expectedModCount;
 }
 
 private int getFence() { // initialize fence to size on first use
 int hi; // (a specialized variant appears in method forEach)
 ExtArrayList<E> lst;
 if ((hi = fence) < 0) { 
 if ((lst = list) == null)
 hi = fence = 0;
 else { 
 expectedModCount = lst.modCount;
 hi = fence = lst.size;
 }
 }
 return hi;
 }
 
 public ArrayListSpliterator<E> trySplit() { 
 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
 return (lo >= mid) ? null : // divide range in half unless too small
 new ArrayListSpliterator<E>(list, lo, index = mid,
 expectedModCount);
 }
 
 public boolean tryAdvance(Consumer<? super E> action) { 
 if (action == null)
 throw new NullPointerException();
 int hi = getFence(), i = index;
 if (i < hi) { 
 index = i + 1;
 @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
 action.accept(e);
 if (list.modCount != expectedModCount)
 throw new ConcurrentModificationException();
 return true;
 }
 return false;
 }
 
 public void forEachRemaining(Consumer<? super E> action) { 
 int i, hi, mc; // hoist accesses and checks from loop
 ExtArrayList<E> lst; Object[] a;
 if (action == null)
 throw new NullPointerException();
 if ((lst = list) != null && (a = lst.elementData) != null) { 
 if ((hi = fence) < 0) { 
 mc = lst.modCount;
 hi = lst.size;
 }
 else
 mc = expectedModCount;
 if ((i = index) >= 0 && (index = hi) <= a.length) { 
 for (; i < hi; ++i) { 
 @SuppressWarnings("unchecked") E e = (E) a[i];
 action.accept(e);
 }
 if (lst.modCount == mc)
 return;
 }
 }
 throw new ConcurrentModificationException();
 }
 
 public long estimateSize() { 
 return (long) (getFence() - index);
 }
 
 public int characteristics() { 
 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
 }
 }
 
 @Override
 public boolean removeIf(Predicate<? super E> filter) { 
 Objects.requireNonNull(filter);
 // figure out which elements are to be removed
 // any exception thrown from the filter predicate at this stage
 // will leave the collection unmodified
 int removeCount = 0;
 final BitSet removeSet = new BitSet(size);
 final int expectedModCount = modCount;
 final int size = this.size;
 for (int i=0; modCount == expectedModCount && i < size; i++) { 
 @SuppressWarnings("unchecked")
 final E element = (E) elementData[i];
 if (filter.test(element)) { 
 removeSet.set(i);
 removeCount++;
 }
 }
 if (modCount != expectedModCount) { 
 throw new ConcurrentModificationException();
 }
 
 // shift surviving elements left over the spaces left by removed elements
 final boolean anyToRemove = removeCount > 0;
 if (anyToRemove) { 
 final int newSize = size - removeCount;
 for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { 
 i = removeSet.nextClearBit(i);
 elementData[j] = elementData[i];
 }
 for (int k=newSize; k < size; k++) { 
 elementData[k] = null; // Let gc do its work
 }
 this.size = newSize;
 if (modCount != expectedModCount) { 
 throw new ConcurrentModificationException();
 }
 modCount++;
 }
 
 return anyToRemove;
 }
 
 @Override
 @SuppressWarnings("unchecked")
 public void replaceAll(UnaryOperator<E> operator) { 
 Objects.requireNonNull(operator);
 final int expectedModCount = modCount;
 final int size = this.size;
 for (int i=0; modCount == expectedModCount && i < size; i++) { 
 elementData[i] = operator.apply((E) elementData[i]);
 }
 if (modCount != expectedModCount) { 
 throw new ConcurrentModificationException();
 }
 modCount++;
 }
 
 @Override
 @SuppressWarnings("unchecked")
 public void sort(Comparator<? super E> c) { 
 final int expectedModCount = modCount;
 Arrays.sort((E[]) elementData, 0, size, c);
 if (modCount != expectedModCount) { 
 throw new ConcurrentModificationException();
 }
 modCount++;
 }
 }

如有表述不当之处，还请原谅。