集合 - List

开篇：为什么需要集合框架？

学 Java 的第一天，你一定写过这样的代码：

int[] scores = new int[5];

数组简单、直接，但它有一个致命缺陷——大小是固定的。

想象一下，你开了一家奶茶店，开业前预估每天最多 5 个订单，于是准备了一个能放 5 张订单的盒子。结果开业当天来了 50 个顾客……盒子放不下，你只能眼睁睁看着顾客流失。

现实世界的数据量几乎从来都不是固定的——用户列表会增长，购物车商品会增减，日志条目会不断追加。我们需要一种能自动伸缩的容器，这就是 Java 集合框架诞生的原因。

数组的局限不止于此：

• 没有开箱即用的增删方法：想在中间插入一个元素？你得手动搬移后面所有元素。
• 缺少丰富的 API：查找、排序、去重、过滤……这些常见操作数组统统不支持，需要自己从零实现。
• 类型不够灵活：原始类型数组和对象数组是两套体系，泛型支持也不如集合友好。

Java 集合框架就是为了解决这些问题而设计的一整套容器类库。它不仅提供了动态伸缩的能力，还统一了接口规范，让不同实现之间可以无缝替换。

一、集合框架全景图

Java 集合框架的核心就两条线：单元素集合（Collection）和键值对集合（Map）。

简单理解各条线的定位：

• List：有序、可重复，就像一排编了号的座位。
• Set：无序（或有特定顺序）、不可重复，就像一堆不重样的扑克牌。
• Queue：先进先出（或按优先级出队），就像排队买票。
• Map：键值对映射，就像字典——通过"词条"找"释义"。

今天我们聚焦最常用的 List 家族——ArrayList 和 LinkedList。

二、ArrayList：动态数组

2.1 底层结构与扩容

ArrayList 的本质就是一个会自动变大的数组。

打个比方：你住在一间能放 10 箱书的小公寓。当你买到第 11 箱书时，不是往墙上凿个洞，而是直接搬到一间能放 15 箱书的大公寓，然后把旧书一箱箱搬过去。这就是 ArrayList 的扩容过程。

核心要点：

• 默认初始容量为 10（使用无参构造器时，第一次 add 时才真正分配）
• 容量不够时，新容量 = 旧容量 × 1.5（右移一位再加自身：oldCapacity + (oldCapacity >> 1)）
• 扩容本质是 Arrays.copyOf()，创建新数组再把旧数据复制过去
• 最大容量为 Integer.MAX_VALUE - 8（部分 JVM 实现需要在数组头部存储额外信息）

// 扩容核心源码（JDK 8）
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

为什么是 1.5 倍而不是 2 倍？这是时间和空间的折中。倍数太大浪费内存，倍数太小频繁扩容（搬家太频繁），1.5 倍是经过实践检验的甜蜜点。相比之下，旧时代的 Vector 每次扩容 2 倍，更加浪费。

搬家的代价

扩容时要复制整个旧数组，时间复杂度 O(n)。所以如果你提前知道数据量，用 new ArrayList<>(1000) 指定初始容量，可以避免多次"搬家"。这在批量数据处理中是一个重要的性能优化手段。

2.2 增删改查源码解析

理解了底层是数组之后，ArrayList 的所有行为都可以用"数组操作"来推导。

查询（get）—— O(1)

ArrayList 底层就是数组，通过下标直接定位元素，就像翻字典查页码一样快：

public E get(int index) {
    rangeCheck(index);         // 检查下标越界
    return elementData[index]; // 直接按下标取，一步到位
}

这就是数组最大的优势——随机访问。不管数组有 10 个元素还是 1000 万个元素，通过下标取值的速度完全一样。

修改（set）—— O(1)

同理，定位 + 替换，两步搞定：

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData[index];
    elementData[index] = element;
    return oldValue; // 返回被替换的旧值
}

尾部添加（add）—— 均摊 O(1)

大多数时候只需在末尾追加一个元素，非常快。偶尔触发扩容会慢一些，但均摊下来仍是 O(1)：

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 可能触发扩容
    elementData[size++] = e;          // 放到末尾
    return true;
}

中间插入（add(index, element)）—— O(n)

往数组中间插一个元素，后面所有元素都得往后挪一位。就像排队时有人插队，后面的人都要后退一步：

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    // 从 index 开始，所有元素后移一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

删除（remove）—— O(n)

删除后也要把后面的元素往前搬，和插入是镜像操作：

public E remove(int index) {
    rangeCheck(index);
    E oldValue = elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // 让 GC 回收
    return oldValue;
}

各操作复杂度速查

