关于java:ArrayList源码解析思维导图

常见相干问题

1. 通过 ArrayList() 结构一个空集合，初始长度是为 0 的
2. 第 1 次增加元素，会创立一个长度为 10 的数组，并将该元素赋值到数组的第一个地位
3. 第 2 次增加元素，汇合不为空，而且因为汇合的长度 size+ 1 是小于数组的长度 10，所以间接增加元素到数组的第二个地位，不必扩容
4. 第 11 次增加元素，此时 size+1 = 11，而数组长度是 10，这时候创立一个长度为 10+10*0.5 = 15 的数组（扩容 1.5 倍），而后将原数组元素援用拷贝到新数组。并将第 11 次增加的元素赋值到新数组下标为 10 的地位。
5. 当扩容 newCapacity – MAX_ARRAY_SIZE > 0 间接应用 hugeCapacity(minCapacity) 扩容 (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE
6. 第 Integer.MAX_VALUE + 1 次增加元素时，抛出 OutOfMemoryError 异样

• • *

源码如下：

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

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

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    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;
}

ArrayList 和 LinkedLisL 区别

1. 两个都是基于 List 的接口，非线程平安
2. arraylist 底层应用的数组，linkedlist 底层应用的是链表
3. 数组查问具备查问特定元素比拟快，而插入或删除时比较慢（数组在内存中是一块间断的内存，插入或删除时会挪动内存）
4. 链表不要求间断的内存，以后元素寄存上一个或下一个元素的地址，查问时须要从头部开始一个一个的找，查问效率低，插入时不须要挪动内存，只需扭转援用指向即可，所以插入或删除效率高
5. ArrayList 应用在查问多，插入或查问少的场景
6. LinkedList 应用在插入或删除多，查问少的场景中