个人网站

面试常问"ArrayList 和 LinkedList 的区别"，大部分人能说出"数组 vs 链表"，但追问"随机访问差多少"、“头插性能差多少”、“Vector 和 ArrayList 呢”，就说不清楚了。更尴尬的是，很多人以为 LinkedList 插入删除快，实际测试发现并不一定。

今天咱们把三个列表的存储性能彻底对比清楚。

一、先说结论：三剑客核心对比

维度	ArrayList	Vector	LinkedList
底层结构	Object[] 数组	Object[] 数组	双向链表
随机访问	O(1)	O(1)	O(n)
尾部添加	O(1)均摊	O(1)均摊	O(1)
头部添加	O(n)	O(n)	O(1)
中间插入	O(n)	O(n)	O(n)
扩容	1.5 倍	2 倍	无需扩容
线程安全	❌	✅ synchronized	❌
内存占用	紧凑	紧凑	每个 Node 额外 2 个指针

一句话记住：ArrayList 是跑车（快但固定车道），LinkedList 是火车（灵活但提速慢），Vector 是加了锁的跑车（安全但更慢）。

二、ArrayList：数组之王，随机访问无敌

为什么 ArrayList 随机访问快？ 数组的内存是连续的，通过下标直接计算内存地址：

// ArrayList.get(i) 的底层
elementData[index];  // 👈 直接通过下标访问，O(1)

为什么中间插入慢？ 需要移动后面的所有元素：

// ArrayList.add(index, element) 的底层
System.arraycopy(elementData, index, elementData, index + 1, size - index);  // 👈 移动元素，O(n)
elementData[index] = element;

生活类比： ArrayList 像电影院座位——找座快（看编号），但中间加座得让后面的人全往后挪。

ArrayList 的性能特征：

• ✅ get(i) —— 极快
• ✅ add(e) 尾部追加 —— 快（偶尔扩容）
• ❌ add(0, e) 头部插入 —— 慢（移动所有元素）
• ❌ remove(0) 头部删除 —— 慢

三、Vector：加了锁的 ArrayList

Vector 和 ArrayList 底层结构完全一样，唯一区别是所有公共方法都加了 synchronized：

// Vector 的源码
public synchronized boolean add(E e) { /* ... */ }
public synchronized E get(int index) { /* ... */ }
public synchronized E remove(int index) { /* ... */ }

性能代价： 每次操作都要获取锁，单线程场景下白白浪费性能。

操作	ArrayList	Vector
单线程 add	100 ms	150 ms（锁开销）
多线程 add	不安全	安全但串行

什么时候用 Vector？ 基本不用了。需要线程安全用 Collections.synchronizedList() 或 CopyOnWriteArrayList。

Vector 扩容 2 倍 vs ArrayList 扩容 1.5 倍：

初始容量 10，添加 100 个元素：
ArrayList：10 → 15 → 22 → 33 → 49 → 73 → 109（6 次扩容）
Vector：   10 → 20 → 40 → 80 → 160（4 次扩容）

Vector 扩容次数少，但浪费更多空间。

四、LinkedList：链表的真相

LinkedList 是双向链表，每个节点存储前后指针：

private static class Node<E> {
    E item;
    Node<E> next;  // 后继 👈
    Node<E> prev;  // 前驱 👈
}

头插确实快：

// LinkedList.addFirst(e)
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;  // 👈 只改指针，O(1)
if (f == null) last = newNode;
else f.prev = newNode;

但中间插入没有你以为的那么快！

// LinkedList.add(index, element)
// 第一步：找到位置 —— O(n) 👈
Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;       // 从头遍历！
    } else {
        Node<E> x = last;
        for (int i = size-1; i > index; i--)
            x = x.prev;       // 从尾遍历！
    }
}
// 第二步：改指针 —— O(1)

链表插入"O(1)"说的是改指针那一步，找到位置还是要 O(n)！

随机访问更慢：

// LinkedList.get(index) → 从头/尾遍历找，O(n) 👈
// ArrayList.get(index) → 直接下标访问，O(1)

