ArrayList部分底层源码分析

JDK版本为1.8.0_271，以插入和删除元素为例，部分源码如下：

// 部分属性
transient Object[] elementData;	// 底层数组
private int size;	// 记录元素个数
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};	// 空Object数组

//构造器
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  //初始化为空数组
}

//方法:add()相关方法
public boolean add(E e) {
    //查看当前数组是否够多存一个元素
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //存入新元素到[size]位置，然后size自增1
    elementData[size++] = e;
    return true;
}

// 根据当前插入元素后所需要的容量判断
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算当前插入元素后所需要的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果当前数组还是空数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //那么minCapacity取DEFAULT_CAPACITY(10)与minCapacity的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//查看是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  //修改次数加1

    //如果需要的最小容量比当前数组的长度大，即当前数组不够存，就扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 数组扩容，在默认扩容为1.5倍，不够的话就选minCapacity，并校验是否越界，然后拷贝元素
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; //当前数组容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组容量是旧数组容量的1.5倍
    //看旧数组的1.5倍是否够
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //看新数组长度是否超过最大数组限制(Integer.MAX_VALUE-8)
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //复制一个新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 新数组长度超过最大数组限制(Integer.MAX_VALUE-8)
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 对minCapacity和MAX_ARRAY_SIZE进行比较
    // 若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
    // 若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}


// 移除元素，elementData为底层数组
public boolean remove(Object o) {
    // 判断当前元素是否为null
    if (o == null) {	
        // 逐个遍历底层数组中元素，
        for (int index = 0; index < size; index++)
            // 是否存在null
            if (elementData[index] == null) {
                fastRemove(index);	// 移除index位置的元素
                return true;
            }
    } else {
        // 逐个遍历底层数组中元素，
        for (int index = 0; index < size; index++)
            // 是否存在与o相等的元素
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

// 移除index位置的元素
private void fastRemove(int index) {
    modCount++;	// 修改次数加1
    int numMoved = size - index - 1;	// 需要迁移的元素数量，[index+1,size)区间
	// 根据numMoved判断是否需要迁移index之后的元素
    if (numMoved > 0)	// 不是，需要迁移元素
        // 迁移[index+1,size)区间到[index,size-1)区间
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 更新size
    elementData[--size] = null; 
}

在网上找了个添加元素的示意图，如图所示：

• ArrayList采用Object[]数组作为底层实现

• ArrayList自动扩容过程
  grow扩容方法会传入minCapacity，表示新list所需的最小容量；
  新list的容量newCapacity取原list长度*1.5和minCapacity的较大值

• ArrayList的add(E e)方法
  直接在list尾部插入元素e，无需迁移元素，时间复杂度o(1)
  

• ArrayList的add(int index,E e)方法
  在index位置插入元素e前，需要把之前[index,size）的元素整体向右迁移一个单位；
  然后插入元素e到index位置，并更新size,时间复杂度o(n)