Java List 核心数据结构解析：ArrayList、LinkedList 与线程安全

Posted 2023-08-16 Updated 17 days ago

By Ryan Chen

38~50 min read

Java List 核心数据结构解析：ArrayList、LinkedList 与线程安全

前言

List 是 Java 集合框架中最常用的接口之一。它表示一组有序元素，允许重复元素，并且可以通过下标访问。

日常开发中，最常见的选择是 ArrayList。但在面试、性能优化和并发场景中，经常还会遇到这些问题：

ArrayList 和 LinkedList 到底有什么区别？
ArrayList 的 size 和容量是一回事吗？
为什么说 LinkedList 不一定适合频繁插入删除？
遍历时为什么会出现 ConcurrentModificationException？
多线程环境下应该用 synchronizedList、Vector，还是 CopyOnWriteArrayList？

本文围绕 Java List 的核心实现和线程安全方案做一次系统梳理。

List 接口是什么？

java.util.List 是一个有序集合接口，核心特点包括：

有序：元素按照插入顺序或指定位置保存；
可重复：允许多个相同元素；
可按下标访问：支持 get(index)、set(index, element)；
通常允许 null：具体是否允许取决于实现；
支持位置相关操作：例如 add(index, element)、remove(index)。

从 Java 21 开始，List 也属于 SequencedCollection 体系，因此具备更明确的首尾顺序语义。不过日常使用中，大家仍然主要通过 List、ArrayList、LinkedList 这些类型来操作。

常见实现包括：

实现类	底层结构	是否线程安全	典型用途
`ArrayList`	动态数组	否	随机访问、遍历、尾部追加
`LinkedList`	双向链表	否	双端队列、频繁头尾操作
`Vector`	动态数组	是，方法级同步	旧代码兼容，不推荐新代码优先使用
`CopyOnWriteArrayList`	写时复制数组	是	读多写少、遍历多修改少
`Collections.synchronizedList`	同步包装器	是	对普通 List 做同步包装

ArrayList：基于动态数组的 List

ArrayList 是 Java 中最常用的 List 实现。它的底层可以理解为一个可以自动扩容的数组。

List<String> list = new ArrayList<>();
list.add("Java");
list.add("MySQL");
list.add("Redis");

System.out.println(list.get(0)); // Java

ArrayList 的特点

ArrayList 的优势：

按下标访问快，get(index) 是 O(1)；
遍历效率高，数组连续存储，CPU 缓存友好；
尾部追加通常很快，均摊 O(1)；
使用简单，是绝大多数场景的默认选择。

ArrayList 的劣势：

中间插入或删除需要移动元素；
扩容时需要创建新数组并复制元素；
不是线程安全的；
删除大量元素后，内部数组容量不会自动缩小，除非调用 trimToSize()。

size 与 capacity 的区别

ArrayList 有两个容易混淆的概念：

概念	含义	是否可直接获取
`size`	当前实际元素个数	可以，`list.size()`
`capacity`	内部数组容量	没有公开 API 直接获取

示例：

ArrayList<String> list = new ArrayList<>(20);

System.out.println(list.size()); // 0

这里 new ArrayList<>(20) 表示给内部数组预留初始容量，但当前元素数量仍然是 0。

也就是说：

list.size()

获取的是元素个数，不是内部数组容量。

如果提前知道大概会存储多少元素，可以通过构造方法或 ensureCapacity() 减少扩容次数：

ArrayList<String> list = new ArrayList<>(1000);

ArrayList<String> list2 = new ArrayList<>();
list2.ensureCapacity(1000);

ArrayList 扩容机制

当 ArrayList 当前容量不足以容纳新元素时，会触发扩容。扩容过程大致是：

添加元素
  ↓
检查容量是否足够
  ↓
容量不足，创建更大的新数组
  ↓
复制旧数组元素到新数组
  ↓
把内部引用指向新数组
  ↓
写入新元素

在 OpenJDK 的常见实现中，扩容通常约为原容量的 1.5 倍。但这属于具体实现细节，不是 List 接口规范保证。写业务代码时，不应依赖具体扩容倍数。

如果频繁向一个很大的 ArrayList 中追加元素，而没有提前设置容量，就可能产生多次数组复制。对于明确知道数据规模的场景，建议设置合适的初始容量。

LinkedList：基于双向链表的 List

LinkedList 底层是双向链表，每个节点保存：

前驱节点引用 + 当前元素 + 后继节点引用

它既实现了 List，也实现了 Deque，因此既可以当列表使用，也可以当双端队列使用。

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.addFirst("First");
list.addLast("Last");

System.out.println(list.removeFirst());

LinkedList 的特点

LinkedList 的优势：

在已定位到节点时，插入和删除节点本身是 O(1)；
头部、尾部插入删除方便；
天然适合作为队列或双端队列使用。

