ArrayList、LinkedList 与 Vector 的区别？

结论先行：三者都实现了 List，差异集中在三处——底层结构（连续数组 / 双向链表）、扩容策略（1.5 倍 / 2 倍）、线程安全（无锁 / 方法级同步）。日常默认选 ArrayList；LinkedList 的优势只在“频繁头尾增删 + 当双端队列用”；Vector 是 JDK 1.0 的遗留类，锁粒度粗、扩容浪费，已不推荐在新代码中使用。

1. 结构决定复杂度

ArrayList（连续数组，随机访问靠地址计算）
+----+----+----+----+
| A  | B  | C  | D  |
+----+----+----+----+
  0    1    2    3      get(i) = elementData[i]

LinkedList（双向链表，每个节点存前后指针）
null <- [prev|A|next] <-> [prev|B|next] <-> [prev|C|next] -> null
          ^                                        ^
         head                                     tail

2. 扩容：1.5 倍与 2 倍的取舍

// JDK 8 ArrayList.grow()：新容量 = 旧容量 + 旧容量的一半
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;                      // 单次 addAll 撑大时兜底
    }
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// Vector.grow()：capacityIncrement 为 0 时直接翻倍
int newCapacity = oldCapacity + ((capacityIncrement > 0)
        ? capacityIncrement : oldCapacity); // 默认 2 倍

1.5 倍的空间浪费更小，但同样元素量下拷贝次数略多；2 倍拷贝次数少，却更容易出现“申请了用不完”的数组。对现代 JVM 来说，差距远小于一次业务查询，真正的成本在于能否预估容量。

3. 代码：三者行为对照

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

public class ListCompare {
    public static void main(String[] args) {
        List<String> array = new ArrayList<>(4);   // 预分配，避免前几次扩容
        List<String> linked = new LinkedList<>();
        List<String> vector = new Vector<>(4);

        array.add("a");
        linked.add("a");
        vector.add("a");

        // 头部插入：ArrayList 需要整体右移，LinkedList 只改两个指针
        array.add(0, "head");
        linked.add(0, "head");
        vector.add(0, "head");

        // Vector 的每个公开方法都带 synchronized，单线程也要付出锁开销
        System.out.println(vector.get(0)); // 输出：head
        System.out.println(array instanceof java.util.RandomAccess); // 输出：true
    }
}

4. Vector 的同步保护不了复合操作

// 错误：contains 与 add 之间存在竞态，别的线程可能刚好插入同一个值
if (!vector.contains("x")) {
    vector.add("x");
}

// 正确：由调用方锁住同一个对象，把“判断 + 写入”包成一个原子段
synchronized (vector) {
    if (!vector.contains("x")) {
        vector.add("x");
    }
}

即使换成 Collections.synchronizedList(new ArrayList<>())，单次方法调用是原子的，复合操作依旧要外部加锁；迭代时也要手动 synchronized，否则同样会抛 ConcurrentModificationException。

5. 选型建议

• 默认 ArrayList：已知规模就 new ArrayList<>(n)，一次分配到位。
• 栈 / 队列语义用 ArrayDeque：它比 LinkedList 更快、内存更省，LinkedList 只在需要 List 接口的同时又要双端操作时才有存在感。
• 读多写少的并发场景用 CopyOnWriteArrayList：写时复制，读不加锁，适合配置、监听器列表。
• 老系统里的 Vector：可以保留，但新代码不要再用。

常见追问

• RandomAccess 是空标记接口，Collections.binarySearch 靠它决定用下标还是迭代器遍历。
• subList 返回的是视图，对子列表做结构性修改会同步影响原列表，甚至抛 ConcurrentModificationException。
• Arrays.asList 返回定长列表，add / remove 抛 UnsupportedOperationException。
• LinkedList 每个节点除了数据还要存两个引用和对象头，节点数量大时内存开销明显高于数组。
• 遍历方式要匹配结构：ArrayList 用下标 for，LinkedList 用迭代器，避免 O(n²)。
• 删除中间元素时，ArrayList 触发 System.arraycopy，LinkedList 先花 O(n) 定位再改指针。
• 三个类都不是线程安全的（Vector 除外），并发写请换并发容器。

小结

ArrayList 胜在随机访问与内存紧凑，扩容 1.5 倍、能预估就预估；LinkedList 只在头尾增删和双端队列场景有价值，别被“增删快”这句话带偏；Vector 用整表同步换安全，代价是并发吞吐和扩容浪费，属于该被淘汰的遗留实现。面试作答时按“结构 → 复杂度 → 扩容 → 线程安全”四步展开，基本不会漏点。