操作	时间复杂度	说明
get(index)	O(1)	数组下标直达
set(index, e)	O(1)	直接替换
add(e)（尾部）	均摊 O(1)	偶尔扩容 O(n)
add(index, e)	O(n)	需要搬移元素
remove(index)	O(n)	需要搬移元素
contains(o)	O(n)	线性扫描

2.3 RandomAccess 标记接口

ArrayList 实现了 RandomAccess 接口。这个接口没有任何方法，纯粹是一个标记，告诉使用者："我支持高效的随机访问，用 for 循环 + get(i) 遍历我最快。"

JDK 中的 Collections.binarySearch() 就会检查这个标记：

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
        return indexedBinarySearch(list, key);  // 用下标二分
    else
        return iteratorBinarySearch(list, key); // 用迭代器
}

如果集合支持 RandomAccess，就用下标二分查找；否则用迭代器逐步推进。这是一个典型的策略模式应用。

2.4 序列化的小心思

ArrayList 的元素数组被标记为 transient：

transient Object[] elementData;

这意味着默认序列化机制会跳过这个数组。但 ArrayList 并没有放弃序列化，而是自己重写了 writeObject 和 readObject，只序列化 size 个实际元素，而不是整个数组（数组可能有大量空位）。

private void writeObject(ObjectOutputStream s) throws IOException {
    int expectedModCount = modCount;
    s.defaultWriteObject();
    s.writeInt(size);
    // 只写 size 个元素，跳过空闲位
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

这就像搬家时只打包有东西的箱子，空箱子直接扔掉，到了新家再准备新箱子。一个容量 1000 但只存了 3 个元素的 ArrayList，序列化后只包含 3 个元素的数据，省了大量空间。

三、LinkedList：双向链表

3.1 结构与特点

如果说 ArrayList 是一栋公寓楼（通过门牌号直达），那 LinkedList 就是一列火车——每节车厢只知道自己的前一节和后一节是谁，要找第 N 节车厢，得从车头或车尾一节节数过去。

每个节点（Node）长这样：

private static class Node<E> {
    E item;       // 存储的数据
    Node<E> next; // 指向后一个节点
    Node<E> prev; // 指向前一个节点
}

LinkedList 维护了 first 和 last 两个指针分别指向头尾节点，因此头尾操作非常高效：

// 在链表尾部追加
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

操作	时间复杂度	说明
头尾增删	O(1)	直接修改指针，不需要搬移任何元素
中间增删	O(n)	先遍历找到位置（O(n)），再改指针（O(1)）
随机访问	O(n)	必须从头或尾一个个数过去
内存占用	较高	每个元素额外存两个指针引用

LinkedList 同时实现了 List 和 Deque 接口，所以它还能当双端队列用，提供 offerFirst()、offerLast()、peekFirst()、pollLast() 等方法。

用 LinkedList 实现 LRU 缓存

LinkedList 的一个经典应用场景是实现 LRU（最近最少使用）缓存淘汰算法：

public class LruCache<E> {
    private final int maxSize;
    private final LinkedList<E> list = new LinkedList<>();

    public LruCache(int maxSize) { this.maxSize = maxSize; }

    public void access(E e) {
        list.remove(e);       // 从当前位置移除
        list.addFirst(e);     // 放到头部（最近使用）
        if (list.size() > maxSize) {
            list.removeLast(); // 淘汰尾部（最久未使用）
        }
    }
}

每次访问一个元素就把它提到链表头部，尾部自然就是最久没访问的。缓存满了就砍掉尾巴。当然，生产环境通常用 LinkedHashMap 来实现 LRU，性能更好。

3.2 为什么实际开发中很少用？

很多教科书说"频繁增删用 LinkedList"，但现实往往是 ArrayList 几乎总是更好的选择。原因如下：

1. CPU 缓存不友好

ArrayList 的元素在内存中是连续的，CPU 读取一个元素时会把相邻元素一起加载到缓存行中（空间局部性），后续访问命中率极高。LinkedList 的节点散落在堆内存各处，几乎每次访问都是缓存未命中（cache miss），性能差距在大数据量下非常明显。

2. 中间插入也不一定快

LinkedList 虽然改指针是 O(1)，但"找到那个位置"本身就是 O(n)。加起来总操作还是 O(n)，和 ArrayList 的搬移操作在量级上没有本质区别。而 ArrayList 的 System.arraycopy() 是 native 方法，底层用 CPU 的内存批量复制指令实现，实际速度远超逐个遍历链表节点。

3. 内存开销大

每个 Node 除了存数据，还要存 prev 和 next 两个引用（64 位 JVM 上各 8 字节），再加上对象头（16 字节），一个 Node 对象的额外开销就有 32 字节。对于存储小对象（如 Integer），额外开销甚至超过数据本身。

实战建议

除非你的场景确实是高频地在头部或尾部增删（比如实现队列或栈），否则请优先使用 ArrayList。LinkedList 的作者 Joshua Bloch 本人都说过："I wrote it, and I never use it."

四、ArrayList vs LinkedList

一张表说清楚：

维度	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)，支持 RandomAccess	O(n)，需逐个遍历
尾部添加	均摊 O(1)	O(1)
中间插入/删除	O(n)，需搬移元素	O(n)，需先遍历定位
内存占用	紧凑，但可能有空闲槽位	每个节点额外 32+ 字节
CPU 缓存	友好（内存连续）	不友好（节点分散）
扩容	1.5 倍增长，需要复制	无需扩容
迭代器	Iterator + ListIterator	Iterator + DescendingIterator
额外能力	无	可当队列/双端队列使用
推荐程度	绝大多数场景首选	特定场景（队列/栈）才用