LinkedList 的劣势：

按下标访问需要从头或尾遍历，复杂度是 O(n)；
每个节点都要保存前后指针，内存开销更大；
节点分散在堆内存中，CPU 缓存友好性差；
遍历性能通常不如 ArrayList。

因此，很多人说“频繁插入删除用 LinkedList”其实并不完整。

更准确的说法是：

如果已经持有节点位置，链表插入删除很快；但如果需要先按下标查找位置，那么定位成本仍然是 O(n)。在大多数业务场景中，ArrayList 往往比 LinkedList 更常用、更快。

ArrayList 与 LinkedList 对比

操作	ArrayList	LinkedList
按下标访问 `get(i)`	O(1)	O(n)
尾部追加 `add(e)`	均摊 O(1)	O(1)
头部插入	O(n)，需要移动元素	O(1)
中间插入	O(n)，需要移动元素	定位 O(n)，插入 O(1)
中间删除	O(n)，需要移动元素	定位 O(n)，删除 O(1)
遍历	快，缓存友好	相对慢，节点分散
内存占用	较低	较高，每个节点有前后指针
适合场景	随机访问、遍历、尾部追加	队列、双端队列、头尾操作

实际选择建议：

默认优先使用 ArrayList；
需要队列 / 双端队列语义时，优先考虑 ArrayDeque；
只有确实需要链表特性时，再考虑 LinkedList。

泛型与类型安全

Java 中的 List<E> 通过泛型在编译期约束元素类型。

List<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
// names.add(1); // 编译错误

需要注意，Java 的集合本质上保存的是对象引用。如果使用 List<Object>，确实可以放入不同类型对象：

List<Object> list = new ArrayList<>();
list.add("hello");
list.add(100);
list.add(true);

但这通常不推荐，因为读取时需要类型判断和强制转换，容易降低类型安全性。

更推荐的方式是：

业务数据结构明确时，使用具体泛型；
多种类型有共同父类或接口时，抽象出统一父类型；
不要为了“方便”滥用原始类型 List 或 List<Object>。

常见遍历方式

1. 普通 for 循环

适合需要下标的场景。

List<String> list = List.of("a", "b", "c");

for (int i = 0; i < list.size(); i++) {
    System.out.println(i + ": " + list.get(i));
}

对 ArrayList 来说，按下标访问很快；但对 LinkedList 来说，循环中反复 get(i) 可能退化为 O(n²)，不推荐。

2. enhanced for 循环

适合只读遍历。

for (String item : list) {
    System.out.println(item);
}

3. Iterator

适合遍历过程中安全删除当前元素。

List<String> list = new ArrayList<>(List.of("a", "b", "c"));

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String value = iterator.next();
    if ("b".equals(value)) {
        iterator.remove();
    }
}

4. ListIterator

ListIterator 支持双向遍历，并支持在遍历过程中添加、修改元素。

ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
    String value = iterator.next();
    iterator.set(value.toUpperCase());
}

5. Stream API

Java 8 引入 Stream API 后，可以用声明式方式处理集合。

List<Integer> numbers = List.of(3, 1, 2, 5, 4);

numbers.stream()
        .filter(n -> n > 2)
        .sorted()
        .map(n -> n * 10)
        .forEach(System.out::println);

Stream 适合表达过滤、映射、排序、聚合等操作，但不要为了使用 Stream 而牺牲可读性。

fail-fast 与 ConcurrentModificationException

ArrayList、LinkedList 的迭代器通常是 fail-fast 的。

也就是说，如果在迭代过程中，不通过迭代器自身方法，而是直接修改 List 的结构，可能会抛出 ConcurrentModificationException。

错误示例：

List<String> list = new ArrayList<>(List.of("a", "b", "c"));

for (String item : list) {
    if ("b".equals(item)) {
        list.remove(item); // 可能抛出 ConcurrentModificationException
    }
}

推荐写法：

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    if ("b".equals(iterator.next())) {
        iterator.remove();
    }
}

需要注意：fail-fast 是一种尽早暴露并发修改问题的机制，但它不是并发安全保证。不能依赖 ConcurrentModificationException 来实现程序正确性。

排序与常用操作

Collections.sort

List<Integer> list = new ArrayList<>(List.of(3, 1, 2));
Collections.sort(list);
System.out.println(list); // [1, 2, 3]

List.sort

Java 8 之后，也可以直接使用 List.sort()：

list.sort(Integer::compareTo);

自定义排序

List<String> names = new ArrayList<>(List.of("Tom", "Alice", "Bob"));

names.sort(Comparator.comparingInt(String::length));
System.out.println(names);

不可变 List

Java 9 之后可以使用 List.of() 创建不可变列表：

