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

软件求生 2024-01-14 12:16:08

嗨,大家好,我是小米!今天我们要谈论的是 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”,你还会表示赞同吗?

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

0 阅读:11

软件求生

简介:从事软件开发,分享“技术”、“运营”、“产品”等。