ArrayList 和 LinkedList 区别：从底层到实战，彻底搞懂

面试官：“ArrayList 和 LinkedList 有什么区别？”
你：“ArrayList 底层是动态数组，查询快、增删慢；LinkedList 底层是双向链表，增删快、查询慢。”
面试官：“那如果我在链表中间插入元素，真的是 O(1) 吗？”
你：“……”

很多人的回答止步于表面，但面试官追问的往往是细节。本文从源码到内存、从理论到陷阱，彻底讲透这两个集合的区别。

---

一、一句话对比（背诵版）

维度	ArrayList	LinkedList
底层结构	动态数组（Object[]）	双向链表（Node 节点）
查询效率	O(1)，随机访问快	O(n)，需遍历
增删效率	尾部 O(1)，中间 O(n)	头尾 O(1)，中间 O(n)
内存占用	连续内存，有闲置空间	分散内存，每个节点额外存储前后指针
使用场景	读多写少	写多读少（尤其是头尾操作）

---

二、底层结构详解

1. ArrayList：动态数组

// JDK 8 源码简化
public class ArrayList<E> {
    transient Object[] elementData;  // 存储元素的数组
    private int size;                // 实际元素个数
}

• 初始容量为 10（懒加载，add 时才创建）
• 扩容：newCapacity = oldCapacity + (oldCapacity >> 1) → 1.5 倍扩容
• 元素在内存中连续存放，通过下标访问极快。

2. LinkedList：双向链表

// JDK 8 源码简化
public class LinkedList<E> {
    transient Node<E> first;   // 头节点
    transient Node<E> last;    // 尾节点
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
}

• 每个节点独立存在，通过 prev/next 指针连接。
• 没有扩容概念，随增随加。

---

三、增删效率的真实面目

很多人背“LinkedList 增删快 O(1)”，这是不严谨的。

1. 头尾操作：确实是 O(1)

linkedList.addFirst(e);   // 直接修改 first 指针
linkedList.addLast(e);    // 直接修改 last 指针
linkedList.removeFirst();
linkedList.removeLast();

2. 中间插入：O(n) 定位 + O(1) 改指针

// 在 index 处插入元素
linkedList.add(index, element);

源码中会先通过 node(index) 遍历到该位置：

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size-1; i > index; i--) x = x.prev;
        return x;
    }
}

遍历耗时 O(n)，真正改指针只是 O(1)。所以中间增删总复杂度也是 O(n)，和 ArrayList 的 O(n) 没有量级差别，只是常数不同（ArrayList 需要复制元素，LinkedList 只需改指针）。

结论：只有头尾增删，LinkedList 才有真正的 O(1) 优势。

---

四、查询效率：ArrayList 完胜

arrayList.get(10000);   // 直接返回 elementData[10000] → O(1)
linkedList.get(10000);  // 从 first 或 last 遍历 10000 步 → O(n)

所以随机读取场景，ArrayList 碾压 LinkedList。

---

五、内存占用对比

ArrayList

• 数组本身是连续内存，但可能预留了闲置空间（例如 size=10，capacity=15）。
• 每个元素只是一个引用（4 或 8 字节），无额外指针。

LinkedList

• 每个节点：前驱指针 + 后继指针 + 元素引用 ≈ 24 字节额外开销（64位 JVM 默认压缩指针下）。
• 节点在内存中分散，CPU 缓存不友好，遍历时 cache miss 率高。

结论：LinkedList 内存占用明显高于 ArrayList。

---

六、使用场景与误区

正确场景

场景	推荐
频繁随机访问（读多写少）	ArrayList
频繁头尾增删（如队列、栈）	LinkedList（或 ArrayDeque 更优）
频繁中间增删	两者都是 O(n)，但 LinkedList 常数更小，可酌情使用

常见误区

1. “LinkedList 增删总是比 ArrayList 快” → 错。中间增删都需要先定位，ArrayList 在尾部增删甚至更快。
2. “LinkedList 实现了 Queue，所以做队列最好” → 不完全是。ArrayDeque 在大多数场景下比 LinkedList 更快、更省内存。
3. “ArrayList 扩容很慢，所以能用 LinkedList 就用” → 过度担忧。扩容均摊后仍是 O(1)，且现代 JVM 内存分配很快。

---

七、实战建议

1. 写代码时如何选择？

// 已知元素数量，或者以随机访问为主
List<Integer> list = new ArrayList<>();

// 需要频繁在头尾操作，且元素数量很大
Queue<Integer> queue = new LinkedList<>();   // 或者 ArrayDeque

// 不确定？先用 ArrayList，遇到性能瓶颈再分析

2. 性能测试小例子

// 头部插入 10 万次
long start = System.currentTimeMillis();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    list.add(0, i);   // 每次移动全部元素
}
System.out.println("ArrayList head insert: " + (System.currentTimeMillis() - start) + "ms");

// LinkedList 头部插入
list = new LinkedList<>();
start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    list.add(0, i);   // 只改指针
}
System.out.println("LinkedList head insert: " + (System.currentTimeMillis() - start) + "ms");

结果（典型值）：

• ArrayList：~2000ms
• LinkedList：~5ms

---

八、总结一张表

特性	ArrayList	LinkedList
底层	数组	双向链表
随机访问 get/set	O(1)	O(n)
尾部增删	O(1) 均摊	O(1)
头部增删	O(n)	O(1)
中间增删	O(n) + 移动	O(n) + 改指针
内存连续性	连续	分散
额外内存	少量（预留空间）	较大（节点指针）
迭代性能	好（局部性）	差（指针跳跃）

终极建议：

• 默认用 ArrayList。
• 只有确定需要大量头尾操作且不需要随机访问时，再考虑 LinkedList（或更优的 ArrayDeque）。
• 永远不要为了“听说增删快”而在中间插入场景盲目使用 LinkedList。

希望这篇文章能帮你彻底掌握 ArrayList 与 LinkedList 的区别，面试时从容应对追问。