Software Systems Atlas

中文

English

中文

English

主题

第 1 卷 / 第 10 章 / 第 2 课

10.2 List 详解 ​

这是集合框架入门后的第二站。用约 35 分钟跑完 Java 17 示例，你会看清 List 的实现成本、视图与副本，也能在遍历时安全地删改元素。

先按操作模式选择实现 ​

领料记录要按顺序追加、读取第几条，并保留同一个人的多次申请。这些动作都符合 List 的语义：保留遭遇顺序、允许重复、支持位置访问。实现选择还要看动作分布。多数记录在末尾追加并按索引读取时，ArrayList 的连续引用数组很合适；若把 List 当作两端队列，LinkedList 虽能工作，ArrayDeque 往往表达得更准确；它实现 Deque 而非 List，切换时也应调整变量接口。

1. ArrayList 管理可增长的引用数组 ​

java
List<String> claims = new ArrayList<>();
claims.add("领料单-1");
claims.add("领料单-2");
claims.add(0, "紧急单");

ArrayList 的可观察契约包括：

  • get(index) 与 set(index, value) 是 O(1)；
  • 尾部 add(value) 是摊销 O(1)；
  • 中间插入或删除需要移动后续引用，是 O(n)；
  • indexOf、contains 按 equals 线性查找，是 O(n)。

内部数组装满时，JDK 会分配更大存储并复制元素。增长公式、空列表何时首次分配，以及内部字段都属于实现细节，Java API 没有承诺“固定增长 1.5 倍”。应用代码应依赖摊销复杂度，而不是某个 JDK 源码常量。

已知规模时可给构造器一个容量估计：

java
List<Order> orders = new ArrayList<>(expectedCount);

容量不是 size。new ArrayList<>(1000) 只预留存储空间，size() 仍为 0；它也不能从接口层保证“零次扩容”，因为实际元素数可能超过估计。持有具体 ArrayList 类型时还可调用 ensureCapacity，但通常不必为了容量暴露实现类型给调用方。

2. LinkedList 的 O(1) 有位置前提 ​

LinkedList 为每个元素维护前驱与后继链接：

java
Deque<String> waiting = new LinkedList<>();
waiting.addFirst("张三");
waiting.addLast("李四");

已知头尾节点时，两端插入和删除是 O(1)。list.add(index, value) 仍要先走到 index，定位成本为 O(n)。仅仅“经常在中间插入”并不足以选择 LinkedList；只有已经持有 ListIterator 并在当前位置连续修改时，才能避开重复定位。

LinkedList 节点还要保存链接，对 CPU 缓存不如连续数组友好。真实性能取决于数据规模和访问模式，不应引用一组固定毫秒数。需要对比时，用 JMH 避免预热、死代码消除和计时噪声干扰。

操作ArrayListLinkedList
get(i) / set(i, e)O(1)O(n)
尾部追加摊销 O(1)O(1)
add(0, e)O(n)O(1)
add(i, e)O(n) 搬移O(n) 定位，定位后 O(1) 链接
indexOf(e)O(n)O(n)
Iterator 已在当前位置时删除O(n) 搬移O(1) 链接

需要 FIFO/LIFO 或两端操作时优先考虑 ArrayDeque。它不支持按索引访问，也不允许 null，这正好让 poll 返回 null 表示队列为空。

3. remove 的重载会改变含义 ​

List<Integer> 上最容易误删：

java
List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));

numbers.remove(1);                 // 调用 remove(int index)，删除 20
numbers.remove(Integer.valueOf(30)); // 调用 remove(Object)，删除值 30

remove(index) 返回被删元素；remove(object) 返回是否找到并删除。看到整数参数时，先确认你需要的是位置还是值。

4. 三种“看起来像 List”的对象 ​

Arrays.asList：数组的固定大小视图 ​

java
String[] array = {"零件", "木材"};
List<String> view = Arrays.asList(array);

view.set(0, "钢件");   // array[0] 也变成“钢件”
// view.add("皮革");   // UnsupportedOperationException

它允许 set，但不允许改变大小。数组与列表共享元素存储。基本类型数组还有一个容易忽略的边界：Arrays.asList 不会自动把 int[] 拆成 Integer 元素，而会把整个数组当成一个元素：

java
int[] values = {1, 2, 3};
List<int[]> oneArray = Arrays.asList(values);
System.out.println(oneArray.size()); // 1

需要 List<Integer> 时可用 Arrays.stream(values).boxed().toList()；返回列表仍不可修改。

List.of：不可修改列表 ​

java
List<String> fixed = List.of("零件", "木材");

它拒绝 add、remove、set，也拒绝 null 元素。实现类型不属于契约。

new ArrayList<>(source)：独立可变副本 ​

java
List<String> copy = new ArrayList<>(fixed);
copy.add("皮革");

这是浅副本：列表结构独立，元素对象仍被共享。元素本身可变时，要决定是否也需要复制元素。

5. subList 是背靠原列表的范围视图 ​

java
List<String> ledger = new ArrayList<>(
        List.of("零件", "木材", "皮革", "麻绳"));
List<String> firstTwo = ledger.subList(0, 2);

firstTwo.set(1, "硬木");
System.out.println(ledger); // [零件, 硬木, 皮革, 麻绳]

修改视图会反映到原列表。通过视图之外的路径结构性修改原列表后，继续使用旧 subList 的行为通常会因并发修改检测而失败；API 对这种情况的结果不作通用保证。

需要独立结果时复制：

java
List<String> snapshot = List.copyOf(ledger.subList(0, 2));

List.copyOf 返回不可修改的浅副本并拒绝 null。需要可变副本则使用 new ArrayList<>(...)。

