ArrayList和LinkedList的区别看这一篇就够了！

Dear 丶 2023-10-03 10:52 16阅读 0赞

> 用一句话总结ArrayList和LinkedList的区别是：ArrayList底层是数组，查询快、增删慢；LinkedList底层是链表，查询慢、增删快。

但是，任何技术的好坏都是要看场景的...而且，LinkedList增删真的快吗？

关于ArrayList和LinkedList的区别，个人认为要结合底层数据结构来看查询和增删两个操作带来的影响。

## 查询比较 ##

ArrayList底层是数组，数组的存储空间是连续的，可以根据寻址方式直接找到对应的元素位置，时间复杂度是O(1)。

举个例子：在一条正规有门牌的街上，你知道第一家店是001号，那么008肯定就在第8间，你直接过去就好了。啪一下，很快啊！

![ce36bedbd87a3050bfa4fb1f95853136.png][]

但LinkedList底层是链表，存储空间不连续，需要通过指针关联，在查询过程中需要不断跳转新的地址。

举个例子，可能不准确：你想要找一家网红店，结果到了店里，店员告诉你找错了，这是分店3号，并给了你总店的地址，你开车到了总店，结果经理又告诉你业务扩张太快了，这家已经不是总店了，总店在xx路100号...

![5e551c8efa6f45e6acea32511725c6c8.png][]

这就是ArrayList比LinkedList查询快的原因。

## 增删比较 ##

我们都知道Java原生的数组是不能扩容的，如果我初始化时申请5个元素空间，那么就至多能存5个元素，不会因为我长得帅就包容一些。

![ce36bedbd87a3050bfa4fb1f95853136.png][]

ArrayList底层也是数组，但人家支持动态扩容，所以ArrayList人称“动态数组”。什么意思呢？

![323eba54d1ac149290765e4f35f296b1.png][]

假设你原始容量为4，那么插入新元素时就会触发扩容，一定几率还会触发元素拷贝，而数组扩容和元素拷贝是耗时操作，这也是ArrayList被喷增删慢的原因。但是，ArrayList增删元素必然会触发扩容和拷贝吗？NO：

![65b11c8739e432f7a0bbfdae52986bc6.png][]

插入同理，空间足够时，尾部插入不涉及元素拷贝

那么LinkedList在增删的表现如何呢？**理想情况下**，链表的增删操作时间复杂度确实为O(1)：

![9d034df1e5d7fad7796149a009c58729.png][]

我虽然没有像计算机科班的同学那样系统学过数据结构与算法，但是所谓的链表时间复杂度是O(1)是有前提的：**你必须先找到元素要插入或删除的位置！**就好比你要拆除某一间房子，你必须先找到那一间房子呀！

## JDK源码论证 ##

LinkedList的查询相对ArrayList慢一些，这个没有疑问，那么两者增删效率如何呢？

当前得到的信息是：

*  LinkedList查询慢
 *  LinkedList增删快
 *  要增删，必须先找到元素位置，所以增删必然伴随着链表遍历

所以LinkedList增删的效率是综合的结果。最后一句话，可以在LinkedList的API中找到论证：

![a13d8504cef8fd669c5e138b2d753c0a.png][]

![1435a5e958049b152036e5b67e6a1119.png][]

底层需要根据节点指针遍历，时间复杂度O(N)

而反观ArrayList的get(index)：

![625d2832b02287c98921d7ed55f18183.png][]

![99f67a5a694ca013cb445addbbfa544e.png][]

![2e7f2bb8cd7fca927603283a55c4f3c3.png][]

ArrayList的get操作直接根据数组下标得到元素，底层是寻址，不用遍历，时间复杂度O(1)

总的来说就是：

ArrayList：查询O(1)，增删**可能**涉及数组扩容和拷贝（不是100%）

LinkedList：查询O(N)，增删O(1)，**但增删要先找到元素位置**

如果ArrayList初始化时分配恰当的容量，可以避免频繁的扩容和拷贝，甚至不用扩容和拷贝。如果你有兴趣自己动手试验一下，会发现其实**除了头插入和头删除，LinkedList几乎完败。**

本文就是ArrayList和LinkedList的区别总结，希望对大家有帮助哈~~

[ce36bedbd87a3050bfa4fb1f95853136.png]: https://img-blog.csdnimg.cn/img_convert/ce36bedbd87a3050bfa4fb1f95853136.png
[5e551c8efa6f45e6acea32511725c6c8.png]: https://img-blog.csdnimg.cn/img_convert/5e551c8efa6f45e6acea32511725c6c8.png
[323eba54d1ac149290765e4f35f296b1.png]: https://img-blog.csdnimg.cn/img_convert/323eba54d1ac149290765e4f35f296b1.png
[65b11c8739e432f7a0bbfdae52986bc6.png]: https://img-blog.csdnimg.cn/img_convert/65b11c8739e432f7a0bbfdae52986bc6.png
[9d034df1e5d7fad7796149a009c58729.png]: https://img-blog.csdnimg.cn/img_convert/9d034df1e5d7fad7796149a009c58729.png
[a13d8504cef8fd669c5e138b2d753c0a.png]: https://img-blog.csdnimg.cn/img_convert/a13d8504cef8fd669c5e138b2d753c0a.png
[1435a5e958049b152036e5b67e6a1119.png]: https://img-blog.csdnimg.cn/img_convert/1435a5e958049b152036e5b67e6a1119.png
[625d2832b02287c98921d7ed55f18183.png]: https://img-blog.csdnimg.cn/img_convert/625d2832b02287c98921d7ed55f18183.png
[99f67a5a694ca013cb445addbbfa544e.png]: https://img-blog.csdnimg.cn/img_convert/99f67a5a694ca013cb445addbbfa544e.png
[2e7f2bb8cd7fca927603283a55c4f3c3.png]: https://img-blog.csdnimg.cn/img_convert/2e7f2bb8cd7fca927603283a55c4f3c3.png