1. 引言

在 Java 开发中，数据结构的选择直接影响程序的性能与可维护性。数组（Array）和链表（LinkedList）作为最基础的两种线性数据结构，它们的底层实现差异决定了各自在不同场景下的优劣。很多开发者在日常编码中凭直觉使用 ArrayList，却很少深入思考：ArrayList 底层就是数组，LinkedList 底层就是链表，这一差异究竟会带来怎样的性能鸿沟？

本文将从底层原理、内存模型、时间复杂度、实际场景和代码实战五个维度展开，帮你建立对这两种数据结构的完整认知框架。

2. 基本概念

2.1 数组

数组是一块连续的内存空间，用于存储相同类型的元素。在 Java 中，数组是固定长度的，一旦创建便无法改变大小。但我们可以通过 ArrayList 来使用动态数组，其内部本质上仍然是一个 Object 数组，通过扩容机制来支撑动态增删。

数组最大的优势是基于索引的随机访问：只要知道起始地址和元素大小，就能在 O(1) 时间内定位到任意位置的元素。

2.2 链表

链表由一系列节点组成，每个节点包含数据域和指针域。指针指向下一个节点的内存地址，使得所有节点在逻辑上串成一条线，但在物理内存上却可以分散存储。

Java 中的 LinkedList 是一个双向链表，每个节点同时持有前驱和后继的引用。这种结构赋予了链表在头尾进行增删操作时极高的效率，但牺牲了随机访问的能力。

3. 内存模型对比

特性	数组（ArrayList）	链表（LinkedList）
内存布局	连续内存块	分散的节点，通过指针连接
空间占用	仅存储数据本身	每个节点额外存储前驱和后继指针（约 24 字节开销）
缓存友好性	高（顺序读取时 CPU 缓存命中率高）	低（节点跳跃访问，缓存频繁失效）
扩容机制	需要预分配或动态扩容（扩容时复制整个数组）	按需分配，无需扩容

从内存角度看，数组的连续布局天然对 CPU 缓存友好，在遍历场景下性能远超链表。而链表每个节点的额外指针开销意味着相同数量的元素会占用更多内存，且在遍历时频繁的指针跳转会触发大量缓存未命中。

4. 时间复杂度对比

操作	数组（ArrayList）	链表（LinkedList）
随机访问（get）	O(1)	O(n)
头部插入（addFirst）	O(n)（需要移动所有元素）	O(1)
尾部插入（addLast）	均摊 O(1)（非扩容时）	O(1)
中间插入（add index）	O(n)（后续元素需后移）	O(n)（需要先遍历到目标位置）
头部删除（removeFirst）	O(n)	O(1)
尾部删除（removeLast）	O(1)	O(1)
中间删除（remove index）	O(n)	O(n)（同样需要先遍历定位）
搜索（查找元素）	O(n)	O(n)

需要注意一个常见的认知误区：很多人认为「链表中间插入删除是 O(1)」。严格来说，链表在已知节点指针的情况下修改指针引用确实是 O(1)，但在此之前你需要通过遍历定位到该节点，这一步是 O(n)。因此，在未持有节点引用的情况下，链表的中间增删整体复杂度依然是 O(n)。

5. 代码实战

下面用一段 Java 代码直观展示两种数据结构在不同操作场景下的性能差异：

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

public class ArrayVsLinkedList {
    private static final int SIZE = 100_000;

    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // 1. 尾部追加对比
        System.out.println("=== 尾部追加 ===");
        measure(() -> {
            for (int i = 0; i < SIZE; i++) {
                arrayList.add(i);
            }
        }, "ArrayList 尾部追加");

        measure(() -> {
            for (int i = 0; i < SIZE; i++) {
                linkedList.add(i);
            }
        }, "LinkedList 尾部追加");

        // 2. 头部插入对比
        System.out.println("\n=== 头部插入 ===");
        measure(() -> {
            for (int i = 0; i < 10000; i++) {
                arrayList.add(0, i);
            }
        }, "ArrayList 头部插入");

        measure(() -> {
            for (int i = 0; i < 10000; i++) {
                linkedList.add(0, i);
            }
        }, "LinkedList 头部插入");

        // 3. 随机访问对比
        System.out.println("\n=== 随机访问 ===");
        measure(() -> {
            for (int i = 0; i < SIZE; i++) {
                arrayList.get(i);
            }
        }, "ArrayList 随机访问");

        measure(() -> {
            for (int i = 0; i < SIZE; i++) {
                linkedList.get(i);
            }
        }, "LinkedList 随机访问");

        // 4. 遍历对比
        System.out.println("\n=== 顺序遍历 ===");
        measure(() -> {
            for (Integer num : arrayList) {
                // do nothing
            }
        }, "ArrayList for-each 遍历");

        measure(() -> {
            for (Integer num : linkedList) {
                // do nothing
            }
        }, "LinkedList for-each 遍历");
    }

    private static void measure(Runnable task, String label) {
        long start = System.nanoTime();
        task.run();
        long end = System.nanoTime();
        System.out.printf("%s 耗时: %.2f ms%n", label, (end - start) / 1_000_000.0);
    }
}

上述测试中，ArrayList 在随机访问和顺序遍历场景下表现优异，而 LinkedList 在头部插入时具有压倒性优势。读者可在本地环境运行这段代码来获得更直观的感受。

6. 使用场景与选型建议

6.1 优先选择数组（ArrayList）的场景

• 频繁随机访问：需要通过索引读取元素时，ArrayList 的 O(1) 访问速度无出其右。
• 尾部增删为主：大多数业务场景中数据追加在末尾，ArrayList 的尾插均摊 O(1) 完全够用。
• 大规模顺序遍历：数组的 CPU 缓存友好特性使得遍历性能稳定出色。
• 内存敏感场景：ArrayList 比 LinkedList 少存储大量指针，内存占用更低。

6.2 优先选择链表（LinkedList）的场景

• 频繁头部增删：实现队列或双端队列时，LinkedList 的 O(1) 头尾操作优势明显。
• 无需随机访问的纯顺序处理：配合迭代器使用时可以规避 get 遍历的性能陷阱。
• 插入删除远多于查询：如果已经持有节点引用，链表的修改代价极低。

6.3 一个重要提醒

在实际开发中，90% 以上的场景使用 ArrayList 就够了。LinkedList 的优势高度集中在特定场景（如实现队列、频繁头部操作），且因为额外指针开销和缓存不友好，在不恰当的场景中使用反而会导致性能下降。任何时候都不要凭「链表插入快」的笼统印象做选择，要结合具体的操作类型和数据规模来判断。

7. 总结

数组和链表不是谁取代谁的关系，而是互补的关系。理解它们的底层原理，能够帮助你在面试中从容回答，更能在实际项目中做出理性的数据结构选择。牢记三个关键结论：

• 需要随机访问和高吞吐遍历时，选数组。
• 需要频繁在头部或已知位置增删时，选链表。
• 拿不准的时候，默认用 ArrayList，它比你想象的更强大。

数据结构的选择没有银弹，唯有理解本质，才能在正确的时间做出正确的决定。