一句话总结：如果你不确定用哪个，就用 ArrayList。

五、迭代器与快速失败

5.1 Iterator 模式

Java 集合的遍历统一走 Iterator 接口，核心就三个方法：

public interface Iterator<E> {
    boolean hasNext();  // 还有没有下一个
    E next();           // 取下一个
    void remove();      // 删除当前元素（安全删除）
}

为什么不直接用 for 循环加下标？因为不是所有集合都有"下标"的概念。LinkedList、HashSet、TreeSet……它们的内部结构各不相同，但通过 Iterator 统一了遍历方式。这就是迭代器模式的价值——屏蔽内部实现差异，提供统一的遍历协议。

我们平时写的增强 for 循环（foreach），编译后其实就是 Iterator：

// 你写的
for (String name : names) {
    System.out.println(name);
}

// 编译器翻译成
Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
    System.out.println(name);
}

所以 foreach 只是一颗语法糖，底层仍然是 Iterator 在工作。

5.2 fail-fast 机制

fail-fast（快速失败）是 Java 集合的一种自我保护机制。

想象一个场景：你正在数书架上的书（遍历），你的室友突然从中间抽走了一本（修改集合结构）。你数到后面发现对不上了——与其给出错误结果，不如直接报错。这就是 fail-fast 的思想。

原理：ArrayList 内部维护了一个 modCount（修改计数器），每次 add / remove 都会让它 +1。创建 Iterator 时，会把当前 modCount 快照为 expectedModCount。每次调用 next() 都会检查两者是否相等：

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

如果发现 modCount 变了但 expectedModCount 没跟上，说明有人在遍历期间偷偷修改了集合结构，立即抛出 ConcurrentModificationException。

经典踩坑：在 foreach 中调用 list.remove() 会触发 ConcurrentModificationException：

// 错误写法——运行时直接炸
for (String name : names) {
    if ("Hollis".equals(name)) {
        names.remove(name); // 绕过了 Iterator，modCount 和 expectedModCount 不一致
    }
}

为什么会这样？foreach 底层用的是 Iterator，但 names.remove() 直接操作了 ArrayList，只更新了 modCount，没有同步更新 Iterator 内部的 expectedModCount。下一次 next() 检查时就会发现不一致。

正确做法：

// 方式一：使用 Iterator.remove()（经典做法）
Iterator<String> it = names.iterator();
while (it.hasNext()) {
    if ("Hollis".equals(it.next())) {
        it.remove(); // 会同步更新 expectedModCount，安全
    }
}

// 方式二：Java 8+ removeIf（最推荐，简洁）
names.removeIf("Hollis"::equals);

// 方式三：Stream 过滤生成新集合（不修改原集合）
List<String> filtered = names.stream()
    .filter(n -> !"Hollis".equals(n))
    .collect(Collectors.toList());

// 方式四：倒序 for 循环（简单但仅适用于 List）
for (int i = names.size() - 1; i >= 0; i--) {
    if ("Hollis".equals(names.get(i))) {
        names.remove(i);
    }
}

注意

fail-fast 不仅在多线程下触发，单线程中用 foreach + list.remove() 同样会触发。这是一个非常常见的面试考点。

5.3 CopyOnWriteArrayList

在并发场景下，连 Iterator.remove() 也不够用了。这时候可以用 CopyOnWriteArrayList——一个写时复制的线程安全 List。

它的核心策略用一句话概括：读操作无锁直读，写操作加锁复制。

来看看 add 方法的源码：

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();
    }
}

而读操作完全无锁：

public E get(int index) {
    return get(getArray(), index); // 直接读，不加锁
}

CopyOnWriteArrayList vs Vector

