性能篇：深入源码解析和性能测试arraylist和LinkedList差异！

嗨，大家好，我是小米！今天我们要谈论的是 Java 中两个常用的集合类：ArrayList 和 LinkedList。大家都知道，这两者在新增和删除元素的操作上有一些差异，那么它们究竟在性能上有何表现呢？我们通过深入源码解析和性能测试来一探究竟！

ArrayList 新增元素到末尾

这是最常见的新增元素操作，我们使用 add 方法将元素直接添加到 ArrayList 的末尾。

源码解析

下面是 ArrayList 新增元素的关键源码：

ArrayList 新增元素到指定索引位置

有时候，我们需要在 ArrayList 的任意位置添加元素。我们可以使用 add(int index, E element) 方法，将元素插入到指定的索引位置。

源码解析

下面是在任意位置添加元素的新增操作源码：

相同之处

• 在两种情况下，都会调用 ensureCapacityInternal 方法来确保容量足够。
• 都会涉及数组的复制或移动操作，确保新增元素后数组的有序性。

不同之处

• 直接加到末尾的操作无需涉及元素的移动，只需在数组末尾添加即可，效率相对较高。
• 在任意位置添加元素的操作需要涉及数组中间元素的移动，因此效率相对较低。

LinkedList 新增元素到末尾

LinkedList 是基于双向链表实现的集合类。当我们往 LinkedList 中新增元素时，它会在链表中找到合适的位置，然后进行节点的插入操作。

源码解析

下面是 LinkedList 新增元素的核心源码：

LinkedList 新增元素到任意位置

LinkedList 通过 add(int index, E element) 方法，同样可以在任意位置添加元素。

源码解析

下面是在任意位置添加元素的新增操作源码：

相同之处

• 直接加到末尾的操作和 ArrayList 类似，都是在末尾插入新元素。
• 在任意位置添加元素时，也需要检查索引是否越界。

不同之处

• 直接加到末尾的操作时，LinkedList 通过 linkLast 方法在链表末尾插入新节点。
• 在任意位置添加元素的操作时，LinkedList 通过 linkBefore 方法在指定位置之前插入新节点，涉及更多指针的调整。

新增元素操作 JMH 测试

具体的 JMH 测试代码

测试结论

通过ArrayList 和 LinkedList 新增元素操作测试，我们可以得到：

• 如果是从集合的头部新增元素，ArrayList 花费的时间应该比 LinkedList 多，因为需要对头部以后的元素进行复制。
• 如果是从集合的中间位置新增元素，ArrayList 花费的时间搞不好要比 LinkedList 少，因为 LinkedList 需要遍历。
• 如果是从集合的尾部新增元素，ArrayList 花费的时间应该比 LinkedList 少，因为数组是一段连续的内存空间，也不需要复制数组；而链表需要创建新的对象，前后引用也要重新排列。

ArrayList 删除元素

ArrayList 删除元素时，首先要找到要删除的元素位置。然后，它需要将该位置之后的所有元素向前移动一个位置，以保持数组的有序性。这个过程可能会导致性能开销，特别是在删除靠前的元素时，需要移动的元素越多，开销就越大，性能就越慢。

源码解析

下面是 ArrayList 删除元素的核心源码：

删除元素的性能开销

在 ArrayList 中删除元素的性能受到删除位置的影响。当删除靠前的元素时，需要将该位置之后的元素都向前移动，开销较大。这是因为 System.arraycopy 方法需要复制一定数量的元素，而这个数量取决于删除位置之后的元素个数。

LinkedList 删除元素

如何删除元素

LinkedList 删除元素时，首先需要找到要删除的元素位置。这里有一个特殊之处：如果要删除的元素位于链表的前半部分，LinkedList 会从链表头部开始循环查找；而如果位于后半部分，就从链表尾部开始循环查找。这是为了最大程度地减小查找的开销。

源码解析

下面是 LinkedList 删除元素的核心源码片段：

删除元素的性能特点

LinkedList 删除元素的性能特点主要取决于删除的位置。如果删除的元素靠近链表的头部或尾部，性能相对较高，因为只需在相对较短的部分内查找。然而，如果删除的元素位于链表中间，就需要从头部或尾部遍历到目标位置，性能开销相对较大。

删除元素操作 JMH 测试

具体的 JMH 测试代码

测试结论

通过 ArrayList 和 LinkedList 删除元素操作测试，我们可以得到：

• 从集合头部删除元素时，ArrayList 花费的时间比 LinkedList 多很多；
• 从集合中间位置删除元素时，ArrayList 花费的时间比 LinkedList 少很多；
• 从集合尾部删除元素时，ArrayList 花费的时间比 LinkedList 少一点。

总结

由于 ArrayList 是数组实现的，而数组是一块连续的内存空间，在添加（或删除）元素到数组头部的时候，需要对头部以后的数据进行复制重排，所以效率很低；而 LinkedList 是基于链表实现，在添加（或删除）元素的时候，首先会通过循环查找到添加（或删除）元素的位置，如果要添加（或删除）的位置处于 List 的前半段，就从前往后找；若其位置处于后半段，就从后往前找。因此 LinkedList 添加（或删除）元素到头部是非常高效的。

同上可知，ArrayList 在添加（或删除）元素到数组中间时，同样有部分数据需要复制重排，效率也不是很高；LinkedList 将元素添加（或删除）到中间位置，是添加（或删除）元素最低效率的，因为靠近中间位置，在添加（或删除）元素之前的循环查找是遍历元素最多的操作。

而在添加（或删除）元素到尾部的操作中，我们发现，在没有扩容的情况下，ArrayList 的效率要高于 LinkedList。这是因为 ArrayList 在添加（或删除）元素到尾部的时候，不需要复制重排数据，效率非常高。而 LinkedList 虽然也不用循环查找元素，但 LinkedList 中多了 new 对象以及变换指针指向对象的过程，所以效率要低于 ArrayList。

说明一下，这里我是基于 ArrayList 初始化容量足够，排除动态扩容数组容量的情况下进行的测试，如果有动态扩容的情况，ArrayList 的效率也会降低。

END

我们已经从源码的实现角度深入了解了 ArrayList 和 LinkedList 的实现原理以及各自的特点。如果你能充分理解这些内容，很多实际应用中的相关性能问题也就迎刃而解了。

就像如果现在还有人跟你说，“ArrayList 和 LinkedList 在新增、删除元素时，LinkedList 的效率要高于 ArrayList，而在遍历的时候，ArrayList 的效率要高于 LinkedList”，你还会表示赞同吗？

希望通过这篇文章，你对它们的性能差异有了更深入的了解！如果有任何疑问或建议，欢迎在评论区留言，让我们一同学习进步！

如有疑问或者更多的技术分享，欢迎关注我的微信公众号“知其然亦知其所以然”！