ArrayList

ArrayList扩容

private void ensureCapacityInternal(int minCapacity) {  
    if (minCapacity - elementData.length > 0) {  
        // 计算新的容量大小  
	    int newCapacity = elementData.length + (elementData.length >> 1);  
        if (newCapacity - minCapacity < 0) {  
            // 如果新的容量大小仍然不足以存储新元素
            // 就将需要的容量大小设置为新元素的个数加上一定的缓冲空间  
            newCapacity = minCapacity + 10;  
         }
         // 创建一个新的数组，将原来的元素复制到新的数组中  
         elementData = Arrays.copyOf(elementData, newCapacity);  
    }  
}

1. 如果判断容量不足则计算新的容量：为原来的1.5倍；
2. 如果新容量仍然不足以存储新元素，那么就需要将传入的参数（也就是需要的容量大小）+10；
3. 创建新数组；
4. 使用System.arraycopy拷贝旧数组的值到新数组中；
5. 使ArrayList的内部引用指向新数组；

扩容时的时间复杂度是多少？

这个过程中，涉及到复制数组的操作，因此时间复杂度是O(n)。

ArrayList 的 remove 方法有哪些注意事项？

[[快速失败和安全失败]]