List系列->01ArrayList

结合框架太多, 分类对比看或许效果会好一些, List系列, Map系列, Set系列;

List层级关系:

List层级关系

List系列:

1. ArrayList;
2. LinkedList;
3. Vector;
4. Stack;

一、参考文章:

二、ArrayList需要搞懂的问题:

• 1、add, get, remove时间复杂度是多少?
• 2、如何扩容, 为何要1.5倍扩容;

三、ArrayList.add:

3.1 ArrayList.add:

public boolean add(E e) {
    /**
     * 每次在添加元素之前, 都需要对ArrayList内部维持的数组容量进行检测, 如果在插入之前,
     * 数组容量 ≥ MaxCap, 则需要对当前数组进行扩容;模块<3.2>
     */
    ensureCapacityInternal(size + 1);  
    /**
     * 1. 如果忽略数组拷贝的操作, 这里每次插入元素的时间复杂度为O(1);
     * 2. 结合模块<3.4> ~ <3.5>可知, 插入n个元素, 均摊到每个元素身上的拷贝时间复杂度为O(1);
     * 3. 所以两者结合起来以及根据时间复杂度的定义, 每次插入操作的时间复杂度还是O(1);
     */
    elementData[size++] = e;
    return true;
}

3.2 ArrayList.ensureCapacityInternal:

private void ensureCapacityInternal(int minCapacity) {
    /**
     * 默认情况下elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, 所以如果是第一次执行
     * add操作, 一定是会进入if内部, 然后对minCapacity进行赋值, 也可以说是初始化操作, 初始值
     * 为DEFAULT_CAPACITY = 10; 
     */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    /**
     * 然后就是对数组进行扩容操作;模块<3.3>
     */
    ensureExplicitCapacity(minCapacity);
}

3.3 ArrayList.ensureExplicitCapacity:

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    /**
     * 结合模块<3.1>传入的size + 1可知, 如果此时minCapacity - elementData.length > 0,
     * 则说明插入元素之后数组会越界, 所以在插入操作之前需要进入扩容操作; 模块<3.4>
     */
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

3.4 ArrayList.ensureExplicitCapacity:

private void grow(int minCapacity) {
    /**
     * 插入元素之前数组长度;
     */
    int oldCapacity = elementData.length;
    /**
     * 新的数组长度, 这里采用1.5倍扩容;
     */
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    /**
     * 如果1.5倍扩容还是 < minCapacity, 则直接使用minCapacity;
     */
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    /**
     * 这里就是一个数组长度极限的问题, 没啥好说的;
     */
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    /**
     * 数组扩容操作完成以后, 进行数据从旧数组到新数组的拷贝操作;
     */
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• 这里有一个比较关键的问题, 就是数组扩容采用的是1.5倍扩容, 查阅相关文章是没有发现有什么文章对这一点进行说明的, 为什么是1.5倍扩容, 不是1倍扩容? 不是2倍, 3倍扩容? 下面尝试证明一下为何要用1.5倍的方式进行扩容;

3.5 何为是1.5倍扩容:

• 1、假设1.5倍扩容, 连续插入n = 1.5^m个元素;
• 2、每次在1.5⁰, 1.5¹, 1.5², 1.5³ ... 1.5^m处需要扩容, 这些地方先记作扩容点;
• 3、每次扩容都需要进行元素从旧数组到新数组的拷贝操作, 则每次扩容需要复制元素的个数依次为1.5⁰, 1.5¹, 1.5², 1.5³, ... 1.5^m;
• 4、对于第三步, 总复制数通过等比数列公式可以算出为O(n) = 3 * 1.5^m - 2, 前面定义了n = 1.5^m, 所以O(n) = 3 * 1.5^m - 2 = 3*n - 2;
• 5、通过以上四步总结就是连续插入n个元素扩容需要进行元素复制的总次数为3n - 2, 均摊给每一个元素的复制操作次数为1, 即如果是1.5倍扩容, 则每个元素需要复制的时间复杂度为O(1);

3.6 假设2倍, 3倍扩容:

• 1、结合上面模块<3.5>, 其实按某一倍数进行扩容, 均摊到每一次元素身上复制操作的时间复杂度为O(1), 但是如果按其他倍数扩容, 每次申请会多余申请很多内存空间出来, 造成内存的浪费;

3.7 如果按某一基数继续扩容:

• 1、假设按T数量进行扩容, 连续插入n = m * t个元素;
• 2、则每次需要在1 + T, 1 + 2T, 1+ 3T...1 + mT处进行扩容, 这些地方可以即为扩容点;
• 3、每次扩容都需要进行元素从旧数组到新数组的拷贝操作, 则每次扩容需要复制元素的个数依次为1 + T, 1 + 2T, 1+ 3T...1 + mT;
• 4、对于第三步, 总复制数通过等差数列公式可以算出为O(n) =T², 均摊到每个元素身上就是O(n);
• 5、所以如果按照某一定值进行扩容, 则均摊到每个元素身上的拷贝操作的时间复杂度为O(1);

四、ArrayList.get:

4.1、ArrayList.get:

public E get(int index) {

    rangeCheck(index);

    return elementData(index);
}

E elementData(int index) {
    /**
     * get操作的时间复杂度仅为O(1)
     */
    return (E) elementData[index];
}

五、ArrayList.remove:

public E remove(int index) {

    modCount++;
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
        /**
         * 时间复杂度取决于这个地方, 如果每次都是从末端进行remove操作, 时间复杂度为O(1),
         * 仅仅执行了删除操作, 但是如果删除从某一处执行, 则删除之前需要进行数组的拷贝操作, 
         * 从index开始到末尾的元素整体往前移动一位, 也就是说每次删除一个元素, 针对元素偏移
         * 需要进行的拷贝数为O(n);
         */
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

六、ArrayList.add(int index, E e):

public void add(int index, E element) {
    /**
     * 这里也可以总结出, ArrayList内部维持的动态数组是指按脚标递增时, 如果数据容量已满,
     * 则进行数组扩容操作, 而不是在任意位置进行插入操作都会触发数组扩容操作;
     */
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    /**
     * 与模块<五>类似, 从index位置到末端所有元素往后偏移一位, 时间复杂度为O(n);
     */
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

七、总结(关于时间复杂度):

操作	时间复杂度	对时间复杂度有影响的操作
add(E e)	O(1)	elementData[index] = e
add(int index, E e)	O(n)	System.arraycopy
get	O(1)	return elementData[index]
remove	O(n)	System.arraycopy
扩容操作	O(1)	扩容策略