Java集合：List实现类深度对比

面试官通过这道题主要想考察你：

一、标准回答

List 接口是 Java 集合框架的三大核心接口之一（另外两个是 Set 和 Map），代表一个有序、可重复的元素序列。常用的 List 实现类包括：

• ArrayList：基于动态数组（Object[]），支持快速随机访问（O(1)），非尾部增删需要移动元素（平均 O(n)），线程不安全，但遍历效率高，是日常开发首选。
• LinkedList：基于双向链表（Node 节点），两端的增删复杂度为 O(1)，查询为 O(n)，同时实现了 Deque 接口，可当作队列、栈、双端队列使用。
• Vector：古老的线程安全容器，所有方法都用 synchronized 修饰，性能极低，官方已明确建议弃用。
• Stack：继承自 Vector，模拟栈结构，同样不推荐使用，应改用 Deque 的实现。
• CopyOnWriteArrayList：并发容器，写操作会复制整个底层数组（写时复制），读操作完全无锁，适合“读多写少”的并发场景。
• 同步包装器：通过 Collections.synchronizedList 可以将任何 List 包装成线程安全的视图，但遍历时仍需手动同步。

二、核心原理

下图从底层数据结构、扩容机制、线程安全及迭代器行为四个维度对主流实现类进行对比：

LinkedList 节点结构：

private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

CopyOnWriteArrayList 写操作关键逻辑：

public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}

此外，所有线程不安全的 List 都依赖 modCount 字段记录结构修改次数。每当 List 发生结构修改（add/remove/clear 等改变元素数量的操作），modCount 就会自增 1。迭代器在创建时会用 expectedModCount 字段保存当时的 modCount 值，之后每次执行 next()、remove() 等操作前，都会调用 checkForComodification() 方法比对两者是否一致——若不一致则立即抛出 ConcurrentModificationException，这就是 fail‑fast 机制。

以 ArrayList 内部类 Itr 为例，核心检查逻辑如下：

private class Itr implements Iterator<E> {
int cursor; // 下一个返回元素的索引
int lastRet = -1; // 上一次返回元素的索引，-1 表示刚删除
int expectedModCount = modCount; // 创建时快照

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

public E next() {
checkForComodification(); // 每次取元素前检查
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); // 删除前也检查
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount; // 迭代器自己的 remove 会同步
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}

注意：迭代器自身的 remove() 方法在删除元素后，会重新同步 expectedModCount = modCount，因此只有使用迭代器自己的 remove 才是安全的；如果在迭代过程中直接调用 list.remove()，只会修改外部的 modCount，迭代器内部的 expectedModCount 不会同步，下次 next() 就会触发异常。

三、应用场景

日常开发的选择原则：

• ArrayList：适用于频繁随机查询、遍历的场景，例如列表页展示、数据导出、批量处理。大多数业务代码中，只要没有特殊需求，直接使用 ArrayList 即可。
• LinkedList：适合需要大量头尾插入/删除，或需要队列/栈语义的场景，例如消息缓冲队列、LRU 缓存（利用头尾快速删除旧元素）、递归栈模拟。但要注意，大部分情况下 ArrayList 的尾插效率并不比 LinkedList 差，因为 ArrayList 的批量数据移动会受益于现代 CPU 的缓存行。
• CopyOnWriteArrayList：适合“读多写少”的并发场景，例如系统白名单/黑名单缓存、事件监听器列表、配置中心中加载的配置项集合。

主流框架中的落地案例：

• Spring：BeanPostProcessor、ApplicationListener 等监听器列表内部使用 CopyOnWriteArrayList 存储，既保证线程安全，又允许大量读操作无锁执行。
• MyBatis：结果集映射时，使用 ArrayList 存放每一行的结果对象，利用其顺序存储和快速遍历特性。
• RocketMQ：消息存储的队列管理、消费进度下标维护大量使用 ArrayList。
• Java ClassLoader：每个 ClassLoader 在加载类时会把已加载的类缓存到 ArrayList 中，以便快速查找。
• HikariCP 连接池：使用 CopyOnWriteArrayList 保存连接状态快照，减少锁竞争。

