集合源码阅读：ArrayList

1.继承关系：

   public class ArrayList<E> extends AbstractList<E>
          implements List<E>, RandomAccess, Cloneable, java.io.Serializable
          
   ===================================================
   
    
2. 属性：

    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

    // 空数组，第一次存入元素时更新大小为 DEFAULT_CAPACITY
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 空数组，默认设定大小为 DEFAULT_CAPACITY
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 添加第一个元素时扩展到默认容量，transient：关闭序列化
    transient Object[] elementData;

    // 数组中元素个数
    private int size;
    
   ===================================================
   
    
3.方法：

   // 构造函数：initialCapacity 集合容量，该值为0时设定集合为 EMPTY_ELEMENTDATA，否则取其正值。
   public ArrayList(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);
        }
    }
  
   // 无参构造：默认设定大小为 DEFAULT_CAPACITY
   public ArrayList() {
         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }
   
   // 构造函数：拷贝已知集合，若参数为空集合则使用 EMPTY_ELEMENTDATA。
   public ArrayList(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;
           }
       }
     
   // 将容量调整为数组的当前大小，可以最小化存储空间。
   public void trimToSize() {
          modCount++;
          if (size < elementData.length) {
              elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
          }
      }
      
   // 增加此实例的容量，minCapacity 所需的最小容量
   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);
       }
   }
   
   private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       ensureExplicitCapacity(minCapacity);
   }

   private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }

   // 数组最大容量（分配过大容量可能会导致 OOM 异常，因为超过了虚拟机限制）
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

   // 增加容量到可以容纳 minCapacity 个元素。
   private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       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;
   }
   
   // 返回集合元素个数
   public int size() {
       return size;
   }

   // 检查是否为空
   public boolean isEmpty() {
       return size == 0;
   }

   // 检查是否存在元素： o 
   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;
   }
   
   // 浅clone，不会复制元素本身。
   public Object clone() {
       try {
           ArrayList<?> v = (ArrayList<?>) 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);
       }
   }
   
   // 返回包含所有元素的数组，该数组是安全的。（此方法分配的是一个全新的数组，没有对它的引用存在，故调用者可对其自由修改。）
   public Object[] toArray() {
       return Arrays.copyOf(elementData, size);
   }

   // 返回包含参数数组中所有元素的数组。
   @SuppressWarnings("unchecked")
   public <T> T[] toArray(T[] a) {
       if (a.length < size)
           // 建一个 a 类型的新数组, 并填充当前集合的元素到其中。
           return (T[]) Arrays.copyOf(elementData, size, a.getClass());
       System.arraycopy(elementData, 0, a, 0, size);
       if (a.length > size)
           a[size] = null;
       return a;
   }

   // 返回对应索引位的元素   
   @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;
   }
   
   // 于末尾新增指定元素
   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);  // Increments modCount!!
       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);

       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;
   }
   
   // 快速删除：跳过边界检查，且无返回
   private 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
   }
   
   // 清空集合
   public void clear() {
       modCount++;

       // clear to let GC do its work
       for (int i = 0; i < size; i++)
           elementData[i] = null;

       size = 0;
   }
   
   // 追加指定非空集合所有元素到本集合末尾
   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;
   }
   
   // 从指定位置开始插入指定非空集合中的所有元素
   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));
   }

   // add 和 addAll使用的 rangeCheck 版本
   private void rangeCheckForAdd(int index) {
       if (index > size || index < 0)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }
   
   // 构造索引越界（下标越界）的返回信息内容：索引值 + 集合总容量大小。
   private String outOfBoundsMsg(int index) {
       return "Index: "+index+", Size: "+size;
   }

   // 删除指定集合中的所有元素
   public boolean removeAll(Collection<?> c) {
       Objects.requireNonNull(c);
       return batchRemove(c, false);
   }
   
   // 仅保留指定集合中的元素，删除其余元素。
   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;
   }
   
   // 保存到流，即：序列化。
   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();
       }
   }
   
   // 从流重组为集合，即：反序列化。
   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
           ensureCapacityInternal(size);

           Object[] a = elementData;
           // Read in all elements in the proper order.
           for (int i=0; i<size; i++) {
               a[i] = s.readObject();
           }
       }
   }
   
   // 返回从指定索引位开始的迭代器
   public ListIterator<E> listIterator(int index) {
       if (index < 0 || index > size)
           throw new IndexOutOfBoundsException("Index: "+index);
       return new ListItr(index);
   }
   
   // 以适当的顺序，返回包含此集合所有元素的集合迭代器。
   public ListIterator<E> listIterator() {
       return new ListItr(0);
   }
   
   // 以适当的顺序，返回包含此集合所有元素的迭代器。
   public Iterator<E> iterator() {
       return new Itr();
   }
   
   // 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;

       public boolean hasNext() {
           return cursor != size;
       }

       @SuppressWarnings("unchecked")
       public E next() {
           checkForComodification();
           int i = cursor;
           if (i >= size)
               throw new NoSuchElementException();
           Object[] elementData = ArrayList.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 {
               ArrayList.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 = ArrayList.this.size;
           int i = cursor;
           if (i >= size) {
               return;
           }
           final Object[] elementData = ArrayList.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();
       }
   }
   
   // 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 = ArrayList.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 {
               ArrayList.this.set(lastRet, e);
           } catch (IndexOutOfBoundsException ex) {
               throw new ConcurrentModificationException();
           }
       }

       public void add(E e) {
           checkForComodification();

           try {
               int i = cursor;
               ArrayList.this.add(i, e);
               cursor = i + 1;
               lastRet = -1;
               expectedModCount = modCount;
           } catch (IndexOutOfBoundsException ex) {
               throw new ConcurrentModificationException();
           }
       }
   }
   
   // 返回子集合，前闭后开。fromIndex = toIndex 时返回空集合。
   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 = ArrayList.this.modCount;
       }

       public E set(int index, E e) {
           rangeCheck(index);
           checkForComodification();
           E oldValue = ArrayList.this.elementData(offset + index);
           ArrayList.this.elementData[offset + index] = e;
           return oldValue;
       }

       public E get(int index) {
           rangeCheck(index);
           checkForComodification();
           return ArrayList.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 = ArrayList.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 = ArrayList.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 = ArrayList.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 = ArrayList.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 = ArrayList.this.modCount;
                   } catch (IndexOutOfBoundsException ex) {
                       throw new ConcurrentModificationException();
                   }
               }

               public void set(E e) {
                   if (lastRet < 0)
                       throw new IllegalStateException();
                   checkForComodification();

                   try {
                       ArrayList.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 = ArrayList.this.modCount;
                   } catch (IndexOutOfBoundsException ex) {
                       throw new ConcurrentModificationException();
                   }
               }

               final void checkForComodification() {
                   if (expectedModCount != ArrayList.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 (ArrayList.this.modCount != this.modCount)
               throw new ConcurrentModificationException();
       }

       public Spliterator<E> spliterator() {
           checkForComodification();
           return new ArrayListSpliterator<E>(ArrayList.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();
       }
   }
   
   // 创建一个拆分器，@since 1.8。
   @Override
   public Spliterator<E> spliterator() {
       return new ArrayListSpliterator<>(this, 0, -1, 0);
   }

   // 延迟初始化的拆分器。
   static final class ArrayListSpliterator<E> implements Spliterator<E> {

       // 如果集合结构是不变的，没有CRUD操作，则用 Arrays.spliterator 实现拆分. 
       private final ArrayList<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(ArrayList<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)
           ArrayList<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
           ArrayList<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;
       }
   }
   
   // Predicate 函数式编程，参见个人博客 ：https://blog.csdn.net/jiangyu1013/article/details/103500724
   @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;
   }

   // Predicate 函数式编程，参见个人博客 ：https://blog.csdn.net/jiangyu1013/article/details/103500724
   @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++;
   }