ArrayList和LinkedList的区别

ArrayList

扩容机制

1. ArrayList()会使用长度为零的数组

2. ArrayList(int initialCapacity)会使用指定容量的数组

3. public ArrayList(Collection<?entends E>c)会使用c的大小作为数组容量

4. add(Object o)首次扩容为10，再次扩容为上次的1.5倍

5. addAll(Collection c)没有元素时，扩容为Math.max(10,实际元素个数)，有元素是，扩容为Math.max(原容量1.5倍，实际元素个数)

特点

1.基于数组，需要连续内存

2.随机访问快（根据指定下标访问）

3.尾部插入，删除性能可以，其他部分插入、删除都会移动数据，因此性能会低

4.可以利用cpu缓存，局部性原理

LinkedList

特点

1.基于双向链表，无需连续内存（每一位都存有下一个的指针）

2.随机访问慢（要沿着链表遍历）

3.头尾插入删除性能高

4.占用内存多