大厂之路的第三篇 LinkedList和ArrayList
前两篇我们分别从源码角度分析了 LinkedList和ArrayList。今天，我们要对这两种线性表做一个总结，分析一下两者各自的优劣势以及各自适合的应用场景。
要对比两者的优劣势，我们可以从数据的增删改查角度来分别对比。
-
增，即插入。
插入可以分为向中间插入和向尾部插入两种情况。1.1 向中间插入:
对于ArrayList:由于其底层是基于动态数组，在向中间插入的过程一方面可能要涉及到数组的扩容，另一方面在向中间插入的过程需要将要插入位置后所有元素都往后移动，这样的性能肯定是很差的。
而对于LinkedList：由于其底层是基于链表的形式，所以在向中间插入的过程中，只需要找到对应的位置，改变一下next和prev指针即可。在性能上就要远远高于ArrayList。1.2 向尾部插入：
对于ArrayList:由于其底层基于数组，所以要找到尾部时间复杂度就是O(1)，又由于是向尾部插入，除了需要扩容外不需要做其他任何操作，所以性能还算是不错的。
对于LinkedList:由于其是基于双链表，能够通过last指针很容易获取到链表尾部，然后要做的就是移动last指针和给原last节点重新赋给next指针即可。所以性能也是非常不错的。
所以， 对比
LinkedList和ArrayList，如果要向中间插入数据，LinkedList要优于ArrayList；而如果是向尾部添加数据，二者性能其实差不多。
-
删，即删除。
同样，删除也可以分为从中间删除和从尾部删除两种情况。2.1 从中间删除:
对于ArrayList:由于其底层是基于动态数组，从中间移除一个元素需要将要移除位置后所有元素都向前移动，这样的性能肯定是很差的。
而对于LinkedList：由于其底层是基于链表的形式，所以在移除中间节点的过程中，只需要找到对应的位置，改变一下next和prev指针即可。在性能上就要远远高于ArrayList。
2.2 从尾部删除:
与两者从尾部插入性质差不多，对于ArrayList可能还少了数组的扩容的步骤，所以性能也是差不多的。
所以， 对比
LinkedList和ArrayList，如果要移除中间某个位置的数据，LinkedList要优于ArrayList；而如果是向尾部添加数据，二者性能也差不多。
3.查，即查找。
查找分为查找指定位置和查找指定元素。
3.1 查找指定位置即随机查找:
对于ArrayList:由于其底层是基于数组，随机查找的时间复杂度为O(1)。
而对于LinkedList：由于其底层是基于链表的形式，随机查找的时间复杂度是O(n)。
3.2 查找指定元素即遍历查找: 两者的时间复杂度都为O(n)。
所以，对于随机查找
ArrayList要明显优于LinkedList,而在遍历查找时二者区别不大。
4.改，即修改某个元素的值。
对于修改来说，其实就是随机查找加重新赋值的过程。所以，ArrayList的性能显然要优于LinkedList。
增删改查我们都分析完了，两者的优劣势也就很明显了:
- 对于需要频繁插入和删除的数据集，我们优先使用
LinkedList. - 对于随机查找比较多的业务我们优先使用
ArrayList.
最后，还有几点需要补充：
1.ArrayList和LinkedList都是线程不安全的。对于ArrayList来说我们可以用Vector来替代；而对于LinkedList来说我们可以采用List list = Collections.synchronizedList(new LinkedList(...));这种方式来解决，这也是官方建议的方式。
- 在存储相同的数据时，
ArrayList所占的内存要小于LinkedList，因为ArrayList数组中存储的只是数据，而对于LinkedList的Node来说还需要存储next和prev指针。
3.在使用ArrayList的时候，如果可以的话尽量给ArrayList一个合适的初识大小，这样可以减少ArrayList数组的扩容操作，进而提高性能。
