Java集合ArrayList

   /**
   * 序列化版本标识，序列化和反序列化时使用
   */
private static final long serialVersionUID = 8683452581122892189L;

   /**
    * 默认初始容量.
    */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * 用于 ArrayList 空实例的共享空数组实例.
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

   /**
    * 用于默认大小空实例的共享空数组实例.
    * 我们将其与 EMPTY_ELEMENTDATA 区分开来, 以了解添加第一个元素时应该膨胀多少
    */
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   /**
    * 存储 ArrayList 元素的数组缓冲区. 
    * ArrayList 的容量是此数组的长度.
    * 当添加第一个元素时, 任何 emementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将被扩展为 DEFAULT_CAPACITY.
    */
   transient Object[] elementData; // non-private to simplify nested class access

   /**
    * ArrayList 的大小.
    */
   private int size;

/**
 * 构造具有指定初始容量的空列表。
 *
 * @param  initialCapacity  列表的初始容量
 * @throws 如果容量为负数, 抛出 IllegalArgumentException
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 指定大小大于0 创建指定大小的列表
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 指定大小为 0, 指向同一个空列表, 可以减少内存的使用
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 指定大小小于 0, 抛出 IllegalArgumentException 异常.
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * 无参构造
 * 创建一个大小为 10 的列表.
 */
public ArrayList() {
    // 当添加第一个元素时, 任何指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将被扩展为容量为 DEFAULT_CAPACITY(10)的列表.
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 按照集合迭代器返回元素的顺序, 构造一个包含指定集合元素的列表.
 *
 * @param c 要将其元素放入此列表的集合.
 * @throws 如果参数为null, 抛出 NullPointerException
 */
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // 指向空数组.
        elementData = EMPTY_ELEMENTDATA;
    }
}

  /**
   * 将指定的元素追加到此列表的末尾。
   *
   * @param e 要添加的元素
   * @return true (由 Collection.add 指定)
   */
  public boolean add(E e) {
      // 检查是否需要扩容
      ensureCapacityInternal(size + 1);
      elementData[size++] = e;
      return true;
  }


  /**
   * 在列表的指定位置插入一个元素, 该位置之后的元素后移一位.
   *
   * @param index 要插入的位置的索引
   * @param element 插入的元素
   * @throws 索引超出边界,抛出 IndexOutOfBoundsException
   */
  public void add(int index, E element) {
      // 判断索引是否超出界限, 超出抛出 IndexOutOfBoundsException 异常.
      rangeCheckForAdd(index);

      ensureCapacityInternal(size + 1); 
      System.arraycopy(elementData, index, elementData, index + 1, size - index);
      elementData[index] = element;
      size++;
  }

  private static int calculateCapacity(Object[] elementData, int minCapacity) {
      // 如果是用空参数创建的列表, 第一次添加数据时将其扩展为容量最小为 DEFAULT_CAPACITY(10) 的列表.
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          return Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      return minCapacity;
  }

  private void ensureCapacityInternal(int minCapacity) {
      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  }


  private void ensureExplicitCapacity(int minCapacity) {
      // 用于记录列表被修改的次数.
      // 用来限制用户在迭代时修改列表, 造成数据错乱.
      modCount++;

      // 扩容, 可能溢出
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }


  /**
   * 列表的最大容量.
   * 有些虚拟机在数组中保存 header word 头部字, 用于存储数组的容量, 占八位.因此,列表的最大容量为 Integer.MAX_VALUE - 8
   */
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  /**
   * 扩容, 确保至少可以容纳 minCapacity 个元素
   *
   * @param minCapacity 所需最小容量
   */
  private void grow(int minCapacity) {
      // 存在整数溢出的可能
      int oldCapacity = elementData.length;
      // 扩大 1.5 倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity < 0)
          // 可能整数溢出
          // 可能 newCapacity < minCapacity
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
// 通过 System.arraycopy 方法将原数组拷贝到容量为 newCapacity 的新数组中
      elementData = Arrays.copyOf(elementData, newCapacity);
  }

  private static int hugeCapacity(int minCapacity) {
      if (minCapacity < 0) // overflow
          throw new OutOfMemoryError();
      return (minCapacity > MAX_ARRAY_SIZE) ?
          Integer.MAX_VALUE :
          MAX_ARRAY_SIZE;
  }