维度	Vector	CopyOnWriteArrayList
加锁策略	所有方法加 synchronized	只有写操作加锁
读写关系	读写互斥	读写不互斥
适用场景	几乎没有	读多写少
迭代器	fail-fast	fail-safe（快照遍历）
性能	差（读也要抢锁）	读性能极好，写性能一般

适用场景：读多写少（如白名单、配置列表、监听器列表）。写操作频繁时，频繁复制数组的开销会很大，就不适合了。

fail-safe

CopyOnWriteArrayList 的迭代器遍历的是创建迭代器那一刻的数组快照，遍历期间即使其他线程修改了集合，也不会抛 ConcurrentModificationException。这种机制叫 fail-safe。代价是遍历期间看不到其他线程的最新修改——这是最终一致性，而非强一致性。

六、subList 的坑

List.subList() 返回的不是一个新的 List，而是原 List 的一个视图（内部类 SubList）。SubList 没有自己的数据存储，它直接引用原 List 的底层数组，只是记住了偏移量和长度。

理解这一点可以避免很多线上 bug：

List<String> original = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
List<String> sub = original.subList(1, 4); // [B, C, D]

坑 1：不能强转为 ArrayList

SubList 是 ArrayList 的内部类，和 ArrayList 之间没有继承关系：

ArrayList<String> wrong = (ArrayList<String>) sub; // ClassCastException!

坑 2：修改视图会影响原 List（反之亦然）

sub.set(0, "X");
System.out.println(original); // [A, X, C, D, E] —— 原 List 也变了！

坑 3：修改原 List 结构后操作视图会炸

original.add("F"); // 原 List 结构变了
sub.get(0);        // ConcurrentModificationException!

原因是 SubList 在创建时记录了 modCount，如果原 List 的 modCount 变了，SubList 就认为自己失效了。

安全用法——如果需要独立子列表，创建一个副本：

List<String> safeCopy = new ArrayList<>(original.subList(1, 4));
// 或者用 Stream
List<String> safeCopy2 = original.stream().skip(1).limit(3).collect(Collectors.toList());

七、常见面试题精选

Q1：ArrayList 和 LinkedList 的区别？什么时候用哪个？

ArrayList 基于动态数组，随机访问 O(1)，中间增删 O(n)；LinkedList 基于双向链表，头尾增删 O(1)，随机访问 O(n)。但由于 CPU 缓存局部性、内存开销、System.arraycopy() 的底层优化等因素，绝大多数场景下 ArrayList 都更快。只有需要频繁头尾操作（如实现队列）时才考虑 LinkedList。

Q2：ArrayList 扩容机制是怎样的？

无参构造器创建的 ArrayList 初始为空数组，第一次 add 时分配容量 10。此后容量不足时扩为原来的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。扩容通过 Arrays.copyOf() 创建新数组并复制元素。所以如果提前知道数据量，用 new ArrayList<>(expectedSize) 指定初始容量可以减少扩容次数，提升性能。

Q3：为什么 ArrayList 的 elementData 用 transient 修饰？

因为 ArrayList 的数组通常有空闲位置（容量 > size），直接序列化整个数组会序列化大量 null 值，浪费空间和带宽。ArrayList 自定义了 writeObject/readObject，只序列化 size 个实际元素。

Q4：什么是 fail-fast？如何避免 ConcurrentModificationException？

fail-fast 是集合在检测到遍历期间被意外修改时，立刻抛异常的保护机制。它通过比较 modCount 和 expectedModCount 来实现。避免方式：使用 Iterator.remove()、removeIf()、Stream 过滤，或使用 CopyOnWriteArrayList 等 fail-safe 容器。

Q5：CopyOnWriteArrayList 和 Vector 有什么区别？

都是线程安全的 List，但策略完全不同。Vector 对所有方法（包括读）加 synchronized，读写互斥，性能差；CopyOnWriteArrayList 读无锁、写时复制，读写不互斥，适合读多写少。另外 Vector 同样无法保证复合操作（如"先检查再操作"）的线程安全性。

Q6：如何让一个集合变成线程安全的？

四种常见方式：

1. 外部加锁：用 synchronized 或 ReentrantLock 包裹读写操作
2. Collections 包装：Collections.synchronizedList(new ArrayList<>())，所有方法加 synchronized
3. 并发容器：CopyOnWriteArrayList（读多写少）
4. 不可变集合：List.of()（Java 9+）或 Guava ImmutableList，天然线程安全

小结

记住三个核心结论：

1. 日常开发首选 ArrayList——它在绝大多数场景下都是最优解，别被教科书的"链表增删快"误导。
2. 遍历时修改集合，用 removeIf 或 Iterator.remove()——远离 ConcurrentModificationException。
3. 线程安全场景用 CopyOnWriteArrayList——别用 Vector，那是上个世纪的产物了。