一点一点看JDK源码（三）java.util.ArrayList 前偏

   1 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
   2     /**
   3      * 序列化版本号
   4      */
   5     private static final long serialVersionUID = 8683452581122892189L;
   6     /**
   7      * 默认容量。
   8      */
   9     private static final int DEFAULT_CAPACITY = 10;
  10 
  11     /**
  12      * 以object数组做为类内共享实例容器。
  13      */
  14     private static final Object[] EMPTY_ELEMENTDATA = {};
  15 
  16     /**
  17      * 以object数组做为类内共享实例容器，使用默认容量实例化时使用。
  18      */
  19     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  20 
  21     /**
  22      * 以object数组做为容器缓自排序冲数组，注意没有private关键字，用于排序，当地一个元素添加的时候将转为默认容量
  23      */
  24     transient Object[] elementData; // non-private to simplify nested class access
  25 
  26     /**
  27      * 缓存的size大小，
  28      */
  29     private int size;
  30 
  31     /**
  32      * 带参构造，手动设置容器初始大小，若实例化时能肯定大小，最好别使用默认扩展容量，将提升运行效率
  33      */
  34     public ArrayList(int initialCapacity) {
  35         if (initialCapacity > 0) {
  36             this.elementData = new Object[initialCapacity]; //使用自排序缓冲数组
  37         } else if (initialCapacity == 0) {
  38             this.elementData = EMPTY_ELEMENTDATA; //使用默认数组
  39         } else {
  40             throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); //容量扩充参数异常
  41         }
  42     }
  43 
  44     /**
  45      * 无参构造，使用默认容器初始化大小
  46      */
  47     public ArrayList() {
  48         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  49     }
  50 
  51     /**
  52      * 带参构造器,将参数集合用数组工具类转成数组,并存入缓冲数组,对缓冲数组进行校验.
  53 * 若转换后的数组并不是object数组（内嵌套没法直接引用状况下），则使用数组工具类将该数组使用深度拷贝
  54      */
  55     public ArrayList(Collection<? extends E> c) {
  56         elementData = c.toArray();
  57         if ((size = elementData.length) != 0) {
  58             // c.toArray might (incorrectly) not return Object[] (see 6260652)
  59             if (elementData.getClass() != Object[].class)
  60                 elementData = Arrays.copyOf(elementData, size, Object[].class);
  61         } else {
  62             // replace with empty array.
  63             this.elementData = EMPTY_ELEMENTDATA;
  64         }
  65     }
  66 
  67     /**
  68      * 去除多余的数组申请空间，在内存紧张时会用到
  69      */
  70     public void trimToSize() {
  71         modCount++;//修改次数
  72         if (size < elementData.length) {
  73             elementData = (size == 0)
  74               ? EMPTY_ELEMENTDATA
  75               : Arrays.copyOf(elementData, size);
  76         }
  77     }
  78 
  79     /**
  80      * 对底层缓冲数组进行扩容的优化方法,若是已知该ArrayList容量,则可执行一次性扩容,
  81      * 不然将在数组add的过程当中进行动态扩容,效率较低
  82      */
  83     public void ensureCapacity(int minCapacity) {
  84         int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY;
  85         if (minCapacity > minExpand) {
  86             ensureExplicitCapacity(minCapacity);
  87         }
  88     }
  89     /**
  90      * 从新计算ArrayList的size,在使用构造和扩容时调用
  91      */
  92     private static int calculateCapacity(Object[] elementData, int minCapacity) {
  93         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  94             return Math.max(DEFAULT_CAPACITY, minCapacity);
  95         }
  96         return minCapacity;
  97     }
  98 
  99     /**
 100      * 被add调用,内部调用calculatecapacity,用于扩容
 101      */
 102     private void ensureCapacityInternal(int minCapacity) {
 103         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 104     }
 105 
 106     /**
 107      * 被ensureCapacity调用,内部调用calculatecapacity,用于扩容或优化
 108      */
 109     private void ensureExplicitCapacity(int minCapacity) {
 110         modCount++;
 111         // overflow-conscious code
 112         if (minCapacity - elementData.length > 0)
 113             grow(minCapacity);
 114     }
 115 
 116     /**
 117      * 目标分配数组的容器大小,最大值要小于Integer.MAX_VALUE-8
 118      */
 119     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 120 
 121     /**
 122      * 扩容
 123      */
 124     private void grow(int minCapacity) {
 125         int oldCapacity = elementData.length; //原容量
 126         int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量,扩容1.5倍,自查>>位运算
 127         if (newCapacity - minCapacity < 0) //容量不足,则扩容
 128             newCapacity = minCapacity;
 129         if (newCapacity - MAX_ARRAY_SIZE > 0) //扩容超支,使用最大容
 130             newCapacity = hugeCapacity(minCapacity);
 131         // minCapacity is usually close to size, so this is a win:
 132         elementData = Arrays.copyOf(elementData, newCapacity);
 133     }
 134 /**
 135      * 被grow方法调用,扩容为最大
 136      */
 137     private static int hugeCapacity(int minCapacity) {
 138         if (minCapacity < 0) //参数错误,抛出异常
 139             throw new OutOfMemoryError();
 140         return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; //返回最大容量
 141     }
 142 
 143     /**
 144      * 获取当前size
 145      */
 146     public int size() {
 147         return size;
 148     }
 149 
 150     /**
 151      * 判断当前是size是否为0,容器是否为空
 152      */
 153     public boolean isEmpty() {
 154         return size == 0;
 155     }
 156 
 157     /**
 158      * 判断是否包含元素o,返回该元素的index是否大于等于0的判断,是为包含,否为不包含
 159      */
 160     public boolean contains(Object o) {
 161         return indexOf(o) >= 0;
 162     }
 163 
 164     /**
 165      * 获取查询元素的index,若备查元素为null,则寻找空元素,返回index
 166      * 若备查元素不为null，则使用equal判断该元素是否存在，并返回index
 167      * 不存在则返回-1
 168      * 被contains调用
 169      */
 170     public int indexOf(Object o) {
 171         if (o == null) {
 172             for (int i = 0; i < size; i++)
 173                 if (elementData[i]==null)
 174                     return i;
 175         } else {
 176             for (int i = 0; i < size; i++)
 177                 if (o.equals(elementData[i]))
 178                     return i;
 179         }
 180         return -1;
 181     }
 182 
 183     /**
 184      * 倒叙查询第一个出现的被查元素
 185      */
 186     public int lastIndexOf(Object o) {
 187         if (o == null) {
 188             for (int i = size-1; i >= 0; i--)
 189                 if (elementData[i]==null)
 190                     return i;
 191         } else {
 192             for (int i = size-1; i >= 0; i--)
 193                 if (o.equals(elementData[i]))
 194                     return i;
 195         }
 196         return -1;
 197     }
 198 
 199     /**
 200      * clone本实例数组，返回类型为Object，使用根类意为可转换为其余格式容器
 201      */
 202     public Object clone() {
 203         try {
 204             ArrayList<?> v = (ArrayList<?>) super.clone();
 205             v.elementData = Arrays.copyOf(elementData, size);
 206             v.modCount = 0;
 207             return v;
 208         } catch (CloneNotSupportedException e) {
 209             throw new InternalError(e);
 210         }
 211     }
 212 
 213     /**
 214      * 将本实例转换为object数组，调用数组工具类拷贝
 215      */
 216     public Object[] toArray() {
 217         return Arrays.copyOf(elementData, size);
 218     }
 219 
 220     /**
 221      * 将本实例转换为指定类型数组，调用数组工具类拷贝，并得到泛型的Class
 222      */
 223     @SuppressWarnings("unchecked")
 224     public <T> T[] toArray(T[] a) {
 225         if (a.length < size)
 226             // Make a new array of a's runtime type, but my contents:
 227             return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 228         System.arraycopy(elementData, 0, a, 0, size);
 229         if (a.length > size)
 230             a[size] = null;
 231         return a;
 232     }
 233 
 234     /**
 235      * 获取指定index的元素，被get方法调用，get方法内进行check，util包内的类可调用
 236      */
 237     @SuppressWarnings("unchecked")
 238     E elementData(int index) {
 239         return (E) elementData[index];
 240     }
 241 
 242     /**
 243      * 获取指定元素的方法，使用rangeCheck进行index的check
 244      */
 245     public E get(int index) {
 246         rangeCheck(index);
 247         return elementData(index);
 248     }
 249 
 250     /**
 251      * 将指定index的值设置为指定值，使用rangeCheck进行index的check
 252      */
 253     public E set(int index, E element) {
 254         rangeCheck(index);
 255         E oldValue = elementData(index);
 256         elementData[index] = element;
 257         return oldValue;
 258     }
 259 
 260     /**
 261      * 容量+1的，在容器尾部添加元素
 262      */
 263     public boolean add(E e) {
 264         ensureCapacityInternal(size + 1);  // Increments modCount!!
 265         elementData[size++] = e; // 这个在数组尾部追加元素的写法很好用,前提是扩容
 266         return true; // 有返回值的,应当接收
 267     }
 268 
 269     /**
 270      * 在指定index添加指定元素,首先使用rangeCheckForAdd进行check,为保证数组操做的正确性,使用arraycopy来移动数组元素
 271      */
 272     public void add(int index, E element) {
 273         rangeCheckForAdd(index);
 274         ensureCapacityInternal(size + 1);  // Increments modCount!!
 275         System.arraycopy(elementData, index, elementData, index + 1, size - index);
 276         elementData[index] = element;
 277         size++;
 278     }
 279 
 280     /**
 281      * remove指定index的元素,并重构本实例
 282      */
 283     public E remove(int index) {
 284         rangeCheck(index);
 285         modCount++;
 286         E oldValue = elementData(index);
 287         int numMoved = size - index - 1;
 288         if (numMoved > 0)
 289             System.arraycopy(elementData, index+1, elementData, index, numMoved);
 290         elementData[--size] = null; // clear to let GC do its work
 291         return oldValue;
 292     }
 293 
 294     /**
 295      * remove指定元素,返回是否找到该元素并移除成功的boolean标记
 296      */
 297     public boolean remove(Object o) {
 298         if (o == null) {
 299             for (int index = 0; index < size; index++)
 300                 if (elementData[index] == null) {
 301                     fastRemove(index);
 302                     return true;
 303                 }
 304         } else {
 305             for (int index = 0; index < size; index++)
 306                 if (o.equals(elementData[index])) {
 307                     fastRemove(index);
 308                     return true;
 309                 }
 310         }
 311         return false;
 312     }
 313 
 314     /*
 315      * 内部使用,快速移除指定index的元素
 316      */
 317     private void fastRemove(int index) {
 318         modCount++;
 319         int numMoved = size - index - 1;
 320         if (numMoved > 0)
 321             System.arraycopy(elementData, index+1, elementData, index,
 322                              numMoved);
 323         elementData[--size] = null; // clear to let GC do its work
 324     }
 325 
 326     /**
 327      * 清除本实例内部的全部元素,加速gc回收
 328      */
 329     public void clear() {
 330         modCount++;
 331         // clear to let GC do its work
 332         for (int i = 0; i < size; i++)
 333             elementData[i] = null;
 334         size = 0;
 335     }
 336 
 337     /**
 338      * 添加指定集合到本实例中Object数组末尾
 339      */
 340     public boolean addAll(Collection<? extends E> c) {
 341         Object[] a = c.toArray();
 342         int numNew = a.length;
 343         ensureCapacityInternal(size + numNew);  // Increments modCount
 344         System.arraycopy(a, 0, elementData, size, numNew);
 345         size += numNew;
 346         return numNew != 0;
 347     }
 348 
 349     /**
 350      * 从指定元素开始添加指定集合到本实例
 351      */
 352     public boolean addAll(int index, Collection<? extends E> c) {
 353         rangeCheckForAdd(index);
 354         Object[] a = c.toArray();
 355         int numNew = a.length;
 356         ensureCapacityInternal(size + numNew);  // Increments modCount
 357         int numMoved = size - index;
 358         if (numMoved > 0)
 359             System.arraycopy(elementData, index, elementData, index + numNew,
 360                              numMoved);
 361         System.arraycopy(a, 0, elementData, index, numNew);
 362         size += numNew;
 363         return numNew != 0;
 364     }
 365 
 366     /**
 367      * 本类和子类可以使用,移除指定范围的index的全部元素
 368      */
 369     protected void removeRange(int fromIndex, int toIndex) {
 370         modCount++;
 371         int numMoved = size - toIndex;
 372         System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
 373         int newSize = size - (toIndex-fromIndex);
 374         for (int i = newSize; i < size; i++) {
 375             elementData[i] = null;
 376         }
 377         size = newSize;
 378     }
 379 
 380     /**
 381      * 内部的index超限检测方法,当index超过size的时候,抛出index超限异常,在本类中被屡次调用
 382      */
 383     private void rangeCheck(int index) {
 384         if (index >= size)
 385             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 386     }
 387 
 388     /**
 389      * 同上,可是在add和addAll中专用
 390      */
 391     private void rangeCheckForAdd(int index) {
 392         if (index > size || index < 0)
 393             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 394     }
 395 
 396     /**
 397      * index超限抛异常时使用,用来提示size和index的值
 398      */
 399     private String outOfBoundsMsg(int index) {
 400         return "Index: "+index+", Size: "+size;
 401     }
 402 
 403     /**
 404      * 从本类实例中移除指定集合中全部元素的方法,返回值应接收
 405      */
 406     public boolean removeAll(Collection<?> c) {
 407         Objects.requireNonNull(c);
 408         return batchRemove(c, false);
 409     }
 410 
 411     /**
 412      * 从本类实例中保留指定集合中全部元素的方法,与removeAll相反
 413      */
 414     public boolean retainAll(Collection<?> c) {
 415         Objects.requireNonNull(c);
 416         return batchRemove(c, true);
 417     }
 418 
 419     /**
 420      * 内部调用,若是参数集合发生更改,则返回true
 421      */
 422     private boolean batchRemove(Collection<?> c, boolean complement) {
 423         final Object[] elementData = this.elementData; //获取本实例的全部元素
 424         int r = 0, w = 0; //r用于遍历,w用于记录相同元素的数量,也用于记录容器的扩容标记
 425         boolean modified = false; //标志位
 426         try {
 427             for (; r < size; r++)
 428                 if (c.contains(elementData[r]) == complement) //判断该元素是否被包含
 429                     elementData[w++] = elementData[r]; //包含则w++
 430         } finally {
 431             // Preserve behavioral compatibility with AbstractCollection,
 432             // even if c.contains() throws.
 433             if (r != size) {//集合有变化
 434                 System.arraycopy(elementData, r, elementData, w, size - r);
 435                 w += size - r;
 436             }
 437             if (w != size) {//容量不相等
 438                 // clear to let GC do its work
 439                 for (int i = w; i < size; i++)
 440                     elementData[i] = null;
 441                 modCount += size - w;
 442                 size = w;
 443                 modified = true; //容量有变化,说明有交集,则返回true
 444             }
 445         }
 446         return modified;
 447     }
 448 
 449     /**
 450      * 将本实例对象写入流中,实际上只写入了modCount,size和element[i],其他的内容在实例化时候是没必要要的,或者可恢复的
 451      */
 452     private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
 453         // Write out element count, and any hidden stuff
 454         int expectedModCount = modCount;
 455         s.defaultWriteObject();
 456         // Write out size as capacity for behavioural compatibility with clone()
 457         s.writeInt(size);
 458         // Write out all elements in the proper order.
 459         for (int i=0; i<size; i++) {
 460             s.writeObject(elementData[i]);
 461         }
 462         if (modCount != expectedModCount) {
 463             throw new ConcurrentModificationException();
 464         }
 465     }
 466 
 467     /**
 468      * 从流中读取本实例对象
 469      */
 470     private void readObject(java.io.ObjectInputStream s)
 471         throws java.io.IOException, ClassNotFoundException {
 472         elementData = EMPTY_ELEMENTDATA
 473         // Read in size, and any hidden stuff
 474         s.defaultReadObject();
 475         // Read in capacity
 476         s.readInt(); // ignored
 477         if (size > 0) {
 478             // be like clone(), allocate array based upon size not capacity
 479             int capacity = calculateCapacity(elementData, size);
 480             SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
 481             ensureCapacityInternal(size);
 482             Object[] a = elementData;
 483             // Read in all elements in the proper order.
 484             for (int i=0; i<size; i++) {
 485                 a[i] = s.readObject();
 486             }
 487         }
 488     }
 489 
 490     /**
 491      * 得到指定长度额本实例的List迭代器
 492      */
 493     public ListIterator<E> listIterator(int index) {
 494         if (index < 0 || index > size)
 495             throw new IndexOutOfBoundsException("Index: "+index);
 496         return new ListItr(index);
 497     }
 498 
 499     /**
 500      * 得到本实例的默认List迭代器
 501      */
 502     public ListIterator<E> listIterator() {
 503         return new ListItr(0);
 504     }
 505 
 506     /**
 507      * 得到本实例的默认迭代器
 508      */
 509     public Iterator<E> iterator() {
 510         return new Itr();
 511     }
 512 
 513     /**
 514      * 内部使用的迭代器,重写自Iterator接口,为内部类
 515      */
 516     private class Itr implements Iterator<E> {
 517         int cursor;       // index of next element to return    迭代器指针
 518         int lastRet = -1; // index of last element returned; -1 if no such    末尾标记
 519         int expectedModCount = modCount;
 520         Itr() {}
 521         public boolean hasNext() {
 522             return cursor != size;
 523         }
 524         @SuppressWarnings("unchecked")
 525       //重写迭代器提供next方法,可能unchecked报错
 526         public E next() {
 527             checkForComodification();
 528             int i = cursor;
 529             if (i >= size)
 530                 throw new NoSuchElementException();
 531             Object[] elementData = ArrayList.this.elementData;
 532             if (i >= elementData.length)
 533                 throw new ConcurrentModificationException();
 534             cursor = i + 1;
 535             return (E) elementData[lastRet = i];
 536         }
 537       //重写迭代器提供remove方法
 538         public void remove() {
 539             if (lastRet < 0)
 540                 throw new IllegalStateException();
 541             checkForComodification();
 542             try {
 543                 ArrayList.this.remove(lastRet);
 544                 cursor = lastRet;
 545                 lastRet = -1;
 546                 expectedModCount = modCount;
 547             } catch (IndexOutOfBoundsException ex) {
 548                 throw new ConcurrentModificationException();
 549             }
 550         }
 551 
 552         @Override
 553         @SuppressWarnings("unchecked")//重写迭代器接口下的forEachRemaining方法,可能unchecked报错,可以使用lambda迭代
 554         public void forEachRemaining(Consumer<? super E> consumer) {
 555             Objects.requireNonNull(consumer);
 556             final int size = ArrayList.this.size;
 557             int i = cursor;
 558             if (i >= size) {
 559                 return;
 560             }
 561             final Object[] elementData = ArrayList.this.elementData;
 562             if (i >= elementData.length) {
 563                 throw new ConcurrentModificationException();
 564             }
 565             while (i != size && modCount == expectedModCount) {
 566                 consumer.accept((E) elementData[i++]);
 567             }
 568             // update once at end of iteration to reduce heap write traffic
 569             cursor = i;
 570             lastRet = i - 1;
 571             checkForComodification();
 572         }
 573       //校验modCount修改次数的方法
 574         final void checkForComodification() {
 575             if (modCount != expectedModCount)
 576                 throw new ConcurrentModificationException();
 577         }
 578     }
 579 
 580     /**
 581      * 另外一个内部提供ListItr的迭代器,继承自上述内部类,实现ListIteraotr接口,本内部类将容许使用固定长度的迭代器
 582      */
 583     private class ListItr extends Itr implements ListIterator<E> {
 584         ListItr(int index) {
 585             super();
 586             cursor = index;
 587         }
 588       //是否有前一个元素
 589         public boolean hasPrevious() {
 590             return cursor != 0;
 591         }
 592       //获取下一个index
 593         public int nextIndex() {
 594             return cursor;
 595         }
 596       //获取前一个index
 597         public int previousIndex() {
 598             return cursor - 1;
 599         }
 600       //获取前一个元素,可能由于unchecked报错
 601         @SuppressWarnings("unchecked")
 602         public E previous() {
 603             checkForComodification();
 604             int i = cursor - 1;
 605             if (i < 0)
 606                 throw new NoSuchElementException();
 607             Object[] elementData = ArrayList.this.elementData;
 608             if (i >= elementData.length)
 609                 throw new ConcurrentModificationException();
 610             cursor = i;
 611             return (E) elementData[lastRet = i];
 612         }
 613       //对迭代器内当index的元素设置为指定值
 614         public void set(E e) {
 615             if (lastRet < 0)
 616                 throw new IllegalStateException();
 617             checkForComodification();
 618             try {
 619                 ArrayList.this.set(lastRet, e);
 620             } catch (IndexOutOfBoundsException ex) {
 621                 throw new ConcurrentModificationException();
 622             }
 623         }
 624 
 625         public void add(E e) {
 626             checkForComodification();
 627 
 628             try {
 629                 int i = cursor;
 630                 ArrayList.this.add(i, e);
 631                 cursor = i + 1;
 632                 lastRet = -1;
 633                 expectedModCount = modCount;
 634             } catch (IndexOutOfBoundsException ex) {
 635                 throw new ConcurrentModificationException();
 636             }
 637         }
 638     }
 639 
 640     /**
 641      * 从fromIndex到toIndex拆分数组，内部调用subListRangeCheck方法对本实例进行check
 642      */
 643     public List<E> subList(int fromIndex, int toIndex) {
 644         subListRangeCheck(fromIndex, toIndex, size);
 645         return new SubList(this, 0, fromIndex, toIndex); //调用复写的内部类,十分巨大
 646     }
 647 /**
 648      * 被内部调用，进行拆分时的参数check校验
 649      */
 650     static void subListRangeCheck(int fromIndex, int toIndex, int size) {
 651         if (fromIndex < 0)
 652             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 653         if (toIndex > size)
 654             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 655         if (fromIndex > toIndex)
 656             throw new IllegalArgumentException("fromIndex(" + fromIndex +") > toIndex(" + toIndex + ")");
 657     }
 658 
 659 /**
 660      * 重写继承的AbstractList中的SubList类,对于该类提供和list基本相同的功能进行从新封装
 661      */
 662     private class SubList extends AbstractList<E> implements RandomAccess {
 663         private final AbstractList<E> parent;
 664         private final int parentOffset;
 665         private final int offset;
 666         int size;
 667       //构造
 668         SubList(AbstractList<E> parent,
 669                 int offset, int fromIndex, int toIndex) {
 670             this.parent = parent;
 671             this.parentOffset = fromIndex;
 672             this.offset = offset + fromIndex;
 673             this.size = toIndex - fromIndex;
 674             this.modCount = ArrayList.this.modCount;
 675         }
 676       //内部类的set方法
 677         public E set(int index, E e) {
 678             rangeCheck(index);
 679             checkForComodification();
 680             E oldValue = ArrayList.this.elementData(offset + index);
 681             ArrayList.this.elementData[offset + index] = e;
 682             return oldValue;
 683         }
 684       //内部类的get方法
 685         public E get(int index) {
 686             rangeCheck(index);
 687             checkForComodification();
 688             return ArrayList.this.elementData(offset + index);
 689         }
 690        //内部类的size方法
 691         public int size() {
 692             checkForComodification();//复用
 693             return this.size;
 694         }
 695       //内部类的add方法
 696         public void add(int index, E e) {
 697             rangeCheckForAdd(index); //复用
 698             checkForComodification();//复用
 699             parent.add(parentOffset + index, e);
 700             this.modCount = parent.modCount;
 701             this.size++;
 702         }
 703       //内部类的remove方法
 704         public E remove(int index) {
 705             rangeCheck(index); //复用
 706             checkForComodification();//复用
 707             E result = parent.remove(parentOffset + index);
 708             this.modCount = parent.modCount;
 709             this.size--;
 710             return result;
 711         }
 712       //从本内部类实例中移除指定范围的元素并重构本实例
 713         protected void removeRange(int fromIndex, int toIndex) {
 714             checkForComodification();//复用
 715             parent.removeRange(parentOffset + fromIndex,
 716                                parentOffset + toIndex); //使用父类
 717             this.modCount = parent.modCount;
 718             this.size -= toIndex - fromIndex;
 719         }
 720       //内部类的addAll
 721         public boolean addAll(Collection<? extends E> c) {
 722             return addAll(this.size, c);
 723         }
 724       //内部类的addAll,从指定index开始
 725         public boolean addAll(int index, Collection<? extends E> c) {
 726             rangeCheckForAdd(index); //复用
 727             int cSize = c.size();
 728             if (cSize==0)
 729                 return false;
 730             checkForComodification();//复用
 731             parent.addAll(parentOffset + index, c);
 732             this.modCount = parent.modCount;
 733             this.size += cSize;
 734             return true;
 735         }
 736       //内部类的迭代器
 737         public Iterator<E> iterator() {
 738             return listIterator();
 739         }
 740       //内部类的迭代器,被内部调用
 741         public ListIterator<E> listIterator(final int index) {
 742             checkForComodification();//复用
 743             rangeCheckForAdd(index); //复用
 744             final int offset = this.offset;
 745             return new ListIterator<E>() {
 746                 int cursor = index;
 747                 int lastRet = -1;
 748                 int expectedModCount = ArrayList.this.modCount;
 749                 public boolean hasNext() {
 750                     return cursor != SubList.this.size;
 751                 }
 752             //内部类的迭代器的next
 753                 @SuppressWarnings("unchecked")
 754                 public E next() {
 755                     checkForComodification();
 756                     int i = cursor;
 757                     if (i >= SubList.this.size)
 758                         throw new NoSuchElementException();
 759                     Object[] elementData = ArrayList.this.elementData;
 760                     if (offset + i >= elementData.length)
 761                         throw new ConcurrentModificationException();
 762                     cursor = i + 1;
 763                     return (E) elementData[offset + (lastRet = i)];
 764                 }
 765             //内部类的迭代器的判断是否有前一个元素
 766                 public boolean hasPrevious() {
 767                     return cursor != 0;
 768                 }
 769             //内部类的获取前一个元素
 770                 @SuppressWarnings("unchecked")
 771                 public E previous() {
 772                     checkForComodification();
 773                     int i = cursor - 1;
 774                     if (i < 0)
 775                         throw new NoSuchElementException();
 776                     Object[] elementData = ArrayList.this.elementData;
 777                     if (offset + i >= elementData.length)
 778                         throw new ConcurrentModificationException();
 779                     cursor = i;
 780                     return (E) elementData[offset + (lastRet = i)];
 781                 }
 782             //剩余元素的迭代,可使用lambda表达式进行遍历
 783                 @SuppressWarnings("unchecked")
 784                 public void forEachRemaining(Consumer<? super E> consumer) {
 785                     Objects.requireNonNull(consumer);
 786                     final int size = SubList.this.size;
 787                     int i = cursor;
 788                     if (i >= size) {
 789                         return;
 790                     }
 791                     final Object[] elementData = ArrayList.this.elementData;
 792                     if (offset + i >= elementData.length) {
 793                         throw new ConcurrentModificationException();
 794                     }
 795                     while (i != size && modCount == expectedModCount) {
 796                         consumer.accept((E) elementData[offset + (i++)]);
 797                     }
 798                     // update once at end of iteration to reduce heap write traffic
 799                     lastRet = cursor = i;
 800                     checkForComodification();
 801                 }
 802             //内部类的迭代器中获取下一个元素的index
 803                 public int nextIndex() {
 804                     return cursor;
 805                 }
 806             //内部类的迭代器中获取上一个元素的index
 807                 public int previousIndex() {
 808                     return cursor - 1;
 809                 }
 810             //内部类的迭代器中移除当前元素
 811                 public void remove() {
 812                     if (lastRet < 0)
 813                         throw new IllegalStateException();
 814                     checkForComodification();
 815                     try {
 816                         SubList.this.remove(lastRet);
 817                         cursor = lastRet;
 818                         lastRet = -1;
 819                         expectedModCount = ArrayList.this.modCount;
 820                     } catch (IndexOutOfBoundsException ex) {
 821                         throw new ConcurrentModificationException();
 822                     }
 823                 }
 824             //内部类的迭代器对当前元素设置成指定值
 825                 public void set(E e) {
 826                     if (lastRet < 0)
 827                         throw new IllegalStateException();
 828                     checkForComodification();
 829                     try {
 830                         ArrayList.this.set(offset + lastRet, e);
 831                     } catch (IndexOutOfBoundsException ex) {
 832                         throw new ConcurrentModificationException();
 833                     }
 834                 }
 835             //内部类的迭代器中add方法添加元素到迭代器末尾
 836                 public void add(E e) {
 837                     checkForComodification();
 838                     try {
 839                         int i = cursor;
 840                         SubList.this.add(i, e);
 841                         cursor = i + 1;
 842                         lastRet = -1;
 843                         expectedModCount = ArrayList.this.modCount;
 844                     } catch (IndexOutOfBoundsException ex) {
 845                         throw new ConcurrentModificationException();
 846                     }
 847                 }
 848             //内部类的modCount校验
 849                 final void checkForComodification() {
 850                     if (expectedModCount != ArrayList.this.modCount)
 851                         throw new ConcurrentModificationException();
 852                 }
 853             };
 854         }
 855       
 856 /**
 857          * 内部类的拆分list的方法
 858          */
 859         public List<E> subList(int fromIndex, int toIndex) {
 860             subListRangeCheck(fromIndex, toIndex, size);
 861             return new SubList(this, offset, fromIndex, toIndex);
 862         }
 863       /**
 864             * 内部类的index越界检查方法
 865          */
 866         private void rangeCheck(int index) {
 867             if (index < 0 || index >= this.size)
 868                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 869         }
 870       /**
 871             * 同上,add和addAll专用
 872          */
 873         private void rangeCheckForAdd(int index) {
 874             if (index < 0 || index > this.size)
 875                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 876         }
 877       /**
 878             * 内部类rangeCheckForAdd中抛异常调用,写明index和size
 879          */
 880         private String outOfBoundsMsg(int index) {
 881             return "Index: "+index+", Size: "+this.size;
 882         }
 883       /**
 884             * 内部类的modCount校验
 885          */
 886         private void checkForComodification() {
 887             if (ArrayList.this.modCount != this.modCount)
 888                 throw new ConcurrentModificationException();
 889         }
 890       /**
 891             * 内部类的分离迭代器函数,调用ArrayList的ArrayListSpliterator内部类的构造器
 892          */
 893         public Spliterator<E> spliterator() {
 894             checkForComodification();
 895             return new ArrayListSpliterator<E>(ArrayList.this, offset, offset + this.size, this.modCount);
 896         }
 897     }
 898 
 899 /**
 900      * 重写继承的forEach方法,用于迭代
 901      */
 902     @Override
 903     public void forEach(Consumer<? super E> action) {
 904         Objects.requireNonNull(action);
 905         final int expectedModCount = modCount;
 906         @SuppressWarnings("unchecked")
 907         final E[] elementData = (E[]) this.elementData;
 908         final int size = this.size;
 909         for (int i=0; modCount == expectedModCount && i < size; i++) {
 910             action.accept(elementData[i]);
 911         }
 912         if (modCount != expectedModCount) {
 913             throw new ConcurrentModificationException();
 914         }
 915     }
 916 
 917     /**
 918      * jd1.8更新
 919      * 重写自父类,分离数组,默认使用本类内容,从0-末尾,
 920      */
 921     @Override
 922     public Spliterator<E> spliterator() {
 923         return new ArrayListSpliterator<>(this, 0, -1, 0);
 924     }
 925 
 926     /**
 927      * jd1.8更新
 928      * 重写自父类,实现Spliterator接口
 929      * 本类用于分离ArrayList,前提是ArrayList暂定是不变的,不然将可能出现线程错误
 930      */
 931     static final class ArrayListSpliterator<E> implements Spliterator<E> {
 932 
 933         private final ArrayList<E> list;
 934         private int index; // current index, modified on advance/split
 935         private int fence; // -1 until used; then one past last index
 936         private int expectedModCount; // initialized when fence set
 937 
 938        /**
 939          * 内部类ArrayListSpliterator的构造器
 940          */
 941         ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
 942                              int expectedModCount) {
 943             this.list = list; // OK if null unless traversed
 944             this.index = origin;
 945             this.fence = fence;
 946             this.expectedModCount = expectedModCount;
 947         }
 948        /**
 949          * 内部类ArrayListSpliterator中不少方法都使用的初始化方法
 950          */
 951         private int getFence() { // initialize fence to size on first use
 952             int hi; // (a specialized variant appears in method forEach)
 953             ArrayList<E> lst;
 954             if ((hi = fence) < 0) {
 955                 if ((lst = list) == null)
 956                     hi = fence = 0;
 957                 else {
 958                     expectedModCount = lst.modCount;
 959                     hi = fence = lst.size;
 960                 }
 961             }
 962             return hi;
 963         }
 964        /**
 965          * 内部类ArrayListSpliterator的拆分arraylist方法,不保证结果正确
 966          */
 967         public ArrayListSpliterator<E> trySplit() {
 968             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
 969             return (lo >= mid) ? null : // divide range in half unless too small
 970                 new ArrayListSpliterator<E>(list, lo, index = mid, expectedModCount);
 971         }
 972 
 973        /**
 974          * 内部类ArrayListSpliterator的预拆分?尝试是否可以拆分
 975          */
 976         public boolean tryAdvance(Consumer<? super E> action) {
 977             if (action == null)
 978                 throw new NullPointerException();
 979             int hi = getFence(), i = index;
 980             if (i < hi) {
 981                 index = i + 1;
 982                 @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
 983                 action.accept(e);
 984                 if (list.modCount != expectedModCount)
 985                     throw new ConcurrentModificationException();
 986                 return true;
 987             }
 988             return false;
 989         }
 990 
 991        /**
 992          * 内部类ArrayListSpliterator迭代
 993          */
 994         public void forEachRemaining(Consumer<? super E> action) {
 995             int i, hi, mc; // hoist accesses and checks from loop
 996             ArrayList<E> lst; Object[] a;
 997             if (action == null)
 998                 throw new NullPointerException();
 999             if ((lst = list) != null && (a = lst.elementData) != null) {
1000                 if ((hi = fence) < 0) {
1001                     mc = lst.modCount;
1002                     hi = lst.size;
1003                 }
1004                 else
1005                     mc = expectedModCount;
1006                 if ((i = index) >= 0 && (index = hi) <= a.length) {
1007                     for (; i < hi; ++i) {
1008                         @SuppressWarnings("unchecked") E e = (E) a[i];
1009                         action.accept(e);
1010                     }
1011                     if (lst.modCount == mc)
1012                         return;
1013                 }
1014             }
1015             throw new ConcurrentModificationException();
1016         }
1017       //内部类ArrayListSpliterator的size预估
1018         public long estimateSize() {
1019             return (long) (getFence() - index);
1020         }
1021 
1022       //分离参数初始化
1023         public int characteristics() {
1024             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1025         }
1026     }
1027 
1028     /**
1029      * 重写自父类,使用重写的filter接口进行筛选,符合条件的则移除
1030      */
1031     @Override
1032     public boolean removeIf(Predicate<? super E> filter) {
1033         Objects.requireNonNull(filter);
1034         // figure out which elements are to be removed
1035         // any exception thrown from the filter predicate at this stage
1036         // will leave the collection unmodified
1037         int removeCount = 0;
1038         final BitSet removeSet = new BitSet(size);
1039         final int expectedModCount = modCount;
1040         final int size = this.size;
1041         for (int i=0; modCount == expectedModCount && i < size; i++) {
1042             @SuppressWarnings("unchecked")
1043             final E element = (E) elementData[i];
1044             if (filter.test(element)) {
1045                 removeSet.set(i);
1046                 removeCount++;
1047             }
1048         }
1049         if (modCount != expectedModCount) {
1050             throw new ConcurrentModificationException();
1051         }
1052 
1053         // shift surviving elements left over the spaces left by removed elements
1054         final boolean anyToRemove = removeCount > 0;
1055         if (anyToRemove) {
1056             final int newSize = size - removeCount;
1057             for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
1058                 i = removeSet.nextClearBit(i);
1059                 elementData[j] = elementData[i];
1060             }
1061             for (int k=newSize; k < size; k++) {
1062                 elementData[k] = null;  // Let gc do its work
1063             }
1064             this.size = newSize;
1065             if (modCount != expectedModCount) {
1066                 throw new ConcurrentModificationException();
1067             }
1068             modCount++;
1069         }
1070         return anyToRemove;
1071     }
1072 
1073    /**
1074      * 重写自父类,使用重写的operator接口进行替代本实例中匹配的元素
1075      */
1076     @Override
1077     @SuppressWarnings("unchecked")
1078     public void replaceAll(UnaryOperator<E> operator) {
1079         Objects.requireNonNull(operator);
1080         final int expectedModCount = modCount;
1081         final int size = this.size;
1082         for (int i=0; modCount == expectedModCount && i < size; i++) {
1083             elementData[i] = operator.apply((E) elementData[i]);
1084         }
1085         if (modCount != expectedModCount) {
1086             throw new ConcurrentModificationException();
1087         }
1088         modCount++;
1089     }
1090 
1091    /**
1092      * 重写自父类,使用comparator接口对本实例进行排序
1093      */
1094     @Override
1095     @SuppressWarnings("unchecked")
1096     public void sort(Comparator<? super E> c) {
1097         final int expectedModCount = modCount;
1098         Arrays.sort((E[]) elementData, 0, size, c);
1099         if (modCount != expectedModCount) {
1100             throw new ConcurrentModificationException();
1101         }
1102         modCount++;
1103     }
1104 }