ArrayList

重要的属性

int size	数组长度
Object[] elementData	元素数组

特点

1. 线程不安全

2. 数组自动扩容

3. 元素可以为Null

4. 元素可以重复

5. 有序，元素输出顺序与输入顺序一致

6. 插入与删除操作代价昂贵

添加

ArrayList.add()

public boolean add(E e) {
    // 确保数组容量足够大
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

ArrayList.ensureCapacityInternal()

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    
    ensureExplicitCapacity(minCapacity);
}

ArrayList.ensureExplicitCapacity()

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        // 扩容
        grow(minCapacity);
}

ArrayList.grow()

private void grow(int minCapacity) {
    // 获去老数组的容量
    int oldCapacity = elementData.length;
    // 扩容，容量增加一半
    // oldCapacity >> 1，相当于除以2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // copy到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

插入

public void add(int index, E element) {
    // 校验index是否超出数组容量
    rangeCheckForAdd(index);
    // 确保数组容量足够大
    ensureCapacityInternal(size + 1); 
    // 将index后的元素整体后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

System.arraycopy()

/**
 * System类的静态native方法
 * 实现数组之间的复制
 * @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);

System.arraycopy是对内存直接进行复制，减少了for循环过程中的寻址时间，从而提高了效能。System.arraycopy是浅复制，线程不安全的。