ArrayList源码解析（JDK1.8）

   1 package java.util;
   2 
   3 import sun.misc.SharedSecrets;
   4 
   5 import java.util.function.Consumer;
   6 import java.util.function.Predicate;
   7 import java.util.function.UnaryOperator;
   8 
   9 
  10 /**
  11  * 概述：
  12  * List接口可调整大小的数组实现。实现所有可选的List操作，并允许所有元素，包括null，元素可重复。
  13  * 除了列表接口外，该类提供了一种方法来操作该数组的大小来存储该列表中的数组的大小。
  14  * 时间复杂度：
  15  * 方法size、isEmpty、get、set、iterator和listIterator的调用是常数时间的。
  16  * 添加删除的时间复杂度为O(N)。其他所有操作也都是线性时间复杂度。
  17  * 容量：
  18  * 每个ArrayList都有容量，容量大小至少为List元素的长度，默认初始化为10。
  19  * 容量可以自动增长。
  20  * 如果提前知道数组元素较多，可以在添加元素前通过调用ensureCapacity()方法提前增加容量以减小后期容量自动增长的开销。
  21  * 也可以通过带初始容量的构造器初始化这个容量。
  22  * 线程不安全：
  23  * ArrayList不是线程安全的。
  24  * 如果需要应用到多线程中，需要在外部做同步
  25  * modCount：
  26  * 定义在AbstractList中：protected transient int modCount = 0;
  27  * 已从结构上修改此列表的次数。从结构上修改是指更改列表的大小，或者打乱列表，从而使正在进行的迭代产生错误的结果。
  28  * 此字段由iterator和listiterator方法返回的迭代器和列表迭代器实现使用。
  29  * 如果意外更改了此字段中的值，则迭代器（或列表迭代器）将抛出concurrentmodificationexception来响应next、remove、previous、set或add操作。
  30  * 在迭代期间面临并发修改时，它提供了快速失败 行为，而不是非确定性行为。
  31  * 子类是否使用此字段是可选的。
  32  * 如果子类希望提供快速失败迭代器（和列表迭代器），则它只需在其 add(int,e)和remove(int)方法（以及它所重写的、导致列表结构上修改的任何其他方法）中增加此字段。
  33  * 对add(int, e)或remove(int)的单个调用向此字段添加的数量不得超过 1，否则迭代器（和列表迭代器）将抛出虚假的 concurrentmodificationexceptions。
  34  * 如果某个实现不希望提供快速失败迭代器，则可以忽略此字段。
  35  * transient：
  36  * 默认情况下,对象的所有成员变量都将被持久化.在某些情况下,如果你想避免持久化对象的一些成员变量,你可以使用transient关键字来标记他们,transient也是java中的保留字(JDK 1.8)
  37  */
  38 
  39 public class ArrayList<E> extends AbstractList<E>
  40         implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
  41     private static final long serialVersionUID = 8683452581122892189L;
  42 
  43     /**
  44      * 默认容量
  45      */
  46     private static final int DEFAULT_CAPACITY = 10;
  47 
  48     /**
  49      * 空的对象数组
  50      */
  51     private static final Object[] EMPTY_ELEMENTDATA = {};
  52 
  53     /**
  54      * 默认的空数组
  55      * 无参构造函数创建的数组
  56      */
  57     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  58 
  59     /**
  60      * 存放数据的数组的缓存变量，不可序列化
  61      */
  62     transient Object[] elementData;
  63 
  64     /**
  65      * 元素数量
  66      *
  67      * @serial
  68      */
  69     private int size;
  70 
  71     /**
  72      * 带有容量initialCapacity的构造方法
  73      *
  74      * @param 初始容量列表的初始容量
  75      * @throws IllegalArgumentException 如果指定容量为负
  76      */
  77     public ArrayList(int initialCapacity) {
  78         // 如果初始化时ArrayList大小大于0
  79         if (initialCapacity > 0) {
  80             // new一个该大小的object数组赋给elementData
  81             this.elementData = new Object[initialCapacity];
  82         } else if (initialCapacity == 0) {// 如果大小为0
  83             // 将空数组赋给elementData
  84             this.elementData = EMPTY_ELEMENTDATA;
  85         } else {// 小于0
  86             // 则抛出IllegalArgumentException异常
  87             throw new IllegalArgumentException("Illegal Capacity: " +
  88                     initialCapacity);
  89         }
  90     }
  91 
  92     /**
  93      * 不带参数的构造方法
  94      */
  95     public ArrayList() {
  96         // 直接将空数组赋给elementData
  97         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  98     }
  99 
 100     /**
 101      * 带参数Collection的构造方法
 102      *
 103      * @param c 其元素将被放入此列表中的集合
 104      * @throws NullPointerException 如果指定的集合是空的
 105      */
 106     public ArrayList(Collection<? extends E> c) {
 107         elementData = c.toArray();
 108         if ((size = elementData.length) != 0) {
 109             // c.toarray可能（错误地）不返回对象[]（见JAVA BUG编号6260652）
 110             if (elementData.getClass() != Object[].class)
 111                 elementData = Arrays.copyOf(elementData, size, Object[].class);
 112         } else {
 113             // 使用空数组
 114             this.elementData = EMPTY_ELEMENTDATA;
 115         }
 116     }
 117 
 118     /**
 119      * 因为容量常常会大于实际元素的数量。内存紧张时，可以调用该方法删除预留的位置，调整容量为元素实际数量。
 120      * 如果确定不会再有元素添加进来时也可以调用该方法来节约空间
 121      */
 122     public void trimToSize() {
 123         modCount++;
 124         // 如果size小于length
 125         if (size < elementData.length) {
 126             // 重新将elementData设置大小为size
 127             elementData = (size == 0)
 128                     ? EMPTY_ELEMENTDATA
 129                     : Arrays.copyOf(elementData, size);
 130         }
 131     }
 132 
 133     /**
 134      * 使用指定参数设置数组容量
 135      *
 136      * @param minCapacity 所需的最小容量
 137      */
 138     public void ensureCapacity(int minCapacity) {
 139         //如果数组为空，容量预取0，否则去默认值(10)
 140         int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
 141                 // any size if not default element table
 142                 ? 0
 143                 // larger than default for default empty table. It's already
 144                 // supposed to be at default size.
 145                 : DEFAULT_CAPACITY;
 146         //若参数大于预设的容量，在使用该参数进一步设置数组容量
 147         if (minCapacity > minExpand) {
 148             ensureExplicitCapacity(minCapacity);
 149         }
 150     }
 151 
 152     private static int calculateCapacity(Object[] elementData, int minCapacity) {
 153         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 154             return Math.max(DEFAULT_CAPACITY, minCapacity);
 155         }
 156         return minCapacity;
 157     }
 158 
 159     /**
 160      * 得到最小扩容量
 161      *
 162      * @param minCapacity
 163      */
 164     private void ensureCapacityInternal(int minCapacity) {
 165         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 166     }
 167 
 168     /**
 169      * 判断是否需要扩容
 170      *
 171      * @param minCapacity
 172      */
 173     private void ensureExplicitCapacity(int minCapacity) {
 174         modCount++;
 175 
 176         // 如果最小需要空间比elementData的内存空间要大，则需要扩容
 177         if (minCapacity - elementData.length > 0)
 178             grow(minCapacity);
 179     }
 180 
 181     /**
 182      * 数组的最大容量，可能会导致内存溢出(VM内存限制)
 183      */
 184     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 185 
 186     /**
 187      * 扩容，以确保它可以至少持有由参数指定的元素的数目
 188      *
 189      * @param minCapacity 所需的最小容量
 190      */
 191     private void grow(int minCapacity) {
 192         // 获取到ArrayList中elementData数组的内存空间长度
 193         int oldCapacity = elementData.length;
 194         // 扩容至原来的1.5倍
 195         int newCapacity = oldCapacity + (oldCapacity >> 1);
 196         // 再判断一下新数组的容量够不够，够了就直接使用这个长度创建新数组，
 197         // 不够就将数组长度设置为需要的长度
 198         if (newCapacity - minCapacity < 0)
 199             newCapacity = minCapacity;
 200         //若预设值大于默认的最大值检查是否溢出
 201         if (newCapacity - MAX_ARRAY_SIZE > 0)
 202             newCapacity = hugeCapacity(minCapacity);
 203         // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
 204         // 并将elementData的数据复制到新的内存空间
 205         elementData = Arrays.copyOf(elementData, newCapacity);
 206     }
 207 
 208     /**
 209      * 检查是否溢出，若没有溢出，返回最大整数值(java中的int为4字节，所以最大为0x7fffffff)或默认最大值
 210      *
 211      * @param minCapacity
 212      * @return
 213      */
 214     private static int hugeCapacity(int minCapacity) {
 215         if (minCapacity < 0)   //溢出
 216             throw new OutOfMemoryError();
 217         return (minCapacity > MAX_ARRAY_SIZE) ?
 218                 Integer.MAX_VALUE :
 219                 MAX_ARRAY_SIZE;
 220     }
 221 
 222     /**
 223      * 返回ArrayList的大小
 224      *
 225      * @return ArrayList中的元素数量
 226      */
 227     public int size() {
 228         return size;
 229     }
 230 
 231     /**
 232      * 返回是否为空
 233      *
 234      * @return true 如果ArrayList中无元素
 235      */
 236     public boolean isEmpty() {
 237         return size == 0;
 238     }
 239 
 240     /**
 241      * 是否包含一个数 返回bool
 242      *
 243      * @param o 检测o是否为ArrayList中元素
 244      * @return true 如果ArrayList中包含o元素
 245      */
 246     public boolean contains(Object o) {
 247         return indexOf(o) >= 0;
 248     }
 249 
 250 
 251     /**
 252      * 返回一个值在数组首次出现的位置，会根据是否为null使用不同方式判断。不存在就返回-1。时间复杂度为O(N)
 253      *
 254      * @param o
 255      * @return
 256      */
 257     public int indexOf(Object o) {
 258         if (o == null) {
 259             for (int i = 0; i < size; i++)
 260                 if (elementData[i] == null)
 261                     return i;
 262         } else {
 263             for (int i = 0; i < size; i++)
 264                 if (o.equals(elementData[i]))
 265                     return i;
 266         }
 267         return -1;
 268     }
 269 
 270     /**
 271      * 返回一个值在数组最后一次出现的位置，会根据是否为null使用不同方式判断。不存在就返回-1。时间复杂度为O(N)
 272      *
 273      * @param o
 274      * @return
 275      */
 276     public int lastIndexOf(Object o) {
 277         if (o == null) {
 278             for (int i = size - 1; i >= 0; i--)
 279                 if (elementData[i] == null)
 280                     return i;
 281         } else {
 282             for (int i = size - 1; i >= 0; i--)
 283                 if (o.equals(elementData[i]))
 284                     return i;
 285         }
 286         return -1;
 287     }
 288 
 289     /**
 290      * 返回副本，元素本身没有被复制，复制过程数组发生改变会抛出异常
 291      *
 292      * @return v ArrayList副本
 293      */
 294     public Object clone() {
 295         try {
 296             // 调用父类(翻看源码可见是Object类)的clone方法得到一个ArrayList副本
 297             ArrayList<?> v = (ArrayList<?>) super.clone();
 298             // 调用Arrays类的copyOf，将ArrayList的elementData数组赋值给副本的elementData数组
 299             v.elementData = Arrays.copyOf(elementData, size);
 300             v.modCount = 0;
 301             // 返回副本v
 302             return v;
 303         } catch (CloneNotSupportedException e) {
 304             // this shouldn't happen, since we are Cloneable
 305             throw new InternalError(e);
 306         }
 307     }
 308 
 309     /**
 310      * 转换为Object数组，使用Arrays.copyOf()方法
 311      *
 312      * @return 一个数组包含所有列表中的元素, 且顺序正确
 313      */
 314     public Object[] toArray() {
 315         return Arrays.copyOf(elementData, size);
 316     }
 317 
 318     /**
 319      * 将ArrayList里面的元素赋值到一个数组中去
 320      * 如果a的长度小于ArrayList的长度，直接调用Arrays类的copyOf，返回一个比a数组长度要大的新数组，里面元素就是ArrayList里面的元素；
 321      * 如果a的长度比ArrayList的长度大，那么就调用System.arraycopy，将ArrayList的elementData数组赋值到a数组，然后把a数组的size位置赋值为空。
 322      *
 323      * @param a 如果它的长度大的话，列表元素将存储在这个数组中; 否则，将为此分配一个相同运行时类型的新数组。
 324      * @return 一个包含ArrayList元素的数组
 325      * @throws ArrayStoreException  将与数组类型不兼容的值赋值给数组元素时抛出的异常
 326      * @throws NullPointerException 数组为空
 327      */
 328     @SuppressWarnings("unchecked")
 329     public <T> T[] toArray(T[] a) {
 330         if (a.length < size)
 331             // 创建一个新的a的运行时类型数组，内容不变
 332             return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 333         System.arraycopy(elementData, 0, a, 0, size);
 334         if (a.length > size)
 335             a[size] = null;
 336         return a;
 337     }
 338 
 339 
 340     /**
 341      * 返回指定位置的值，因为是数组，所以速度特别快
 342      *
 343      * @param index
 344      * @return
 345      */
 346     @SuppressWarnings("unchecked")
 347     E elementData(int index) {
 348         return (E) elementData[index];
 349     }
 350 
 351     /**
 352      * 返回指定位置的值，但是会先检查这个位置数否超出数组长度
 353      *
 354      * @param index 要返回的元素的索引
 355      * @return ArrayList中指定位置的元素
 356      * @throws IndexOutOfBoundsException {@inheritDoc}
 357      */
 358     public E get(int index) {
 359         // 检查是否越界
 360         rangeCheck(index);
 361         // 返回ArrayList的elementData数组index位置的元素
 362         return elementData(index);
 363     }
 364 
 365     /**
 366      * 设置指定位置为一个新值，并返回之前的值，会检查这个位置是否超出数组长度
 367      *
 368      * @param index   要替换的元素的索引
 369      * @param element 要存储在指定位置的元素
 370      * @return 之前在指定位置的元素
 371      * @throws IndexOutOfBoundsException {@inheritDoc}
 372      */
 373     public E set(int index, E element) {
 374         // 检查是否越界
 375         rangeCheck(index);
 376         // 调用elementData(index)获取到当前位置的值
 377         E oldValue = elementData(index);
 378         // 将element赋值到ArrayList的elementData数组的第index位置
 379         elementData[index] = element;
 380         return oldValue;
 381     }
 382 
 383     /**
 384      * 添加一个值，首先会确保容量
 385      *
 386      * @param e 要添加到此列表中的元素
 387      * @return <tt>true</tt> (as specified by {@link Collection#add})
 388      */
 389     public boolean add(E e) {
 390         // 扩容
 391         ensureCapacityInternal(size + 1);  // Increments modCount!!
 392         // 将e赋值给elementData的size+1的位置
 393         elementData[size++] = e;
 394         return true;
 395     }
 396 
 397     /**
 398      * 在ArrayList的index位置，添加元素element，会检查添加的位置和容量
 399      *
 400      * @param index   指定元素将被插入的索引
 401      * @param element 要插入的元素
 402      * @throws IndexOutOfBoundsException {@inheritDoc}
 403      */
 404     public void add(int index, E element) {
 405         // 判断index是否越界
 406         rangeCheckForAdd(index);
 407         // 扩容
 408         ensureCapacityInternal(size + 1);  // Increments modCount!!
 409         //public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
 410         //src:源数组； srcPos:源数组要复制的起始位置； dest:目的数组； destPos:目的数组放置的起始位置； length:复制的长度
 411         // 将elementData从index位置开始，复制到elementData的index+1开始的连续空间
 412         System.arraycopy(elementData, index, elementData, index + 1,
 413                 size - index);
 414         // 在elementData的index位置赋值element
 415         elementData[index] = element;
 416         // ArrayList的大小加一
 417         size++;
 418     }
 419 
 420     /**
 421      * 在ArrayList的移除index位置的元素,会检查添加的位置，返回之前的值
 422      *
 423      * @param index 要删除的元素的索引
 424      * @return 从ArrayList中删除的元素
 425      * @throws IndexOutOfBoundsException {@inheritDoc}
 426      */
 427     public E remove(int index) {
 428         // 判断是否越界
 429         rangeCheck(index);
 430 
 431         modCount++;
 432         // 读取旧值
 433         E oldValue = elementData(index);
 434         // 获取index位置开始到最后一个位置的个数
 435         int numMoved = size - index - 1;
 436         if (numMoved > 0)
 437             // 将elementData数组index+1位置开始拷贝到elementData从index开始的空间
 438             System.arraycopy(elementData, index + 1, elementData, index,
 439                     numMoved);
 440         // 使size-1 ，设置elementData的size位置为空，让GC来清理内存空间
 441         elementData[--size] = null; //便于垃圾回收器回收
 442 
 443         return oldValue;
 444     }
 445 
 446     /**
 447      * 在ArrayList的移除对象为O的元素，跟indexOf方法思想基本一致
 448      *
 449      * @param o 要从该列表中删除的元素（如果存在）
 450      * @return true 如果这个列表包含指定的元素
 451      */
 452     public boolean remove(Object o) {
 453         if (o == null) {
 454             for (int index = 0; index < size; index++)
 455                 if (elementData[index] == null) {
 456                     fastRemove(index);
 457                     return true;
 458                 }
 459         } else {
 460             for (int index = 0; index < size; index++)
 461                 if (o.equals(elementData[index])) {
 462                     fastRemove(index);
 463                     return true;
 464                 }
 465         }
 466         return false;
 467     }
 468 
 469 
 470     /**
 471      * 快速删除指定位置的值，之所以叫快速，应该是不需要检查和返回值，因为只内部使用
 472      *
 473      * @param index
 474      */
 475     private void fastRemove(int index) {
 476         modCount++;
 477         int numMoved = size - index - 1;
 478         if (numMoved > 0)
 479             System.arraycopy(elementData, index + 1, elementData, index,
 480                     numMoved);
 481         // 使size-1 ，设置elementData的size位置为空，让GC来清理内存空间
 482         elementData[--size] = null; //便于垃圾回收器回收
 483     }
 484 
 485     /**
 486      * 清空数组，把每一个值设为null,方便垃圾回收(不同于reset，数组默认大小有改变的话不会重置)
 487      */
 488     public void clear() {
 489         modCount++;
 490 
 491         //便于垃圾回收器回收
 492         for (int i = 0; i < size; i++)
 493             elementData[i] = null;
 494         //把size设置为0，以便我们不会浏览到null值的内存空间
 495         size = 0;
 496     }
 497 
 498     /**
 499      * 添加一个集合的元素到末端，若要添加的集合为空返回false
 500      *
 501      * @param c 包含要添加到此列表中的元素的集合
 502      * @return true 如果该列表因添加而改变
 503      * @throws NullPointerException 如果指定的集合是空的
 504      */
 505     public boolean addAll(Collection<? extends E> c) {
 506         // 将c转换为数组a
 507         Object[] a = c.toArray();
 508         // 获取a占的内存空间长度赋值给numNew
 509         int numNew = a.length;
 510         // 扩容至size + numNew
 511         ensureCapacityInternal(size + numNew);  // Increments modCount
 512         // 将a的第0位开始拷贝至elementData的size位开始，拷贝长度为numNew
 513         System.arraycopy(a, 0, elementData, size, numNew);
 514         // 将size增加numNew
 515         size += numNew;
 516         // 如果c为空，返回false，c不为空，返回true
 517         return numNew != 0;
 518     }
 519 
 520     /**
 521      * 从第index位开始，将c全部拷贝到ArrayList,若要添加的集合为空返回false
 522      *
 523      * @param index 在哪个索引处插入指定集合中的第一个元素
 524      * @param c     包含要添加到此列表中的元素的集合
 525      * @return true 如果该列表因添加而改变
 526      * @throws IndexOutOfBoundsException {@inheritDoc}
 527      * @throws NullPointerException      如果指定的集合是空的
 528      */
 529     public boolean addAll(int index, Collection<? extends E> c) {
 530         // 判断index大于size或者是小于0,如果是，则抛出IndexOutOfBoundsException异常
 531         rangeCheckForAdd(index);
 532         // 将c转换为数组a
 533         Object[] a = c.toArray();
 534         int numNew = a.length;
 535         // 扩容至size + numNew
 536         ensureCapacityInternal(size + numNew);  // Increments modCount
 537         // 获取需要添加的个数
 538         int numMoved = size - index;
 539         if (numMoved > 0)
 540             System.arraycopy(elementData, index, elementData, index + numNew,
 541                     numMoved);
 542 
 543         System.arraycopy(a, 0, elementData, index, numNew);
 544         size += numNew;
 545         return numNew != 0;
 546     }
 547 
 548     /**
 549      * 删除指定范围元素。参数为开始删的位置和结束位置
 550      *
 551      * @throws IndexOutOfBoundsException if {@code fromIndex} or
 552      *                                   {@code toIndex} is out of range
 553      *                                   ({@code fromIndex < 0 ||
 554      *                                   fromIndex >= size() ||
 555      *                                   toIndex > size() ||
 556      *                                   toIndex < fromIndex})
 557      */
 558     protected void removeRange(int fromIndex, int toIndex) {
 559         modCount++;
 560         int numMoved = size - toIndex;//后段保留的长度
 561         System.arraycopy(elementData, toIndex, elementData, fromIndex,
 562                 numMoved);
 563 
 564         //便于垃圾回收期回收
 565         int newSize = size - (toIndex - fromIndex);
 566         for (int i = newSize; i < size; i++) {
 567             elementData[i] = null;
 568         }
 569         size = newSize;
 570     }
 571 
 572     /**
 573      * 检查index是否超出数组长度 用于添加元素时
 574      */
 575     private void rangeCheck(int index) {
 576         // 如果下标超过ArrayList的数组长度
 577         if (index >= size)
 578             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 579     }
 580 
 581     /**
 582      * 检查是否溢出
 583      */
 584     private void rangeCheckForAdd(int index) {
 585         if (index > size || index < 0)
 586             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 587     }
 588 
 589     /**
 590      * 抛出的异常的详情
 591      */
 592     private String outOfBoundsMsg(int index) {
 593         return "Index: " + index + ", Size: " + size;
 594     }
 595 
 596     /**
 597      * ArrayList移除集合c中的所有元素
 598      *
 599      * @param c 包含要从此列表中移除的元素的集合
 600      * @return {@code true} 如果该列表因移除而改变
 601      * @throws ClassCastException   if the class of an element of this list
 602      *                              is incompatible with the specified collection
 603      *                              (<a href="Collection.html#optional-restrictions">optional</a>)
 604      * @throws NullPointerException if this list contains a null element and the
 605      *                              specified collection does not permit null elements
 606      *                              (<a href="Collection.html#optional-restrictions">optional</a>),
 607      *                              or if the specified collection is null
 608      * @see Collection#contains(Object)
 609      */
 610     public boolean removeAll(Collection<?> c) {
 611         // 如果c为空，则抛出空指针异常
 612         Objects.requireNonNull(c);
 613         // 调用batchRemove移除c中的元素
 614         return batchRemove(c, false);
 615     }
 616 
 617     /**
 618      * 仅保留指定集合c中的元素
 619      *
 620      * @param c collection containing elements to be retained in this list
 621      * @return {@code true} if this list changed as a result of the call
 622      * @throws ClassCastException   if the class of an element of this list
 623      *                              is incompatible with the specified collection
 624      *                              (<a href="Collection.html#optional-restrictions">optional</a>)
 625      * @throws NullPointerException if this list contains a null element and the
 626      *                              specified collection does not permit null elements
 627      *                              (<a href="Collection.html#optional-restrictions">optional</a>),
 628      *                              or if the specified collection is null
 629      * @see Collection#contains(Object)
 630      */
 631     public boolean retainAll(Collection<?> c) {
 632         Objects.requireNonNull(c);
 633         // 调用batchRemove保留c中的元素
 634         return batchRemove(c, true);
 635     }
 636 
 637     /**
 638      * 根据complement值，将ArrayList中包含c中元素的元素删除或者保留
 639      *
 640      * @param c
 641      * @param complement true时从数组保留指定集合中元素的值，为false时从数组删除指定集合中元素的值。
 642      * @return 数组中重复的元素都会被删除(而不是仅删除一次或几次)，有任何删除操作都会返回true
 643      */
 644     private boolean batchRemove(Collection<?> c, boolean complement) {
 645         final Object[] elementData = this.elementData;
 646         // 定义一个w，一个r，两个同时右移
 647         int r = 0, w = 0;
 648         boolean modified = false;
 649         try {
 650             // r先右移
 651             for (; r < size; r++)
 652                 // 如果c中不包含elementData[r]这个元素
 653                 if (c.contains(elementData[r]) == complement)
 654                     // 则直接将r位置的元素赋值给w位置的元素，w自增
 655                     elementData[w++] = elementData[r];
 656         } finally {
 657             // 防止抛出异常导致上面r的右移过程没完成
 658             if (r != size) {
 659                 // 将r未右移完成的位置的元素赋值给w右边位置的元素
 660                 System.arraycopy(elementData, r,
 661                         elementData, w,
 662                         size - r);
 663                 // 修改w值增加size-r
 664                 w += size - r;
 665             }
 666             // 如果有被覆盖掉的元素，则将w后面的元素都赋值为null
 667             if (w != size) {
 668                 // clear to let GC do its work
 669                 for (int i = w; i < size; i++)
 670                     elementData[i] = null;
 671                 modCount += size - w;//改变的次数
 672                 //新的大小为保留的元素的个数
 673                 size = w;
 674                 modified = true;
 675             }
 676         }
 677         return modified;
 678     }
 679 
 680     /**
 681      * 保存数组实例的状态到一个流（即序列化）。写入过程数组被更改会抛出异常
 682      *
 683      * @serialData The length of the array backing the <tt>ArrayList</tt>
 684      * instance is emitted (int), followed by all of its elements
 685      * (each an <tt>Object</tt>) in the proper order.
 686      */
 687     private void writeObject(java.io.ObjectOutputStream s)
 688             throws java.io.IOException {
 689         // Write out element count, and any hidden stuff
 690         int expectedModCount = modCount;
 691         //执行默认的反序列化/序列化过程。将当前类的非静态和非瞬态字段写入此流
 692         s.defaultWriteObject();
 693 
 694         // 写入大小
 695         s.writeInt(size);
 696 
 697         // 按顺序写入所有元素
 698         for (int i = 0; i < size; i++) {
 699             s.writeObject(elementData[i]);
 700         }
 701 
 702         if (modCount != expectedModCount) {
 703             throw new ConcurrentModificationException();
 704         }
 705     }
 706 
 707     /**
 708      * 从流中重构ArrayList实例（即反序列化）。
 709      */
 710     private void readObject(java.io.ObjectInputStream s)
 711             throws java.io.IOException, ClassNotFoundException {
 712         elementData = EMPTY_ELEMENTDATA;
 713 
 714         // 执行默认的序列化/反序列化过程
 715         s.defaultReadObject();
 716 
 717         // 读入数组长度
 718         s.readInt(); // ignored
 719 
 720         if (size > 0) {
 721             // 像clone()方法 ，但根据大小而不是容量分配数组
 722             int capacity = calculateCapacity(elementData, size);
 723             SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
 724             ensureCapacityInternal(size);
 725 
 726             Object[] a = elementData;
 727             //读入所有元素
 728             for (int i = 0; i < size; i++) {
 729                 a[i] = s.readObject();
 730             }
 731         }
 732     }
 733 
 734     /**
 735      * 返回一个从index开始的ListIterator对象
 736      *
 737      * @throws IndexOutOfBoundsException {@inheritDoc}
 738      */
 739     public ListIterator<E> listIterator(int index) {
 740         if (index < 0 || index > size)
 741             throw new IndexOutOfBoundsException("Index: " + index);
 742         return new ListItr(index);
 743     }
 744 
 745     /**
 746      * 返回一个ListIterator对象，ListItr为ArrayList的一个内部类，其实现了ListIterator<E> 接口
 747      *
 748      * @see #listIterator(int)
 749      */
 750     public ListIterator<E> listIterator() {
 751         return new ListItr(0);
 752     }
 753 
 754     /**
 755      * 返回一个Iterator对象，Itr为ArrayList的一个内部类，其实现了Iterator<E>接口
 756      *
 757      * @return an iterator over the elements in this list in proper sequence
 758      */
 759     public Iterator<E> iterator() {
 760         return new Itr();
 761     }
 762 
 763     /**
 764      * 通用的迭代器实现
 765      */
 766     private class Itr implements Iterator<E> {
 767         int cursor;       //游标，下一个元素的索引，默认初始化为0
 768         int lastRet = -1; //上次访问的元素的位置
 769         int expectedModCount = modCount;//迭代过程不运行修改数组，否则就抛出异常
 770 
 771         //是否还有下一个
 772         public boolean hasNext() {
 773             return cursor != size;
 774         }
 775 
 776         //下一个元素
 777         @SuppressWarnings("unchecked")
 778         public E next() {
 779             checkForComodification();//检查数组是否被修改
 780             int i = cursor;
 781             if (i >= size)
 782                 throw new NoSuchElementException();
 783             Object[] elementData = ArrayList.this.elementData;
 784             if (i >= elementData.length)
 785                 throw new ConcurrentModificationException();
 786             cursor = i + 1;//向后移动游标
 787             return (E) elementData[lastRet = i];//设置访问的位置并返回这个值
 788         }
 789 
 790         //删除元素
 791         public void remove() {
 792             if (lastRet < 0)
 793                 throw new IllegalStateException();
 794             checkForComodification();//检查数组是否被修改
 795 
 796             try {
 797                 ArrayList.this.remove(lastRet);
 798                 cursor = lastRet;
 799                 lastRet = -1;
 800                 expectedModCount = modCount;
 801             } catch (IndexOutOfBoundsException ex) {
 802                 throw new ConcurrentModificationException();
 803             }
 804         }
 805 
 806         @Override
 807         @SuppressWarnings("unchecked")
 808         public void forEachRemaining(Consumer<? super E> consumer) {
 809             Objects.requireNonNull(consumer);
 810             final int size = ArrayList.this.size;
 811             int i = cursor;
 812             if (i >= size) {
 813                 return;
 814             }
 815             final Object[] elementData = ArrayList.this.elementData;
 816             if (i >= elementData.length) {
 817                 throw new ConcurrentModificationException();
 818             }
 819             while (i != size && modCount == expectedModCount) {
 820                 consumer.accept((E) elementData[i++]);
 821             }
 822             // update once at end of iteration to reduce heap write traffic
 823             cursor = i;
 824             lastRet = i - 1;
 825             checkForComodification();
 826         }
 827 
 828         //检查数组是否被修改
 829         final void checkForComodification() {
 830             if (modCount != expectedModCount)
 831                 throw new ConcurrentModificationException();
 832         }
 833     }
 834 
 835     /**
 836      * ListIterator迭代器实现
 837      */
 838     private class ListItr extends Itr implements ListIterator<E> {
 839         ListItr(int index) {
 840             super();
 841             cursor = index;
 842         }
 843 
 844         public boolean hasPrevious() {
 845             return cursor != 0;
 846         }
 847 
 848         public int nextIndex() {
 849             return cursor;
 850         }
 851 
 852         public int previousIndex() {
 853             return cursor - 1;
 854         }
 855 
 856         @SuppressWarnings("unchecked")
 857         public E previous() {
 858             checkForComodification();
 859             int i = cursor - 1;
 860             if (i < 0)
 861                 throw new NoSuchElementException();
 862             Object[] elementData = ArrayList.this.elementData;
 863             if (i >= elementData.length)
 864                 throw new ConcurrentModificationException();
 865             cursor = i;
 866             return (E) elementData[lastRet = i];
 867         }
 868 
 869         public void set(E e) {
 870             if (lastRet < 0)
 871                 throw new IllegalStateException();
 872             checkForComodification();
 873 
 874             try {
 875                 ArrayList.this.set(lastRet, e);
 876             } catch (IndexOutOfBoundsException ex) {
 877                 throw new ConcurrentModificationException();
 878             }
 879         }
 880 
 881         public void add(E e) {
 882             checkForComodification();
 883 
 884             try {
 885                 int i = cursor;
 886                 ArrayList.this.add(i, e);
 887                 cursor = i + 1;
 888                 lastRet = -1;
 889                 expectedModCount = modCount;
 890             } catch (IndexOutOfBoundsException ex) {
 891                 throw new ConcurrentModificationException();
 892             }
 893         }
 894     }
 895 
 896     /**
 897      * Returns a view of the portion of this list between the specified
 898      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
 899      * {@code fromIndex} and {@code toIndex} are equal, the returned list is
 900      * empty.)  The returned list is backed by this list, so non-structural
 901      * changes in the returned list are reflected in this list, and vice-versa.
 902      * The returned list supports all of the optional list operations.
 903      * <p>
 904      * <p>This method eliminates the need for explicit range operations (of
 905      * the sort that commonly exist for arrays).  Any operation that expects
 906      * a list can be used as a range operation by passing a subList view
 907      * instead of a whole list.  For example, the following idiom
 908      * removes a range of elements from a list:
 909      * <pre>
 910      *      list.subList(from, to).clear();
 911      * </pre>
 912      * Similar idioms may be constructed for {@link #indexOf(Object)} and
 913      * {@link #lastIndexOf(Object)}, and all of the algorithms in the
 914      * {@link Collections} class can be applied to a subList.
 915      * <p>
 916      * <p>The semantics of the list returned by this method become undefined if
 917      * the backing list (i.e., this list) is <i>structurally modified</i> in
 918      * any way other than via the returned list.  (Structural modifications are
 919      * those that change the size of this list, or otherwise perturb it in such
 920      * a fashion that iterations in progress may yield incorrect results.)
 921      *
 922      * @throws IndexOutOfBoundsException {@inheritDoc}
 923      * @throws IllegalArgumentException  {@inheritDoc}
 924      */
 925     public List<E> subList(int fromIndex, int toIndex) {
 926         subListRangeCheck(fromIndex, toIndex, size);
 927         return new SubList(this, 0, fromIndex, toIndex);
 928     }
 929 
 930     /**
 931      * 安全检查
 932      *
 933      * @param fromIndex
 934      * @param toIndex
 935      * @param size
 936      */
 937     static void subListRangeCheck(int fromIndex, int toIndex, int size) {
 938         if (fromIndex < 0)
 939             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 940         if (toIndex > size)
 941             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 942         if (fromIndex > toIndex)
 943             throw new IllegalArgumentException("fromIndex(" + fromIndex +
 944                     ") > toIndex(" + toIndex + ")");
 945     }
 946 
 947     /**
 948      * 子数组
 949      */
 950     private class SubList extends AbstractList<E> implements RandomAccess {
 951         private final AbstractList<E> parent;
 952         private final int parentOffset;
 953         private final int offset;
 954         int size;
 955 
 956         SubList(AbstractList<E> parent,
 957                 int offset, int fromIndex, int toIndex) {
 958             this.parent = parent;
 959             this.parentOffset = fromIndex;
 960             this.offset = offset + fromIndex;
 961             this.size = toIndex - fromIndex;
 962             this.modCount = ArrayList.this.modCount;
 963         }
 964 
 965         public E set(int index, E e) {
 966             rangeCheck(index);
 967             checkForComodification();
 968             E oldValue = ArrayList.this.elementData(offset + index);
 969             ArrayList.this.elementData[offset + index] = e;
 970             return oldValue;
 971         }
 972 
 973         public E get(int index) {
 974             rangeCheck(index);
 975             checkForComodification();
 976             return ArrayList.this.elementData(offset + index);
 977         }
 978 
 979         public int size() {
 980             checkForComodification();
 981             return this.size;
 982         }
 983 
 984         public void add(int index, E e) {
 985             rangeCheckForAdd(index);
 986             checkForComodification();
 987             parent.add(parentOffset + index, e);
 988             this.modCount = parent.modCount;
 989             this.size++;
 990         }
 991 
 992         public E remove(int index) {
 993             rangeCheck(index);
 994             checkForComodification();
 995             E result = parent.remove(parentOffset + index);
 996             this.modCount = parent.modCount;
 997             this.size--;
 998             return result;
 999         }
1000 
1001         protected void removeRange(int fromIndex, int toIndex) {
1002             checkForComodification();
1003             parent.removeRange(parentOffset + fromIndex,
1004                     parentOffset + toIndex);
1005             this.modCount = parent.modCount;
1006             this.size -= toIndex - fromIndex;
1007         }
1008 
1009         public boolean addAll(Collection<? extends E> c) {
1010             return addAll(this.size, c);
1011         }
1012 
1013         public boolean addAll(int index, Collection<? extends E> c) {
1014             rangeCheckForAdd(index);
1015             int cSize = c.size();
1016             if (cSize == 0)
1017                 return false;
1018 
1019             checkForComodification();
1020             parent.addAll(parentOffset + index, c);
1021             this.modCount = parent.modCount;
1022             this.size += cSize;
1023             return true;
1024         }
1025 
1026         public Iterator<E> iterator() {
1027             return listIterator();
1028         }
1029 
1030         public ListIterator<E> listIterator(final int index) {
1031             checkForComodification();
1032             rangeCheckForAdd(index);
1033             final int offset = this.offset;
1034 
1035             return new ListIterator<E>() {
1036                 int cursor = index;
1037                 int lastRet = -1;
1038                 int expectedModCount = ArrayList.this.modCount;
1039 
1040                 public boolean hasNext() {
1041                     return cursor != SubList.this.size;
1042                 }
1043 
1044                 @SuppressWarnings("unchecked")
1045                 public E next() {
1046                     checkForComodification();
1047                     int i = cursor;
1048                     if (i >= SubList.this.size)
1049                         throw new NoSuchElementException();
1050                     Object[] elementData = ArrayList.this.elementData;
1051                     if (offset + i >= elementData.length)
1052                         throw new ConcurrentModificationException();
1053                     cursor = i + 1;
1054                     return (E) elementData[offset + (lastRet = i)];
1055                 }
1056 
1057                 public boolean hasPrevious() {
1058                     return cursor != 0;
1059                 }
1060 
1061                 @SuppressWarnings("unchecked")
1062                 public E previous() {
1063                     checkForComodification();
1064                     int i = cursor - 1;
1065                     if (i < 0)
1066                         throw new NoSuchElementException();
1067                     Object[] elementData = ArrayList.this.elementData;
1068                     if (offset + i >= elementData.length)
1069                         throw new ConcurrentModificationException();
1070                     cursor = i;
1071                     return (E) elementData[offset + (lastRet = i)];
1072                 }
1073 
1074                 @SuppressWarnings("unchecked")
1075                 public void forEachRemaining(Consumer<? super E> consumer) {
1076                     Objects.requireNonNull(consumer);
1077                     final int size = SubList.this.size;
1078                     int i = cursor;
1079                     if (i >= size) {
1080                         return;
1081                     }
1082                     final Object[] elementData = ArrayList.this.elementData;
1083                     if (offset + i >= elementData.length) {
1084                         throw new ConcurrentModificationException();
1085                     }
1086                     while (i != size && modCount == expectedModCount) {
1087                         consumer.accept((E) elementData[offset + (i++)]);
1088                     }
1089                     // update once at end of iteration to reduce heap write traffic
1090                     lastRet = cursor = i;
1091                     checkForComodification();
1092                 }
1093 
1094                 public int nextIndex() {
1095                     return cursor;
1096                 }
1097 
1098                 public int previousIndex() {
1099                     return cursor - 1;
1100                 }
1101 
1102                 public void remove() {
1103                     if (lastRet < 0)
1104                         throw new IllegalStateException();
1105                     checkForComodification();
1106 
1107                     try {
1108                         SubList.this.remove(lastRet);
1109                         cursor = lastRet;
1110                         lastRet = -1;
1111                         expectedModCount = ArrayList.this.modCount;
1112                     } catch (IndexOutOfBoundsException ex) {
1113                         throw new ConcurrentModificationException();
1114                     }
1115                 }
1116 
1117                 public void set(E e) {
1118                     if (lastRet < 0)
1119                         throw new IllegalStateException();
1120                     checkForComodification();
1121 
1122                     try {
1123                         ArrayList.this.set(offset + lastRet, e);
1124                     } catch (IndexOutOfBoundsException ex) {
1125                         throw new ConcurrentModificationException();
1126                     }
1127                 }
1128 
1129                 public void add(E e) {
1130                     checkForComodification();
1131 
1132                     try {
1133                         int i = cursor;
1134                         SubList.this.add(i, e);
1135                         cursor = i + 1;
1136                         lastRet = -1;
1137                         expectedModCount = ArrayList.this.modCount;
1138                     } catch (IndexOutOfBoundsException ex) {
1139                         throw new ConcurrentModificationException();
1140                     }
1141                 }
1142 
1143                 final void checkForComodification() {
1144                     if (expectedModCount != ArrayList.this.modCount)
1145                         throw new ConcurrentModificationException();
1146                 }
1147             };
1148         }
1149 
1150         /**
1151          * 返回指定范围的子数组
1152          *
1153          * @param fromIndex
1154          * @param toIndex
1155          * @return
1156          */
1157         public List<E> subList(int fromIndex, int toIndex) {
1158             subListRangeCheck(fromIndex, toIndex, size);
1159             return new SubList(this, offset, fromIndex, toIndex);
1160         }
1161 
1162         private void rangeCheck(int index) {
1163             if (index < 0 || index >= this.size)
1164                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1165         }
1166 
1167         private void rangeCheckForAdd(int index) {
1168             if (index < 0 || index > this.size)
1169                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1170         }
1171 
1172         private String outOfBoundsMsg(int index) {
1173             return "Index: " + index + ", Size: " + this.size;
1174         }
1175 
1176         private void checkForComodification() {
1177             if (ArrayList.this.modCount != this.modCount)
1178                 throw new ConcurrentModificationException();
1179         }
1180 
1181         public Spliterator<E> spliterator() {
1182             checkForComodification();
1183             return new ArrayListSpliterator<E>(ArrayList.this, offset,
1184                     offset + this.size, this.modCount);
1185         }
1186     }
1187 
1188     @Override
1189     public void forEach(Consumer<? super E> action) {
1190         Objects.requireNonNull(action);
1191         final int expectedModCount = modCount;
1192         @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData;
1193         final int size = this.size;
1194         for (int i = 0; modCount == expectedModCount && i < size; i++) {
1195             action.accept(elementData[i]);
1196         }
1197         if (modCount != expectedModCount) {
1198             throw new ConcurrentModificationException();
1199         }
1200     }
1201 
1202     /**
1203      * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
1204      * and <em>fail-fast</em> {@link Spliterator} over the elements in this
1205      * list.
1206      * <p>
1207      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
1208      * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
1209      * Overriding implementations should document the reporting of additional
1210      * characteristic values.
1211      *
1212      * @return a {@code Spliterator} over the elements in this list
1213      * @since 1.8
1214      */
1215     @Override
1216     public Spliterator<E> spliterator() {
1217         return new ArrayListSpliterator<>(this, 0, -1, 0);
1218     }
1219 
1220     /**
1221      * Index-based split-by-two, lazily initialized Spliterator
1222      */
1223     static final class ArrayListSpliterator<E> implements Spliterator<E> {
1224 
1225         /**
1226          * 如果ArrayLists是不可变的，或者在结构上不可变（不添加，删除等），我们可以用Arrays.spliterator实现它们的分割器。
1227          * 相反，我们在遍历期间检测到尽可能多的干扰而不会影响性能。
1228          * 我们主要依靠modCounts。这些不能保证检测到并发冲突，有时对线程内干扰过于保守，但在实践中检测到足够的问题是值得的。
1229          * 为了实现这一点，我们
1230          * （1）懒惰地初始化fence和expectedModCount，直到我们需要提交到我们正在检查的状态的最后一点;从而提高精度。
1231          * （这不适用于SubLists，它会使用当前非惰性值的分割符）。
1232          * （2）我们在forEach（对性能最敏感的方法）结束时只执行一次ConcurrentModificationException检查。
1233          * 当使用forEach（而不是迭代器）时，我们通常只能在行为之后检测干扰，而不是之前。
1234          * 进一步的CME触发检查适用于所有其他可能的违反假设的情况，例如null或过小的elementData数组，因为它的大小（）只能由于干扰而发生。
1235          * 这允许forEach的内循环在没有任何进一步检查的情况下运行，并且简化了lambda分辨率。虽然这需要进行多次检查，但请注意，在list.stream（）。
1236          * forEach（a）的常见情况中，除forEach本身之外，不会执行任何检查或其他计算。其他较少使用的方法无法利用这些优化的大部分优势。
1237          */
1238 
1239         private final ArrayList<E> list;
1240         private int index; // current index, modified on advance/split
1241         private int fence; // -1 until used; then one past last index
1242         private int expectedModCount; // initialized when fence set
1243 
1244         /**
1245          * Create new spliterator covering the given  range
1246          */
1247         ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
1248                              int expectedModCount) {
1249             this.list = list; // OK if null unless traversed
1250             this.index = origin;
1251             this.fence = fence;
1252             this.expectedModCount = expectedModCount;
1253         }
1254 
1255         private int getFence() { // initialize fence to size on first use
1256             int hi; // (a specialized variant appears in method forEach)
1257             ArrayList<E> lst;
1258             if ((hi = fence) < 0) {
1259                 if ((lst = list) == null)
1260                     hi = fence = 0;
1261                 else {
1262                     expectedModCount = lst.modCount;
1263                     hi = fence = lst.size;
1264                 }
1265             }
1266             return hi;
1267         }
1268 
1269         public ArrayListSpliterator<E> trySplit() {
1270             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1271             return (lo >= mid) ? null : // divide range in half unless too small
1272                     new ArrayListSpliterator<E>(list, lo, index = mid,
1273                             expectedModCount);
1274         }
1275 
1276         public boolean tryAdvance(Consumer<? super E> action) {
1277             if (action == null)
1278                 throw new NullPointerException();
1279             int hi = getFence(), i = index;
1280             if (i < hi) {
1281                 index = i + 1;
1282                 @SuppressWarnings("unchecked") E e = (E) list.elementData[i];
1283                 action.accept(e);
1284                 if (list.modCount != expectedModCount)
1285                     throw new ConcurrentModificationException();
1286                 return true;
1287             }
1288             return false;
1289         }
1290 
1291         public void forEachRemaining(Consumer<? super E> action) {
1292             int i, hi, mc; // hoist accesses and checks from loop
1293             ArrayList<E> lst;
1294             Object[] a;
1295             if (action == null)
1296                 throw new NullPointerException();
1297             if ((lst = list) != null && (a = lst.elementData) != null) {
1298                 if ((hi = fence) < 0) {
1299                     mc = lst.modCount;
1300                     hi = lst.size;
1301                 } else
1302                     mc = expectedModCount;
1303                 if ((i = index) >= 0 && (index = hi) <= a.length) {
1304                     for (; i < hi; ++i) {
1305                         @SuppressWarnings("unchecked") E e = (E) a[i];
1306                         action.accept(e);
1307                     }
1308                     if (lst.modCount == mc)
1309                         return;
1310                 }
1311             }
1312             throw new ConcurrentModificationException();
1313         }
1314 
1315         public long estimateSize() {
1316             return (long) (getFence() - index);
1317         }
1318 
1319         public int characteristics() {
1320             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1321         }
1322     }
1323 
1324     @Override
1325     public boolean removeIf(Predicate<? super E> filter) {
1326         Objects.requireNonNull(filter);
1327         // figure out which elements are to be removed
1328         // any exception thrown from the filter predicate at this stage
1329         // will leave the collection unmodified
1330         int removeCount = 0;
1331         final BitSet removeSet = new BitSet(size);
1332         final int expectedModCount = modCount;
1333         final int size = this.size;
1334         for (int i = 0; modCount == expectedModCount && i < size; i++) {
1335             @SuppressWarnings("unchecked") final E element = (E) elementData[i];
1336             if (filter.test(element)) {
1337                 removeSet.set(i);
1338                 removeCount++;
1339             }
1340         }
1341         if (modCount != expectedModCount) {
1342             throw new ConcurrentModificationException();
1343         }
1344 
1345         // shift surviving elements left over the spaces left by removed elements
1346         final boolean anyToRemove = removeCount > 0;
1347         if (anyToRemove) {
1348             final int newSize = size - removeCount;
1349             for (int i = 0, j = 0; (i < size) && (j < newSize); i++, j++) {
1350                 i = removeSet.nextClearBit(i);
1351                 elementData[j] = elementData[i];
1352             }
1353             for (int k = newSize; k < size; k++) {
1354                 elementData[k] = null;  // Let gc do its work
1355             }
1356             this.size = newSize;
1357             if (modCount != expectedModCount) {
1358                 throw new ConcurrentModificationException();
1359             }
1360             modCount++;
1361         }
1362 
1363         return anyToRemove;
1364     }
1365 
1366     @Override
1367     @SuppressWarnings("unchecked")
1368     public void replaceAll(UnaryOperator<E> operator) {
1369         Objects.requireNonNull(operator);
1370         final int expectedModCount = modCount;
1371         final int size = this.size;
1372         for (int i = 0; modCount == expectedModCount && i < size; i++) {
1373             elementData[i] = operator.apply((E) elementData[i]);
1374         }
1375         if (modCount != expectedModCount) {
1376             throw new ConcurrentModificationException();
1377         }
1378         modCount++;
1379     }
1380 
1381     @Override
1382     @SuppressWarnings("unchecked")
1383     public void sort(Comparator<? super E> c) {
1384         final int expectedModCount = modCount;
1385         Arrays.sort((E[]) elementData, 0, size, c);
1386         if (modCount != expectedModCount) {
1387             throw new ConcurrentModificationException();
1388         }
1389         modCount++;
1390     }
1391 }