ArrayList的扩容机制以及ArrayList与LinkedList的区别

ArrayList的扩容机制

假设采用无参构造器来实列化ArrayList对象

ArrayList arrayList = new ArrayList();

此时，arrayList的初始容量为零,当第一次调用add方法时，会触发扩容机制，容量扩容为10。
此后，在调用add方法时，如果容量不足，则容量会扩容为当前容量的1.5倍。

capcity = capacity + (capacity >> 1); 

如果在调用addAll方法时需要扩容,假设最终数组的长度为len，那么：

capacity = max(capacity + (capacity >> 1), len);

之所以这样设计，是防止采用之前的扩容机制会多次扩容。

ArrayList与LinkedList的区别

• 底层实现上:
  ArrayList底层实现是数组， LinkedList底层实现是双向链表
• 随机查询效率上：
  ArrayList随机查询时间复杂度为O(1), LinkedList随机查询平均复杂度为O(n)
• 增删效率上:
  • ArrayList尾部增加元素，如果不发生扩容，时间复杂度为O(1),如果发生扩容，则时间复杂度为O(n),
    尾部删除元素时间复杂度为O(1),其余位置索引值越小，时间复杂度越高
  • LinkedList首尾增删时间复杂度为O(1),其余位置平均时间复杂度为O(n)
• cpu缓存利用上：
  ArrayList底层是数组，所以其在内存上是一块连续的内存区域，因为cpu缓存利用了局部性原理,
  所以ArrayList的缓存命中率比较高，相反LinkedList的内存空间是不连续的，所以缓存命中率较低。