6. 遍历期间从原 List 删除 ​

旧代码写成：

java
for (String item : items) {
    if (item.startsWith("作废")) {
        items.remove(item);
    }
}

增强 for 使用 Iterator。ArrayList 等实现维护结构修改计数；Iterator 发现预期计数不一致时，常会抛 ConcurrentModificationException。fail-fast 是尽力发现程序错误的机制，不保证在每种时序下都抛，也不能替代同步。

只按条件删除：removeIf ​

java
items.removeIf(item -> item.startsWith("作废"));

遍历中需要更多控制：Iterator.remove ​

java
Iterator<String> iterator = items.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.startsWith("作废")) {
        iterator.remove();
    }
}

必须先成功调用 next，每次 next 后至多调用一次 remove。具体 List 也可能返回不支持删除的 Iterator，例如不可修改列表。

需要按位置处理：倒序索引 ​

java
for (int index = items.size() - 1; index >= 0; index--) {
    if (items.get(index).startsWith("作废")) {
        items.remove(index);
    }
}

倒序可避免删除后未访问元素整体左移导致跳项。ArrayList 每次中间删除仍要搬移元素，大批量条件删除通常让 removeIf 表达得更好。

7. ListIterator 支持双向与原位编辑 ​

java
ListIterator<String> iterator = items.listIterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.equals("木材")) iterator.set("硬木");
    if (item.equals("零件")) iterator.add("质检记录");
}

set 替换最近由 next 或 previous 返回的元素；add 在游标前插入，并把游标留在新元素之后，因此接下来的 next 不会再次读到它。刚调用 add 或 remove 后，不能立即 set；要先成功调用 next 或 previous。需要批量映射所有元素时，replaceAll 往往更简洁。

8. 完整可运行示例 ​

先准备临时目录：

bash
chapter10_list_root=$(mktemp -d)
readonly chapter10_list_root
mkdir -p "$chapter10_list_root/out"
cd "$chapter10_list_root"

保存为 ListContractsDemo.java：

java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;

public class ListContractsDemo {
    public static void main(String[] args) {
        List<String> items = new ArrayList<>(
                List.of("零件", "作废-木材", "皮革", "作废-麻绳"));
        items.removeIf(item -> item.startsWith("作废"));
        checkEquals(List.of("零件", "皮革"), items);

        items.addAll(List.of("作废-旧料", "硬木"));
        Iterator<String> iterator = items.iterator();
        while (iterator.hasNext()) {
            if (iterator.next().startsWith("作废")) iterator.remove();
        }
        checkEquals(List.of("零件", "皮革", "硬木"), items);

        List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));
        checkEquals(20, numbers.remove(1));
        check(numbers.remove(Integer.valueOf(30)), "应按值删除 30");
        checkEquals(List.of(10), numbers);

        String[] array = {"零件", "木材"};
        List<String> arrayView = Arrays.asList(array);
        arrayView.set(0, "钢件");
        checkEquals("钢件", array[0]);
        expect(UnsupportedOperationException.class,
                () -> arrayView.add("皮革"));

        List<String> ledger = new ArrayList<>(
                List.of("零件", "木材", "皮革"));
        List<String> view = ledger.subList(0, 2);
        view.set(1, "硬木");
        checkEquals(List.of("零件", "硬木", "皮革"), ledger);

        Iterator<String> stale = ledger.iterator();
        ledger.add("麻绳");
        expect(ConcurrentModificationException.class, stale::next);

        List<String> snapshot = List.copyOf(ledger.subList(0, 2));
        ledger.set(0, "钢件");
        checkEquals(List.of("零件", "硬木"), snapshot);
        expect(UnsupportedOperationException.class,
                () -> snapshot.add("新料"));

        System.out.println("有效领料：" + items);
        System.out.println("数组视图：" + arrayView);
        System.out.println("独立快照：" + snapshot);
        System.out.println("List 契约检查通过");
    }

    static void expect(Class<? extends Throwable> type, Runnable action) {
        try {
            action.run();
        } catch (Throwable throwable) {
            if (type.isInstance(throwable)) return;
            throw new AssertionError(
                    "expected=" + type + ", actual=" + throwable, throwable);
        }
        throw new AssertionError("expected exception=" + type.getName());
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    static void checkEquals(Object expected, Object actual) {
        if (!Objects.equals(expected, actual)) {
            throw new AssertionError("expected=" + expected + ", actual=" + actual);
        }
    }
}

运行：

bash
javac --release 17 -encoding UTF-8 -Xlint:all -d out ListContractsDemo.java
java -cp out ListContractsDemo

预期输出：

text
有效领料：[零件, 皮革, 硬木]
数组视图：[钢件, 木材]
独立快照：[零件, 硬木]
List 契约检查通过

保存需要的输出后清理：

bash
cd
ls -ld -- "$chapter10_list_root"
rm -r -- "$chapter10_list_root"

合上账本前，确认修改会传到哪里 ​

看到一个 List，先别急着调用 add 或 remove。问清它是独立的 ArrayList、数组的固定大小视图、原列表的 subList，还是不可修改快照。再判断元素对象是否也被共享。只要这条所有权链能画清，很多“明明都是 List”的意外就消失了。

然后用本篇示例做一次小改动：分别用 removeIf、当前 Iterator 和倒序索引删除所有作废记录，并核对没有漏项。若传给 remove 的是整数，还要明确它表示下标还是元素值。

查阅 Java 17 的正式契约 ​

下一步：给库存建立索引 ​

下一篇把物品名称映射到库存数量，再检查相等性规则为何会影响 Set 的去重结果。

继续学习 Map 与 Set

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang