List常用集合分析，让你直接搞懂ArrayList和LinkedList
List集合分析
先理解两种数据结构：数组和链表
数组
- 连续性的内存空间，可以利用空间局部性原理，借助CPU cache进行缓存。
- **一经声明就要占用整块的内存空间，大小固定，不能再修改 **。
链表
- 链表是离散存储线性结构，每个节点通过指针连接，无法进行缓存。
- 链表没有大小限制，支持动态扩容。
再看具体集合
Vector已废弃，不用再考虑。
问题
为什么ArrayList在查询方面比LinkedList要快？
因为，ArrayList数据结构是数组，在内存中是连续存储，CPU Cache会缓存它，而LinkList数据结构是链表，在内存中是离散存储，无法缓存。所以在存取（set、get）方面，ArrayList比LinkList快。
在插入方面，ArrayList和LinkedList哪个更快？
插入分为头插、尾插、中间插。
看一下头插的时候：
ArrayList需要扩容+拷贝+位移
而LinkedList只需要定位到首位，首节点链条链接上就可以
看一下在数据为10W、100W、1000W实际用时对比
明显看到头插的情况下，LinkedList无论什么数据量都是用时最少。
再看一下尾插
尾插的情况下，ArrayList只需要扩容和拷贝
而LinkList需要从首节点顺着指针找到最后一个
看一下在数据为10W、100W、1000W实际用时对比
可以看到，在超过100W的数据时候，随着数据变大ArrayList比LinkList要更快。
中间插
中间插的情况下，ArrayList需要扩容、拷贝、位移。定位时间复杂度是O(1)
LinkList需要顺着指针寻找，定位时间复杂度是O(n)
可以看到，随着数据量增多，LinkList比ArrayList更耗时。
在删除方面，ArrayList和LinkedList哪个更快？
删除与新增差不多，只不过ArrayList只需要扩容和位移，不需要添加元素。LinkList只需要遍历到对应位置，把当前元素的前指针连接到下一个节点。
ArrayList和LinkedList线程安全吗？如何解决安全问题？
//替代LinkedList
List<String> linkedList = Collections.synchronizedList(new LinkedList<String>());
ConcurrentLinkedQueue concurrentLinkedQueue = new ConcurrentLinkedQueue();
//替代ArrayList
List<String> arrayList = Collections.synchronizedList(new ArrayList<String>());
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
总结
- ArrayList与LinkedList都有自己的使用场景，如果不能很好的确定，那么就使用ArrayList。如果能确定你会在集合的首位有大量的插入、删除以及获取操作，那么就使用LinkList。因为有对应的方法addFirst、addLast、removeFirst、removeLast、getFirst、getLast,这些操作的时间复杂度都是O(1)，非常高效。
- LinkedList的链表结构不一定会比ArrayList节省空间，首先它所占用的内存不是连续的，其次他还需要大量的实例化对象创造节点。虽然不一定节省空间，单链表结构也是非常优秀的数据结构，他能在你的程序设计中起着非常优秀的作用，例如可视化的链路追踪图，就是需要链表结构并需要每个节点自旋一次，用于串联业务。
结论
其实集合的源码看起来并不是很困难，遇到问题可以翻一翻，应该是能够看懂的~
ArrayList、LinkedList、Vector算是在面试题中比较常见的的知识点了。下面我就来做一个简单的总结：
ArrayList：
底层实现是数组
ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍
在增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)
LinkedList：
底层实现是双向链表[双向链表方便实现往前遍历]
Vector：
底层是数组，现在已少用，被ArrayList替代，原因有两个：
Vector所有方法都是同步，有性能损失。
Vector初始length是10 超过length时 以100%比率增长，相比于ArrayList更多消耗内存。
总的来说：查询多用ArrayList，增删多用LinkedList。
那到底什么时候用Linkedlist，整天对它扣细节什么用？
来看看Linkedlist作者的回复：
提示
- Arrays.asList 构建的集合，不能赋值给ArrayList
- Arrays.asList 构建的集合，不能再添加元素
- Arrays.asList 构建的集合，不能再删除元素
作者：老街俗人
来源链接：https://blog.csdn.net/longqiyuye925/article/details/117636882
