List

为什么arraylist比linklist查询速度快

array占用的是一段连续的内存空间，因此get(index)的时候，只需要首个元素的位置+偏移量就可以查到。时间复杂度：o(1)。

link占用的内存空间不是连续的，如果想查出来，需要进行遍历。时间复杂度：o(n)。

扩容机制

1. 数组默认大小是10.

2. size不足的时候，会新生成一个增加原有容量一半的数组。

3. 将原有的数组里面的元素拷贝到新数组。

Fail-Fast机制

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。