四、使用方式

以下代码覆盖各实现类的常见操作与并发注意事项。

// ===== ArrayList 基本使用与遍历性能对比 =====
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add(1, "C"); // 指定位置插入
String item = list.get(0); // O(1)
list.remove(1); // 删除，后续元素前移

// 遍历方式性能对比（ArrayList 实现了 RandomAccess，推荐普通 for）
for (int i = 0; i < list.size(); i++) { … } // 最快
for (String s : list) { … } // 中等
list.forEach(System.out::println); // 中等
Iterator<String> it = list.iterator();
while (it.hasNext()) { it.next(); } // 次于普通 for

// 批量操作示例
list.addAll(Arrays.asList("D", "E", "F"));
list.sort(String::compareTo); // lambda 比较器
List<String> sub = list.subList(0, 3); // 视图，修改会同步回原列表

// 安全删除元素（不能在 foreach 中直接 list.remove）
it = list.iterator();
while (it.hasNext()) {
String s = it.next();
if (s.equals("B")) {
it.remove(); // 正确用法
}
}

// ===== LinkedList 用作队列、栈和双端队列 =====
Deque<String> deque = new LinkedList<>();
deque.offerFirst("head");
deque.offerLast("tail");
String first = deque.pollFirst(); // 弹出头部

// 作为栈使用
deque.push("element");
String top = deque.pop();

// 模拟 LRU 缓存淘汰（利用 removeLast）
LinkedHashSet<String> lhs = new LinkedHashSet<>();
// … 这里仅示意思路，实际应继承 LinkedHashMap
lhs.remove(lhs.iterator().next()); // 删除最老元素

// ===== CopyOnWriteArrayList 并发场景 =====
CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();
cowList.add("item");

// 遍历时无需加锁，迭代器持有快照
for (String s : cowList) {
System.out.println(s);
// 迭代过程中修改不影响当前快照，但不会立即反映到迭代器
cowList.add("new");
}
// 写操作由 ReentrantLock 保证互斥，适合读多写少

// ===== 线程安全包装示例 =====
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
syncList.add("safe");
// 遍历时必须手动同步
synchronized (syncList) {
for (String s : syncList) {
// …
}
}
// 不推荐，性能远不如 CopyOnWriteArrayList 或 JUC 容器

五、扩展延伸

• ArrayList 的 RandomAccess 标记：ArrayList 实现了 RandomAccess 接口，遍历时使用下标循环效率最高；LinkedList 未实现该接口，应使用迭代器或 for‑each 循环，否则 O(n²) 的噩梦。
• subList 陷阱：list.subList(from, to) 返回的是原列表的视图，对子列表的修改会直接影响原列表，且原列表的结构变化会导致子列表失效。最好的办法就是是拷贝子列表：new ArrayList<>(list.subList(0, 5))。
• 排序：Collections.sort(list) 要求元素实现 Comparable；list.sort(Comparator) 更灵活，支持 Lambda。
• 不可变 List：Java 9 引入 List.of()，Guava 提供 ImmutableList，这些不可变集合线程安全、内存紧凑，适合常量配置。
• 数组与 List 互转：list.toArray() 和 Arrays.asList()。后者返回的 List 长度固定，不可增删，但支持修改元素值。
• 并行流与 List：使用 parallelStream() 时，底层将 List 转换为 ArrayListSpliterator 进行分割，如果使用 LinkedList 会导致拆分效率极低，因此并行流场景应优先使用 ArrayList。
• List 去重：可用 list.stream().distinct().collect(Collectors.toList()) 或转换为 LinkedHashSet，在去重的同时，还能保证元素的存储顺序与插入顺序一致。

六、面试追问