// 默认容量大小，当你使用无参构造器 new ArrayList() 创建对象时，第一次添加元素（调用 add 方法）时，数组长度会被扩容为这个值（10）
private static final int DEFAULT_CAPACITY = 10;


// 用于空实例的共享空数组实例（当用户显式指定容量为 0 时使用）
private static final Object[] EMPTY_ELEMENTDATA = {};

// 用于默认大小空实例的共享空数组实例（当用户使用无参构造器时使用）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存储元素的数组，transient 表示该字段不参与默认的序列化过程
// 原因：elementData 的长度通常比实际存储的数据 size 大（比如数组长 10，但只存了 1 个数）。如果直接序列化整个数组，会把后面 9 个 null 也序列化进去，浪费空间。
transient Object[] elementData;

// 数组中元素个数，默认是0，注意区分 size 和 elementData.length（容量），size是当前元素个数，length是数组的容量空间
private int size;

// 无参初始化，默认是空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 有参初始化，指定容量大小
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 直接使用指定的容量大小
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}

// 添加元素
public boolean add(E e) {
  // 确保数组容量够用，size是元素个数
  ensureCapacityInternal(size + 1);
  // 直接在下个位置赋值
  elementData[size++] = e;
  return true;
}

// 确保数组容量够用
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算所需最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  	// 如果数组等于空数组，就设置默认容量为10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// 确保容量够用
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
  	// 如果所需最小容量大于数组长度，就进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容，就是把旧数据拷贝到新数组里面
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // 计算新数组的容量大小，是旧容量的1.5倍
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果扩容后的容量小于最小容量，扩容后的容量就等于最小容量
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果扩容后的容量大于Integer的最大值，就用Integer最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 扩容并赋值给原数组
  elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * @param original  原数组
 * @param newLength 新的容量大小
 */
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    // 如果原数组本身就是 Object[] 类型，直接 new Object[]
    // 如果原数组是 String[] 等子类型，需要用反射 Array.newInstance 创建对应类型的数组
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  	// 把原数组的元素拷贝到新数组
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

/**
 * @param src     原数组
 * @param srcPos  原数组的开始位置
 * @param dest    目标数组
 * @param destPos 目标数组的开始位置
 * @param length  被拷贝的长度
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

public boolean remove(Object o) {
  	// 判断要删除的元素是否为null
    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)
      	// 从index+1位置开始拷贝，也就是后面的元素整体向左移动一个位置
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
  	// 设置数组最后一个元素赋值为null，防止会导致内存泄漏
    elementData[--size] = null;
}

// 批量删除ArrayList和集合c都存在的元素
public boolean removeAll(Collection<?> c) {
    // 非空校验
    Objects.requireNonNull(c);
    // 批量删除
    return batchRemove(c, false);
}

// complement：removeAll 调用时传的是 false；retainAll 调用时传的是 true
private boolean batchRemove(Collection<?> c, boolean complement){
    // 将堆内存（Heap）中的实例变量，转存为栈内存（Stack）中的局部变量
    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 {
		// 当出现异常情况的时候，可能不相等
        if (r != size) {
            // 可能是其它线程添加了元素，把新增的元素也左移
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
      	// 把不需要保留的元素设置为null
        if (w != size) {
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}