ArrayList和LinkedList底层实现原理、性能差异

ArrayList和LinkedList底层实现原理

1.说一下 ArrayList 底层实现方式？

①ArrayList 通过数组实现，一旦我们实例化 ArrayList 无参数构造函数默认为数组初始化长度为 10②,add 方法底层实现如果增加的元素个数超过了 10 个，那么 ArrayList 底层会新生成一个数组，长度为原数组的 1.5 倍+1，然后将原数组的内容复制到新数组当中，并且后续增加的内容都会放到新数组当中。当新数组无法容纳增加的元素时，重复该过程。是一旦数组超出长度，就开始扩容数组。扩容数组调用的方法 Arrays.copyOf(objArr, objArr.length + 1);

2.说一下 LinkedList 底层实现方式？

LinkedList 底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：


[使用场景]

（1）如果应用程序对各个索引位置的元素进行大量的存取操作，ArrayList对象要远优于LinkedList对象；
( 2 ) 如果应用程序主要是对列表元素进行循环，并且循环时候进行插入或者删除操作，LinkedList对象要远优于ArrayList对象；
ArrayList:

上述例子中，若删除第二个元素，后面的元素要一个一个向前移，所以越是删前面的元素，越是耗费时间。当数据量很大时，要删前面的元素时，用ArrayList存储数据时相当不划算的。
ArrayList循环删除时（比如删除ArrayList中偶数），应该从后往前遍历删除！

（注意：删了，整体向前移了之后，数组的最后一个元素只是赋值给了它的前一个元素，没有彻底的消失，只是size–之后，我们不能访问和操作它，只能访问到它的前一个元素。）

LinkedList：

删前面或者后面的效率很高，删除中间的效率最低。

[获取方式]
ArrayList有索引，效率会比链表高的多

LinkdeList错误的用法：
list.get(i)，LinkedList的底层是一个链表，随机访问i的时候，链表只能从头往后数，第i个才返回所以时间随着i的变大时间会越来越长
LinkdeList正确的用法：
顺序访问，LinkedList绝对不要用get方法，即使LinkedList的元素个数只有很少的几个。养成好习惯，免得犯错。

for each

for (String element : list) {
    // process element here
}

性能比较 原文：https://blog.csdn.net/zl_StepByStep/article/details/80055792
底层原理 原文：https://blog.csdn.net/weixin_38422276/article/details/78978410