List<String> list = List.of("a", "b", "c");
// list.add("d"); // UnsupportedOperationException

它适合配置项、常量集合等不会修改的场景。

多线程环境下的 List

ArrayList 和 LinkedList 都不是线程安全的。如果多个线程同时修改同一个 List，可能出现数据错乱、元素丢失、异常等问题。

常见解决方案包括：

Collections.synchronizedList()；
CopyOnWriteArrayList；
Vector；
外部加锁；
使用更合适的并发容器或队列。

Collections.synchronizedList

Collections.synchronizedList() 可以把一个普通 List 包装成同步 List。

List<String> list = Collections.synchronizedList(new ArrayList<>());

list.add("a");
list.add("b");

单个方法调用是同步的，但遍历时要特别注意：

synchronized (list) {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

这是官方文档中特别强调的点：遍历 synchronizedList 时，需要手动对返回的 List 加锁，否则仍然可能出现并发修改问题。

适用场景：

并发程度不高；
写操作和读操作都需要同步；
希望在现有 ArrayList 基础上快速增加同步保护。

不足：

粗粒度锁，竞争激烈时性能一般；
复合操作仍需要额外同步；
遍历时容易忘记手动加锁。

CopyOnWriteArrayList

CopyOnWriteArrayList 是 java.util.concurrent 包中的线程安全 List。

它的核心思想是：

读操作不加锁，写操作复制一份新的底层数组。

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("a");
list.add("b");

for (String item : list) {
    System.out.println(item);
}

它的特点：

适合读多写少；
遍历时基于快照，不会抛出 ConcurrentModificationException；
迭代器不会反映创建之后的修改；
写操作成本高，因为每次写都要复制数组；
不适合大列表频繁写入。

典型场景：

配置列表；
监听器列表；
黑白名单；
读远多于写的共享数据。

Vector

Vector 是早期 Java 提供的线程安全动态数组。它的大多数方法都使用 synchronized 修饰。

Vector<String> vector = new Vector<>();
vector.add("a");
vector.add("b");

虽然 Vector 是线程安全的，但新代码通常不优先选择它，原因是：

API 较旧；
方法级同步粒度较粗；
复合操作仍然可能需要额外同步；
现代代码中通常更倾向于使用 ArrayList + 外部同步、Collections.synchronizedList() 或 CopyOnWriteArrayList。

如何选择 List 实现？

可以按下面的规则选择：

场景	推荐选择
默认业务开发	`ArrayList`
需要大量随机访问	`ArrayList`
主要是遍历和尾部追加	`ArrayList`
需要双端队列	优先 `ArrayDeque`，必要时 `LinkedList`
读多写少且多线程	`CopyOnWriteArrayList`
普通 List 需要简单同步	`Collections.synchronizedList()`
旧代码兼容	`Vector`
高频并发生产消费	考虑 `BlockingQueue`、`ConcurrentLinkedQueue` 等队列

一句话总结：

单线程或普通业务默认用 ArrayList；读多写少并发场景用 CopyOnWriteArrayList；不要因为“插入删除多”就盲目选择 LinkedList。

常见误区

误区一：LinkedList 插入删除一定比 ArrayList 快

不一定。

如果已经定位到节点，链表插入删除确实快；但如果需要按下标找到位置，LinkedList 仍然要遍历，整体可能更慢。

误区二：size 就是 ArrayList 的容量

不是。

size 是元素个数，capacity 是内部数组容量。ArrayList 没有公开 API 直接返回 capacity。

误区三：synchronizedList 遍历时一定安全

不一定。

单个方法调用有同步保护，但遍历需要手动加锁。

误区四：CopyOnWriteArrayList 适合所有并发场景

不适合。

它适合读多写少，不适合写频繁或数据量很大的场景。

总结

Java List 是一个有序、可重复、可按下标访问的集合接口。理解它的关键不是背 API，而是理解不同实现背后的数据结构和成本。

ArrayList 基于动态数组，随机访问和遍历性能好，是默认首选；
LinkedList 基于双向链表，适合双端队列语义，但随机访问差、内存开销高；
size 表示元素数量，capacity 是内部数组容量，二者不是一回事；
fail-fast 迭代器可以帮助尽早发现结构性并发修改，但不是线程安全机制；
Collections.synchronizedList() 需要注意遍历时手动加锁；
CopyOnWriteArrayList 适合读多写少，写多场景要谨慎；
Vector 是历史遗留线程安全 List，新代码通常不优先选择。

实际开发中，优先选择简单、稳定、符合访问模式的数据结构，往往比追求“理论上某个操作 O(1)”更重要。

参考资料

Java

Java Java 集合 List ArrayList LinkedList CopyOnWriteArrayList 线程安全数据结构

License: CC BY 4.0