/**
 * 将指定集合中的所有元素按指定集合的迭代器返回的顺序追加到此列表的末尾
 * 添加过程中的元素有发生改变的可能.
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew); 
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

/**
 * 从指定位置开始, 将指定集合中的元素插入此列表. 该位置及其之后的元素后移.
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 判断索引是否超出界限, 超出抛出 IndexOutOfBoundsException 异常.
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew); 

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}


/**
 * 判断索引是否超出界限.
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

  /**
   * 删除指定位置的元素.
   * 其后元素前移.
   *
   * @param index 要删除元素的索引
   * @return 被删除的元素
   * @throws 超出边界,抛出 IndexOutOfBoundsException 
   */
  public E remove(int index) {
      // 判断索引是否超界
      rangeCheck(index);
// 列表修改次数加一
      modCount++;
      E oldValue = elementData(index);

      int numMoved = size - index - 1;
      if (numMoved > 0)
           // 将elemenData中index+1及其后面的元素都向前移动一个下标
          System.arraycopy(elementData, index+1, elementData, index,
                           numMoved);
      // 根据上一步的操作, size-1位置的对象向前移动了一个下标
      // 如果没有elementData[--size]==null, 可能会导致内存泄漏, 若没有这一步操作, 该内存一直指向之前的元素, GC 不会认为它是垃圾, 故无法回收内存造成内存泄漏.
      elementData[--size] = null;

      return oldValue;
  }


  /**
   * 检查索引是否在范围内.
   * 和 添加元素 时的检查函数的区别为: 此函数不检查索引是否为负数, 并且索引不能为 size. 因为在执行此方法之前数组会检查索引, 如果为负数会抛出 ArrayIndexOutOfBoundsException.
   */
  private void rangeCheck(int index) {
      if (index >= size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

  /**
   * 从列表中删除指定元素的第一个匹配, 如果列表中没有此元素, 则保持列表不变
   * null 也被当作一个元素
   * @param o 指定删除的元素
   * @return true 如果删除了指定元素
   */
  public boolean remove(Object o) {
      if (o == null) {
          for (int index = 0; index < size; index++)
              if (elementData[index] == null) {
                  // 删除该位置元素, 其后元素前移
                  fastRemove(index);
                  return true;
              }
      } else {
          for (int index = 0; index < size; index++)
              if (o.equals(elementData[index])) {
                  // 删除该位置元素, 其后元素前移
                  fastRemove(index);
                  return true;
              }
      }
      return false;
  }

  /*
   * 删除当前位置的元素, 其后元素前移
   */
  private void fastRemove(int index) {
      modCount++;
      int numMoved = size - index - 1;
      // 删除的元素不是最后一个
      if (numMoved > 0)
          // 索引后的元素前移
          System.arraycopy(elementData, index+1, elementData, index,
                           numMoved);
      // 同上, 让 GC 回收内存.
      elementData[--size] = null; 
  }

/**
 * 删除列表中索引介于 [fromIndex, toIndex) 的元素.
 * 索引为 fromIndex 的元素会被删除, 索引为 toIndex 的元素会被保留
 * @throws 超界抛 IndexOutOfBoundsException 
 */
protected void removeRange(int fromIndex, int toIndex) {
    // 修改次数 + 1
    modCount++;
    // toIndex(包括)之后的元素数量
    int numMoved = size - toIndex;
    // 将 toIndex(包括)之后的所有元素复制到 fromIndex(包括)之后.
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // 删除后的元素数量
    int newSize = size - (toIndex-fromIndex);
    // GC!! 干活了
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}

/**
 * 从此列表中删除指定集合中包含的所有元素
 *
 * @param c 指定的集合
 * @return 如果在删除期间此 列表 因调用而更改, 返回 true
 * @throws 如果集合中的元素和列表元素不兼容, 抛出 ClassCastException
 * @throws 指定集合为null, 抛出 NullPointerException
 */
public boolean removeAll(Collection<?> c) {
    // 非空检验
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 * 从此列表中 保留 指定集合中包含的所有元素
 * 和上个方法的区别为一个删除, 一个保留
 * 具体差异: 传入 batchRemove 的参数不同
 */
public boolean retainAll(Collection<?> c) {
    // 非空检验
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            // 将需要保留的元素前移
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 即使 c.contains() 抛出异常, 也要于AbstractCollection 保持行为兼容性
        // 备注：ArrayList重写了AbstractCollection中的removeAll方法，removeAll调用了batchRemove
        if (r != size) {
            // 可能因 try 中的循环出现了异常
            // 可能其他线程调用了该列表
            // 将多出来的元素复制到 try 保留的元素后面.
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // GC 干活
            for (int i = w; i < size; i++)
                elementData[i] = null;
            // 这里为什么不是 + 1?
            // 若有读者知道原因, 还望在评论区告知.
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}


/**
 * 清空列表中的元素.
 * 执行完成后, 列表为空(全为null)
 */
public void clear() {
    modCount++;

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

    size = 0;
}

/**
 * 用指定元素替换列表中指定位置的元素.
 *
 * @param index 指定位置的索引
 * @param element 存在指定位置的新元素
 * @return 指定位置时旧元素
 * @throws 索引超界 IndexOutOfBoundsException
 */
public E set(int index, E element) {
    // 和 remove 用的同一个索引检查函数
    rangeCheck(index);
    
    // 更换新元素, 返回旧元素
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

   
// 位置访问操作
// 告诉编译器忽略 unchecked 警告信息
@SuppressWarnings("unchecked")
   E elementData(int index) {
       return (E) elementData[index];
   }

   /**
    * 获取列表指定位置的元素.
    *
    * @param  index 要获取的元素的索引
    * @return 指定位置的元素
    * @throws 索引超界, 抛出 IndexOutOfBoundsException
    */
   public E get(int index) {
       // 同 remove, set
       rangeCheck(index);
	// 这里应该是方便强制类型转换.
       return elementData(index);
   }


   /**
    * 返回指定元素第一次出现的索引
    * 如果列表中没有此元素, 返回 -1
    * contains 方法就是调用的此方法: return indexOf(o) >= 0;
    */
   public int indexOf(Object o) {
       if (o == null) {
           // null 也当成一个元素
           for (int i = 0; i < size; i++)
               if (elementData[i]==null)
                   return i;
       } else {
           for (int i = 0; i < size; i++)
               if (o.equals(elementData[i]))
                   return i;
       }
       return -1;
   }

   /**
    * 返回指定元素最后一次出现的索引
    * 如果列表中没有此元素, 返回 -1
    */
   public int lastIndexOf(Object o) {
       if (o == null) {
           for (int i = size-1; i >= 0; i--)
               if (elementData[i]==null)
                   return i;
       } else {
           for (int i = size-1; i >= 0; i--)
               if (o.equals(elementData[i]))
                   return i;
       }
       return -1;
   }

  /**
   * 序列化
   */
  private void writeObject(java.io.ObjectOutputStream s)
      throws java.io.IOException{
      // fail-fast, 后续判断是否有并发处理
      int expectedModCount = modCount;
      // 序列化没有标记 static, transient的字段包括 size.
      s.defaultWriteObject();

      // 序列化 size
      s.writeInt(size);

      // 按序 序列化所有元素
      for (int i=0; i<size; i++) {
          s.writeObject(elementData[i]);
      }
// 有其他线程修改列表
      if (modCount != expectedModCount) {
          // 抛出 fail-fast 异常.
          throw new ConcurrentModificationException();
      }
  }

  /**
   * 反序列化
   */
  private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {
      elementData = EMPTY_ELEMENTDATA;

      // 反序列化没有标记 static, transient的字段包括 size.
      s.defaultReadObject();

      // 反序列化 size
      s.readInt();

      if (size > 0) {
          // 根据 size 扩容.
          int capacity = calculateCapacity(elementData, size);
          SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
          ensureCapacityInternal(size);

          Object[] a = elementData;
          // 反序列化元素并加入列表中.
          for (int i=0; i<size; i++) {
              a[i] = s.readObject();
          }
      }
  }

   // 重写于 List 接口
@Override
// 消除 unchecked 警告
   @SuppressWarnings("unchecked")
   public void sort(Comparator<? super E> c) {
       // fail-fast, 后续判断是否有并发处理
       final int expectedModCount = modCount;
       // 排序, 底层使用 TimSort 实现, XXXX
       Arrays.sort((E[]) elementData, 0, size, c);
       // ArrayList被并发处理, 抛出异常
       if (modCount != expectedModCount) {
           throw new ConcurrentModificationException();
       }
       // 修改次数 + 1
       modCount++;
   }

  /**
   * 按正确顺序包含此列表中所有元素的数组
   * 返回的数组为 elementData 的复制, 修改返回的数组不会对 elementData 造成影响.
   *
   * @return 按正确顺序包含此列表中所有元素的数组
   */
  public Object[] toArray() {
      // 直接复制 elementData, 然后返回
      return Arrays.copyOf(elementData, size);
  }

  /**
   * 返回运行时指定数组类型的数组.
   * 如果指定数组的容量小于 size, 新建一个容量为size的数组返回.
   * 否则将数据复制到指定数组返回.
*
   * @param a 指定数组, 如果 a 足够大(容量大于 size), 返回该数组, 否则返回一个相同类型的新数组.
   *
   * @return 包含列表元素的数组
   * @throws 如果指定数组的类型不是列表元素类型的父类, 抛出 ArrayStoreException
   * @throws 指定数组为null, 抛出 NullPointerException
   */
  @SuppressWarnings("unchecked")
  public <T> T[] toArray(T[] a) {
      if (a.length < size)
          // 利用反射, 返回一个大小为size , 类型和 a 相同的新数组.
          return (T[]) Arrays.copyOf(elementData, size, a.getClass());
      // 将数据复制到 a 中
      System.arraycopy(elementData, 0, a, 0, size);
      // 将 a[size] 置为 null(如果有的话), 对以后确定列表的长度很有用, 但只在调用方知道列表中不包含任何 null 元素时才有用.
      if (a.length > size)
          a[size] = null;
      return a;
  }

/**
 * 返回此 ArrayList 实例的副本, 浅拷贝
 * 返回 Object 使用时需要强制转换
 * @return 此 ArrayList 的副本
 */
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 通过 Arrays.copyOf 拷贝数据.
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

/**
 * 返回此列表 [fromIndex,toIndex) 之间的数据的 视图(SubList 类).
 * 如果 formIndex 和 toIndex 相等, 返回列表为空.
 * 返回的列表中的 elementData 和此列表的 elementData 是同一个.
 * 通过传递子视图可以将列表的操作用作范围操作, 比如: 删除一部分元素可以用, list.subList(from, to).clear();
 *
 */
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

List<String> strList = new ArrayList<String>(4);
                 strList.add("1");
                 strList.add("2");
                 strList.add("3");

      // for遍历
      for (int i = 0; i < strList.size(); i++) {
          System.out.println(strList.get(i));
      }

      // foreach
      // 备注: 只要实现Iterable接口, 就能使用foreach
     for (String s : strList) {
          System.out.println(s);
     }

     // foreach-lambda遍历
     strList.forEach(System.out::println);

     // iterator遍历
     Iterator<String> iterator = strList.iterator();
     while (iterator.hasNext()){
          String str = iterator.next();
          System.out.println(str);
          // 下一次出现ConcurrentModificationException
          // 问题是因为list的iterator方法返回的是ArrayList的内部类Itr
          // Itr里面的expectedModCount会与ArrayList的modCount进行比较
          // 剩下的就不言而喻
          strList.remove(str);
          // 进行iterator遍历时, 如果进行remove等操作, 调用iterator的方法
          // 而不是ArrayList的方法
         //  iterator.remove();
    }

    // ListIterator可以进行顺序, 逆序遍历, 可以指定index位置开始遍历
    ListIterator<String> iterator = strList.listIterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }
    iterator = strList.listIterator(strList.size());
    while (iterator.hasPrevious()){
        System.out.println(iterator.previous());
        iterator.remove();
    }

    // 使用并行遍历, 可以将元素放在不同的迭代器进行并行遍历
    Spliterator<String> spliterator = strList.spliterator();
    // split, 分而治之, 类似算法里面的分治
    Spliterator<String> otherSpliterator = spliterator.trySplit();
    spliterator.forEachRemaining(System.out::println);
    otherSpliterator.forEachRemaining(System.out::println);

/**
 * The number of times this list has been <i>structurally modified</i>.
 * Structural modifications are those that change the size of the
 * list, or otherwise perturb it in such a fashion that iterations in
 * progress may yield incorrect results.
 *
 * <p>This field is used by the iterator and list iterator implementation
 * returned by the {@code iterator} and {@code listIterator} methods.
 * If the value of this field changes unexpectedly, the iterator (or list
 * iterator) will throw a {@code ConcurrentModificationException} in
 * response to the {@code next}, {@code remove}, {@code previous},
 * {@code set} or {@code add} operations.  This provides
 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
 * the face of concurrent modification during iteration.
 *
 * <p><b>Use of this field by subclasses is optional.</b> If a subclass
 * wishes to provide fail-fast iterators (and list iterators), then it
 * merely has to increment this field in its {@code add(int, E)} and
 * {@code remove(int)} methods (and any other methods that it overrides
 * that result in structural modifications to the list).  A single call to
 * {@code add(int, E)} or {@code remove(int)} must add no more than
 * one to this field, or the iterators (and list iterators) will throw
 * bogus {@code ConcurrentModificationExceptions}.  If an implementation
 * does not wish to provide fail-fast iterators, this field may be
 * ignored.
 */
protected transient int modCount = 0;

/**
 * Returns an iterator over the elements in this list in proper sequence.
 *
 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 *
 * @return an iterator over the elements in this list in proper sequence
 */
public Iterator<E> iterator() {
    return new Itr();
}

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

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

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}