ArrayList 与 LinkedList 在随机访问场景下的性能差异对比

在需要频繁通过索引获取元素（随机访问）的场景下，优先选择 ArrayList，LinkedList 在此类操作上的性能开销显著更高。

先说结论：随机访问场景下 ArrayList 是更稳妥的选择，LinkedList 仅建议在频繁头部插入或删除且极少随机读取时使用。

适合：读多写少、需要按索引快速定位元素的业务逻辑。
重点看：底层数据结构决定的时间复杂度差异，而非单纯的基准测试数字。
别忽略：LinkedList 每个节点额外的内存开销以及 CPU 缓存友好性较差的问题。

快速处理思路

主要通过代码审查和重构来解决，以下是快速排查和调整的思路：

全局搜索项目中 LinkedList 的实例化位置。
检查该集合是否被用于 get(index) 循环或频繁随机读取。
如果是，直接替换为 ArrayList 并回归测试。

为什么会这样

ArrayList 底层基于动态数组实现，内存连续，通过索引计算内存偏移量即可直接获取元素，时间复杂度为 O(1)。LinkedList 底层基于双向链表，每个元素封装在节点对象中，随机访问时需要从头节点或尾节点开始遍历指针，时间复杂度为 O(n)。

性能差异随列表长度增加呈线性增长，大数据量下 LinkedList 可能慢数个数量级。具体倍数取决于列表长度、JVM 版本和硬件缓存策略，但算法复杂度的差异决定了数据量越大，LinkedList 的随机访问劣势越明显。

分步处理

按照以下步骤进行代码调整和确认：

第一步：定位使用点

在 IDE 中搜索 new LinkedList 或 Lists.newLinkedList，记录所有声明为 List<T> 但实现类为 LinkedList 的地方。

第二步：分析访问模式

检查代码中是否存在如下模式的循环：

for (int i = 0; i < list.size(); i++) {
    T item = list.get(i);
    // 处理逻辑
}

这种写法在 LinkedList 上会导致每次 get(i) 都触发一次遍历，整体复杂度变为 O(n^2)。

第三步：执行替换

将初始化代码改为：

List<T> list = new ArrayList<>();

如果涉及并发修改，考虑 CopyOnWriteArrayList 或加锁，不要盲目替换为线程不安全集合。

怎么验证是否生效

不要仅依赖 System.currentTimeMillis() 进行微基准测试，建议使用 JMH（Java Microbenchmark Harness）进行验证。

1. 引入依赖

在 pom.xml 中添加：

<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>1.37</version>
</dependency>
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>1.37</version>
</dependency>

2. 编写基准测试

@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@State(Scope.Thread)
public class ListAccessBenchmark {

    @Param({"100", "10000"})
    public int size;

    private ArrayList<Integer> arrayList;
    private LinkedList<Integer> linkedList;

    @Setup
    public void setup() {
        arrayList = new ArrayList<>();
        linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
    }

    @Benchmark
    public Integer arrayListAccess() {
        return arrayList.get(size / 2);
    }

    @Benchmark
    public Integer linkedListAccess() {
        return linkedList.get(size / 2);
    }
}

3. 其他观察方式

使用 profiling 工具（如 VisualVM、JProfiler）查看 CPU 采样，确认 LinkedList.get 方法不再是热点。
观察 GC 日志，ArrayList 通常比 LinkedList 产生更少的临时对象和垃圾回收压力。
在测试环境模拟大数据量（如 10 万级以上元素），观察接口响应时间的变化趋势。

常见坑

误以为插入都快：LinkedList 仅在已知节点位置（如通过迭代器）插入/删除时有优势，随机位置插入同样需要遍历查找位置。
内存开销：LinkedList 每个节点需要额外存储前后指针，内存占用远高于 ArrayList，大列表下可能引发频繁 GC。
缓存局部性：ArrayList 内存连续，对 CPU 缓存更友好，LinkedList 节点分散在堆内存中，缓存命中率低。
线程安全：两者都不是线程安全的，多线程环境下替换时需确认同步机制。