生活类比： LinkedList 像手拉手排队——找人得从头数（O(n)），但中间插入只需松手重拉（O(1) 改指针）。

五、实际性能测试对比

10 万次操作耗时（ms）

操作              ArrayList    LinkedList
─────────────────────────────────────────
尾部追加          8            12
头部插入          2500         5
随机访问(get)     2            45000
中间插入          1200         1800
遍历(for-each)    5            15

结论：

1. 尾部追加：ArrayList 更快（数组连续内存，CPU 缓存友好）
2. 头部插入：LinkedList 完胜
3. 随机访问：ArrayList 完胜（几千倍差距）
4. 中间插入：差不多！链表查找慢抵消了插入快的优势
5. 遍历：ArrayList 更快（CPU 缓存预取）

大多数场景下 ArrayList 更优——因为 CPU 缓存对连续内存的加成太大了。

三者性能对比 全景

ArrayList / Vector / LinkedList 性能对比 全景

底层结构
├── ArrayList ── Object[] 数组
├── Vector ── Object[] 数组 + synchronized
└── LinkedList ── 双向链表

时间复杂度
├── 随机访问 ── O(1) / O(1) / O(n)
├── 尾部添加 ── O(1)* / O(1)* / O(1)
├── 头部添加 ── O(n) / O(n) / O(1)
├── 中间插入 ── O(n) / O(n) / O(n)
└── *均摊

空间占用
├── ArrayList ── 紧凑，可能有预留空间
├── Vector ── 紧凑，预留更多（2 倍扩容）
└── LinkedList ── 每个节点额外 2 个指针（16 字节）

选型建议
├── 默认选 ArrayList ── 综合最优
├── 大量头插选 LinkedList ── 场景少见
├── 需要线程安全 → CopyOnWriteArrayList
└── 别用 Vector ── 已被淘汰

口诀：数组访问快如风，链表头插是强项，
      中间插入都挺慢，缓存友好数组赢，
      Vector 加锁已淘汰，ArrayList 是首选。

回答技巧与点评

标准回答

ArrayList 和 Vector 底层都是 Object[] 数组，LinkedList 是双向链表。ArrayList 随机访问 O(1) 极快，但头部插入 O(n) 慢；LinkedList 头部插入 O(1) 快，但随机访问 O(n) 慢；中间插入两者都是 O(n)。Vector 和 ArrayList 结构相同，但所有方法加了 synchronized，线程安全但性能差。实际开发中默认选 ArrayList，因为 CPU 缓存对连续内存的加成使它在大多数场景下更快；需要线程安全用 CopyOnWriteArrayList 而非 Vector。

加分回答

1. CPU 缓存的影响：ArrayList 的数组在内存中连续，CPU 可以预取（prefetch）数据到缓存行（通常 64 字节），一次加载多个元素。LinkedList 的节点在内存中分散，每次访问都可能缓存未命中。这就是为什么 ArrayList 遍历比 LinkedList 快好几倍——不是算法复杂度的差距，而是硬件层面的差距
2. LinkedList 的实际使用场景极少：如果需要频繁头插尾插，用 ArrayDeque（数组实现的双端队列）比 LinkedList 更快，因为数组连续内存+循环数组的设计避免了元素移动。LinkedList 在实际项目中几乎从不使用
3. fail-fast 机制：三个列表都有 modCount 机制，迭代过程中如果列表结构被修改（非迭代器的 remove/add），会抛 ConcurrentModificationException。这是"快速失败"策略——宁可报错也不默默产生错误结果

面试官点评

这道题考的是你对数据结构选型的理解。能说出"数组 vs 链表、随机访问 vs 头插"是基本要求，能讲清楚 LinkedList 中间插入也是 O(n)（查找抵消了插入优势）、CPU 缓存对连续内存的加成，才算及格。如果你能提到 CPU 缓存行、ArrayDeque 替代方案、fail-fast 机制，面试官会认为你不只会背复杂度，还理解底层硬件和工程实践。

原文阅读

---

内容有帮助？点赞、收藏、关注三连！评论区等你 💪