Java 集合框架：ArrayList 与 LinkedList 的性能对比

在 Java 开发中，ArrayList 和 LinkedList 是 List 接口最常用的两个实现类。尽管它们存储数据的方式相似，但在底层原理和性能表现上却有着天壤之别。选择错误的集合类型可能会导致程序在处理大量数据时效率低下。

1. 理解底层存储机制

观察 数据结构本质。

ArrayList 基于动态数组实现。它在内存中开辟一块连续的空间来存储元素。当你初始化一个 ArrayList 时，它通常会预分配一定的容量（默认为 10）。当元素数量超过容量时，它会进行扩容操作，通常是创建一个更大的新数组，并将旧数据复制过去。

LinkedList 基于双向链表实现。它在内存中通过“节点”存储数据。每个节点包含三个部分：当前元素值、前一个节点的指针、后一个节点的指针。数据在内存中不连续分布，依靠指针链接。

2. 随机访问性能对比

分析 读取数据的效率。

ArrayList 支持高效的随机访问。由于内存连续，计算机可以通过简单的数学计算直接定位到任意索引位置的元素。其时间复杂度为 $O(1)$。

LinkedList 不支持高效的随机访问。要获取第 $N$ 个元素，必须从头节点（或尾节点）开始，顺着指针一个一个地向后遍历，直到找到目标位置。其时间复杂度为 $O(n)$。

结论：如果你需要频繁地通过索引（如 get(100)）读取数据，优先选择 ArrayList。

3. 插入与删除性能对比

区分 操作位置对性能的影响。

这是两者最容易混淆的地方，必须根据操作发生的具体位置来判断。

在列表头部（索引 0）操作

在 ArrayList 头部插入或删除元素非常低效。因为需要把数组中现有的所有元素向后（或向前）移动一位，腾出（或填补）位置。时间复杂度为 $O(n)$。

在 LinkedList 头部操作非常高效。只需要改变头节点的指针指向，无需移动其他元素。时间复杂度为 $O(1)$。

在列表中间指定位置操作

在 ArrayList 中，需要移动该位置之后的所有元素，时间复杂度为 $O(n)$。

在 LinkedList 中，虽然不需要移动元素，但必须先遍历链表找到该位置，这个过程耗时 $O(n)$，因此整体操作的时间复杂度也为 $O(n)$。

注意：虽然理论上复杂度接近，但 ArrayList 在批量复制内存时利用了 CPU 的局部性原理，实际速度往往比人们预期的要快，甚至在某些 JDK 版本中优于 LinkedList 的中间插入。

在列表尾部操作

在 ArrayList 尾部插入通常很快（除非触发扩容），平均时间复杂度接近 $O(1)$。

在 LinkedList 尾部操作也非常快，时间复杂度为 $O(1)$。

4. 内存消耗对比

计算 空间开销。

ArrayList 只存储具体的数据对象，除了预留的一点点缓冲容量外，没有额外的空间浪费。

LinkedList 的每个节点都需要维护额外的指针对象（前驱和后继）。如果存储 Integer 这种小对象，指针占用的内存可能比数据本身还大。

5. 实操代码演示

运行 以下代码，直观感受性能差异。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListPerformanceTest {
    static final int COUNT = 100000;

    public static void main(String[] args) {
        // 测试 ArrayList
        List<Integer> arrayList = new ArrayList<>();
        long start1 = System.currentTimeMillis();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(0, i); // 在头部插入
        }
        long end1 = System.currentTimeMillis();
        System.out.println("ArrayList 头部插入耗时: " + (end1 - start1) + "ms");

        // 测试 LinkedList
        List<Integer> linkedList = new LinkedList<>();
        long start2 = System.currentTimeMillis();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(0, i); // 在头部插入
        }
        long end2 = System.currentTimeMillis();
        System.out.println("LinkedList 头部插入耗时: " + (end2 - start2) + "ms");
    }
}

观察 控制台输出。你会发现 LinkedList 在头部插入时速度极快，而 ArrayList 会随着数据量增加变得越来越慢。如果你将 add(0, i) 改为 add(i)（尾部插入），两者的差距会大幅缩小。

6. 选择决策指南

参考 下表，根据实际场景做出选择。

总结：在绝大多数业务开发中，90% 的情况下你应该默认使用 ArrayList。只有当你明确需要在列表头部进行频繁的增删操作，或者实现特定的队列逻辑时，才考虑使用 LinkedList（或者更好的 ArrayDeque）。