ArrayList&LinkedList

ArrayList&LinkedList ArrayList

基于数组，需要连续内存随机访问快(根据下标)尾部插入、删除性能可以，其他部分插入、删除会移动数据因此性能差可以利用cpu缓存，局部性原理

linkedList

基于双向链表，无需连续内存随机访问慢(需要遍历链表)头尾插入删除性能高内存占用多

注意：并不是linkedList 就一定增删快，只是头尾快

往中间插入数据 linkedList不如ArrayList

局部性原理

cpu在读取集合的时候，会先将集合元素附近的内存一起放入cpu缓存中

而ArrayList是连续内存，所以可以一次读取很多元素

而linkedList在内存中不一定连续，所以一次存入缓存的元素可能会少一些

而且cpu缓存大小是有限的，可能会优化掉前面的cpu缓存数据