今天我们要谈论的是 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”，你还会表示赞同吗？
