ArrayList 与 LinkedList

S1-016必学入门约 90 分钟JDK 21编程语言基础 · 集合

1. 本节定位

《List、Set、Map》讲了 List 接口的语义，本节看它的两个实现：ArrayList（动态数组）与 LinkedList（双向链表）。

结论先行：99% 的场景用 ArrayList。 本节的价值在于让你理解"为什么"，并知道那 1% 是什么场景——因为面试会问，也因为不理解结构就会用错。

2. 学习目标

完成本节后，你应该能够：

说出 ArrayList 与 LinkedList 的底层结构；
用"数组 vs 链表"解释两者的性能差异（随机访问、头部插入、尾部追加）；
在 ArrayList 可能频繁扩容时预分配容量；
说出 LinkedList 真正的适用场景（以及它更适合的替代品 ArrayDeque）；
用复杂度表做出选型判断，而不是凭感觉。

3. 前置知识检查

知道 List 与 Set 的语义差别吗？（《List、Set、Map》）
知道什么叫"时间复杂度 O(n)"吗？（《时间复杂度和空间复杂度》，不了解也能学，本节会给直观解释）

4. 为什么需要这个知识

两种实现提供完全相同的方法（都实现 List 接口），但性能可能差几百倍。这不是理论问题：

text

ArrayList 随机访问 20000 次: 1 ms
LinkedList 随机访问 20000 次: 432 ms     ← 400 倍差距

接口相同、行为相同、性能天差地别——这正是"数据结构决定性能"的最好例子。选错实现的后果是：代码能跑，但慢得莫名其妙。

5. 核心概念

5.1 两种结构

text

ArrayList：动态数组
┌───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │   │   │   连续内存，按下标直接定位
└───┴───┴───┴───┴───┴───┘

LinkedList：双向链表
┌──────┐   ┌──────┐   ┌──────┐
│ prev │◀─▶│ prev │◀─▶│ prev │   每个节点存前后指针，内存不连续
│ item │   │ item │   │ item │
│ next │   │ next │   │ next │
└──────┘   └──────┘   └──────┘

由结构直接推出性能：

操作	ArrayList	LinkedList	原因
尾部追加	快	快	数组末尾直接放；链表有尾指针
随机访问 `get(i)`	快（O(1)）	慢（O(n)）	数组按下标算地址；链表要从头走 i 步
头部/中间插入	慢（O(n)）	快（O(1)）	数组要整体搬家；链表改两个指针
内存占用	小（连续）	大（每节点两个指针）

5.2 实测数据

text

ArrayList 尾部追加 200000 次:  8 ms
LinkedList 尾部追加 200000 次: 10 ms

ArrayList 头部插入 20000 次: 474 ms
LinkedList 头部插入 20000 次:  12 ms     ← 40 倍差距

ArrayList 随机访问 20000 次:   1 ms
LinkedList 随机访问 20000 次: 432 ms     ← 400 倍差距

关于性能数字

具体毫秒数依赖机器与 JVM 状态，不要记数字，要记数量级：随机访问差两个数量级，头部插入差一到两个数量级，尾部追加基本持平。

想看自己机器上的数据，运行 labs/collections 的 ListPerformance。

5.3 ArrayList 的扩容

text

容量 10 的数组已满 → 申请一个更大的数组（约 1.5 倍）→ 把旧元素复制过去 → 指向新数组

扩容是 ArrayList 最耗时的操作，且复制成本随元素数量增长。

知道大概要存多少数据时，直接指定初始容量：

java

// 预计存 10000 条
List<String> list = new ArrayList<>(10000);

怎么知道该给多少：new ArrayList<>(expectedSize) 即可。ArrayList 内部会处理，不必精确——关键是避免"从 10 开始一次次翻倍复制"。

为什么是 1.5 倍

扩太大浪费空间，扩太小频繁复制。1.5 是空间与时间的折中。既然是"够用就行"的策略，提前知道数量时直接给容量就是最省的方式。

5.4 那 LinkedList 还有什么用

它实现了 Deque 接口，可以当队列（FIFO）与栈（LIFO）用：

java

Deque<String> queue = new LinkedList<>();
queue.offerLast("a");        // 入队
queue.pollFirst();           // 出队

但即使这个场景，ArrayDeque 也通常是更好的选择（更快、更省内存）——LinkedList 在现代 Java 里几乎没有必须使用的场景。

实用结论：

场景	选择
绝大多数列表需求	`ArrayList`
需要队列/栈	`ArrayDeque`（而不是 `LinkedList`）
需要在中间频繁插入删除	先想清楚：你真的需要吗？（通常用 `Map` 或别的方式更好）

6. 递进示例

6.1 最小示例：随机访问的差距

java

List<Integer> arrayList = new ArrayList<>(List.of(1, 2, 3, 4, 5));
System.out.println(arrayList.get(4));        // 直接算地址

List<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3, 4, 5));
System.out.println(linkedList.get(4));       // 从头走 4 步

结果相同，但 linkedList.get(4) 需要遍历 4 个节点。数据量越大、下标越大，差距越明显。

6.2 业务示例：预分配合适的容量

java

// 从数据库读出 5000 条数据
List<String> rows = new ArrayList<>(5000);      // 一次分配到位
for (int i = 0; i < 5000; i++) {
    rows.add("row-" + i);
}

不指定容量时，ArrayList 会经历"10 → 15 → 22 → 33 …"的多次复制。指定容量直接跳过这些步骤。

6.3 反例：用 LinkedList 做"按位置频繁访问"

java

List<String> list = new LinkedList<>();
// ... 插入 10000 条
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));        // 每次 get 都从头遍历 → O(n²)
}

修复：改用 ArrayList，或直接用增强 for（迭代器遍历链表是 O(n)）。

注意：LinkedList 用增强 for 遍历其实是高效的（顺着 next 指针走），慢的只是"按下标随机访问"。这是它最容易被误判的地方。

7. 完整可运行代码

文件：labs/collections/src/main/java/cn/kb/learn/collection/ListPerformance.java

java

package cn.kb.learn.collection;

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

public class ListPerformance {
    private static final int COUNT = 200_000;
    private static final int ACCESS_TIMES = 20_000;

    public static void main(String[] args) {
        measure("ArrayList 尾部追加 " + COUNT + " 次", () -> {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < COUNT; i++) {
                list.add(i);
            }
        });

        measure("LinkedList 尾部追加 " + COUNT + " 次", () -> {
            List<Integer> list = new LinkedList<>();
            for (int i = 0; i < COUNT; i++) {
                list.add(i);
            }
        });

        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        measure("ArrayList 头部插入 " + COUNT / 10 + " 次", () -> {
            List<Integer> list = new ArrayList<>(arrayList);
            for (int i = 0; i < COUNT / 10; i++) {
                list.add(0, i);
            }
        });

        measure("LinkedList 头部插入 " + COUNT / 10 + " 次", () -> {
            List<Integer> list = new LinkedList<>(linkedList);
            for (int i = 0; i < COUNT / 10; i++) {
                list.add(0, i);
            }
        });

        measure("ArrayList 随机访问 " + ACCESS_TIMES + " 次", () -> {
            long sum = 0;
            for (int i = 0; i < ACCESS_TIMES; i++) {
                sum += arrayList.get(i % COUNT);
            }
            if (sum < 0) {
                System.out.print("");
            }
        });

        measure("LinkedList 随机访问 " + ACCESS_TIMES + " 次", () -> {
            long sum = 0;
            for (int i = 0; i < ACCESS_TIMES; i++) {
                sum += linkedList.get(i % COUNT);
            }
            if (sum < 0) {
                System.out.print("");
            }
        });
    }

    private static void measure(String label, Runnable action) {
        long start = System.nanoTime();
        action.run();
        long costMillis = (System.nanoTime() - start) / 1_000_000;
        System.out.println(label + ": " + costMillis + " ms");
    }
}

运行命令：

powershell

cd labs
./mvnw -pl collections compile
java -cp collections/target/classes cn.kb.learn.collection.ListPerformance

本机实测输出：

text

ArrayList 尾部追加 200000 次: 8 ms
LinkedList 尾部追加 200000 次: 10 ms
ArrayList 头部插入 20000 次: 474 ms
LinkedList 头部插入 20000 次: 12 ms
ArrayList 随机访问 20000 次: 1 ms
LinkedList 随机访问 20000 次: 432 ms

你的机器上数字会不同，请关注比例关系：

尾部追加：两者接近；
头部插入：LinkedList 快约 40 倍；
随机访问：ArrayList 快约 400 倍。

为什么"头部插入"和"随机访问"的差距不对称：数组的插入需要搬移元素（平均搬一半），是 O(n) 但常数小；链表的随机访问要遍历节点，也是 O(n) 但访存不连续（缓存不友好），所以慢得多。

8. Debug 观察点

在循环里 list.add(i) 处断点，展开 ArrayList 的 elementData 数组，观察长度如何从 10 变 15、变 22——这就是扩容的现场；
对比 new ArrayList<>(10000) 与 new ArrayList<>() 在添加 10000 个元素后的 elementData.length；
展开 LinkedList 对象，观察 first / last 节点的 prev / next 指针结构；
在 linkedList.get(199999) 处断点并 F7 进入 LinkedList.node(int index)，观察它从 first 或 last 开始一步步走（源码里有"下标小于一半就从头走"的优化）。

9. 常见错误

错误 1：用 LinkedList 做按位置的循环访问

java

for (int i = 0; i < list.size(); i++) {
    String item = list.get(i);      // LinkedList 下是 O(n²)
}

修复：改用增强 for（迭代器遍历），或改用 ArrayList。

错误 2：ArrayList 频繁插入中间位置

java

for (int i = 0; i < 10000; i++) {
    list.add(0, item);              // 每次都要搬移所有元素
}

修复：先 add 到末尾再 Collections.reverse，或换用 LinkedList / ArrayDeque。

错误 3：明明知道大小却不预分配

java

List<Result> results = new ArrayList<>();     // 从容量 10 开始
// ... 添加 10000 条

修复：new ArrayList<>(10000)。

错误 4：以为 `ArrayList` 是线程安全的

java

List<String> shared = new ArrayList<>();
// 多线程 add → 数据错乱甚至抛异常

修复：用 CopyOnWriteArrayList、Collections.synchronizedList(...)，或加锁（《线程与同步基础》会讲并发集合）。

10. 动手实验

目标：用自己的数据验证两种实现的行为差异。

步骤：

运行 ListPerformance，记录你机器上的六行数据；
把 COUNT 改成 50000 再跑一次，观察哪一组的差距缩小得最明显，并解释原因；
写代码验证"ArrayList 预分配容量"的效果：分别用 new ArrayList<>() 与 new ArrayList<>(1000000) 添加 100 万个元素，对比耗时；
用增强 for 遍历一个 10 万元的 LinkedList，与用下标 for 遍历对比耗时——验证"链表遍历不慢，慢的是按下标访问"；
把 ArrayList 换成 ArrayDeque 做队列（offerLast / pollFirst），与 LinkedList 对比。

验收方式：能解释第 2 步与第 4 步的结果。

扩展任务：实现一个简单的"用 ArrayList 当队列"的类（add 到末尾、poll 从头部取），分析它的时间复杂度，并对比 ArrayDeque 的实现思路。

11. 练习题

基础题

判断：LinkedList 的随机访问比 ArrayList 快。（对 / 错）
填空：ArrayList 扩容大约是原容量的 ______ 倍；需要队列时应该优先用 ______。
简答：为什么 ArrayList 的中间插入比 LinkedList 慢？

代码阅读题

java

List<Integer> list = new ArrayList<>(2);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list.size());

输出是什么？初始容量是 2，为什么能装下 4 个元素？

编程题

从 10 万条数据中删除所有偶数，分别用 ArrayList 与 LinkedList 实现，并思考：
- 用倒序下标删除（ArrayList 友好）；
- 用迭代器删除（两者都友好）；
- 用 removeIf（最简洁）；对比三种写法的耗时与代码可读性。

综合任务

实现一个"最近访问记录"（LRU 的简化版）：
- 最多保留 N 条记录；
- 重复访问时把记录移到最前；
- 超出容量时丢弃最旧的；
- 要求：用 LinkedList 与 ArrayList 各实现一次，对比两者的性能与代码复杂度；
- 说明：真实场景下你会怎么实现（提示：LinkedHashMap 有现成的 LRU 支持）。

分级提示

提示 1（方向）：第 4 题的关键是"容量 ≠ 长度"——容量可以自动增长。

提示 2（关键点）：第 5 题的 removeIf 在 ArrayList 上会用一次搬移完成，通常最快。

提示 3（接近答案）：第 6 题用 LinkedList 时，"移到最前"是 remove + addFirst；用 ArrayList 则需要 remove 后再 add(0, ...)，后者要搬移元素。

12. 参考答案

基础题

错。ArrayList 的随机访问是 O(1)（按下标算地址），LinkedList 是 O(n)（从头遍历）。实测差距可达数百倍。
1.5、ArrayDeque。
因为数组是连续内存：在中间插入一个元素，必须把它后面的所有元素依次向后搬移一格；而链表只需修改相邻节点的两个指针。所以数据量大时 LinkedList 的插入更快。

代码阅读题（第 4 题）

输出 4。

容量与长度是两个概念：new ArrayList<>(2) 只是"初始容量是 2"，元素超过容量时 ArrayList 会自动扩容（大约 1.5 倍），所以能装下更多。size() 返回的是元素个数，不是容量。

想看当前容量可以用 ArrayList 的 ensureCapacity / 反射，或观察调试器里的 elementData.length。

编程题（第 5 题）

java

package cn.kb.learn.collection;

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

public class RemoveEven {
    private static final int COUNT = 100_000;

    public static void main(String[] args) {
        List<Integer> arrayList = build(new ArrayList<>());
        List<Integer> linkedList = build(new LinkedList<>());

        // 方式一：倒序下标删除（对 ArrayList 友好）
        List<Integer> copy1 = new ArrayList<>(arrayList);
        measure("ArrayList 倒序删除", () -> {
            for (int i = copy1.size() - 1; i >= 0; i--) {
                if (copy1.get(i) % 2 == 0) {
                    copy1.remove(i);
                }
            }
        });

        // 方式二：迭代器删除（对两者都友好）
        List<Integer> copy2 = new LinkedList<>(linkedList);
        measure("LinkedList 迭代器删除", () -> {
            Iterator<Integer> iterator = copy2.iterator();
            while (iterator.hasNext()) {
                if (iterator.next() % 2 == 0) {
                    iterator.remove();
                }
            }
        });

        // 方式三：removeIf（最简洁）
        List<Integer> copy3 = new ArrayList<>(arrayList);
        measure("ArrayList removeIf", () -> copy3.removeIf(value -> value % 2 == 0));

        System.out.println("剩余元素数量: " + copy1.size() + " / " + copy2.size() + " / " + copy3.size());
    }

    private static List<Integer> build(List<Integer> target) {
        for (int i = 0; i < COUNT; i++) {
            target.add(i);
        }
        return target;
    }

    private static void measure(String label, Runnable action) {
        long start = System.nanoTime();
        action.run();
        long cost = (System.nanoTime() - start) / 1_000_000;
        System.out.println(label + ": " + cost + " ms");
    }
}

三种写法的对比结论：

写法	可读性	性能	适用
倒序下标	中	`ArrayList` 上快	需要按下标处理逻辑时
迭代器	中	两者都好	需要精细控制时
`removeIf`	最好	好（内部用了一次搬移）	首选

实践建议：优先 removeIf；只有在需要按索引做复杂判断时才用倒序下标。

综合任务（第 6 题）

java

package cn.kb.learn.collection;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class RecentHistory {
    /** LinkedList 版：头尾操作都是 O(1) */
    static class LinkedVersion {
        private final int capacity;
        private final LinkedList<String> items = new LinkedList<>();

        LinkedVersion(int capacity) {
            this.capacity = capacity;
        }

        void visit(String item) {
            items.remove(item);
            items.addFirst(item);
            while (items.size() > capacity) {
                items.removeLast();
            }
        }

        List<String> items() {
            return new ArrayList<>(items);
        }
    }

    /** ArrayList 版：移到最前要搬移元素 */
    static class ArrayVersion {
        private final int capacity;
        private final List<String> items = new ArrayList<>();

        ArrayVersion(int capacity) {
            this.capacity = capacity;
        }

        void visit(String item) {
            items.remove(item);
            items.add(0, item);                 // O(n) 搬移
            while (items.size() > capacity) {
                items.remove(items.size() - 1);
            }
        }

        List<String> items() {
            return new ArrayList<>(items);
        }
    }

    /** 生产环境推荐：LinkedHashMap 自带访问顺序 + 淘汰 */
    static class LruVersion extends LinkedHashMap<String, Boolean> {
        private final int capacity;

        LruVersion(int capacity) {
            super(16, 0.75f, true);             // accessOrder = true
            this.capacity = capacity;
        }

        void visit(String item) {
            put(item, Boolean.TRUE);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Boolean> eldest) {
            return size() > capacity;
        }
    }

    public static void main(String[] args) {
        LinkedVersion linked = new LinkedVersion(3);
        ArrayVersion array = new ArrayVersion(3);
        LruVersion lru = new LruVersion(3);

        for (String item : List.of("A", "B", "C", "A", "D")) {
            linked.visit(item);
            array.visit(item);
            lru.visit(item);
        }

        System.out.println("LinkedList 版: " + linked.items());
        System.out.println("ArrayList 版: " + array.items());
        System.out.println("LinkedHashMap 版: " + lru.keySet());
    }
}

对比结论：

实现	移到最前	淘汰最旧	代码量
`LinkedList`	`remove` + `addFirst`，O(n) 查找 + O(1) 操作	`removeLast()` O(1)	中
`ArrayList`	`remove` + `add(0, ...)`，两次 O(n) 搬移	`remove(size-1)` O(1)	中
`LinkedHashMap`	自动维护访问顺序	`removeEldestEntry` 一行	最少

这就是"选对数据结构"的价值：LinkedHashMap 用一行 removeEldestEntry 实现了两个手写版本共几十行代码的功能，而且内部是哈希结构、访问更快。

结论：LinkedList 在教学上很有价值，但在生产代码里几乎总能找到更好的替代品。

预期输出：

text

LinkedList 版: [D, A, C]
ArrayList 版: [D, A, C]
LinkedHashMap 版: [D, A, C]

13. 掌握标准

[ ] 能说出两种实现的底层结构与复杂度差异；
[ ] 知道随机访问与中间插入的性能差距来自哪里；
[ ] 会在已知数据量时预分配 ArrayList 容量；
[ ] 知道"需要队列就用 ArrayDeque"而不是 LinkedList；
[ ] 能用增强 for 遍历链表，而不是按下标访问。

14. 扩展资源

ArrayList 官方 API：类注释里写了扩容策略
LinkedList 官方 API
《HashMap》：另一个"结构决定性能"的经典案例

15. 下一步学习

《HashSet、TreeSet 与集合排序》：Set 的三种实现，以及"怎么给对象排序"这件必须掌握的事。

前置知识

S1-015 List、Set、Map

后续知识

暂无

进度只保存在本机浏览器，可随时清除

外部学习资源

面试题库索引

项目与练手索引

工具与软件索引

ArrayList 与 LinkedList

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 两种结构

5.2 实测数据

5.3 ArrayList 的扩容

5.4 那 LinkedList 还有什么用

6. 递进示例

6.1 最小示例：随机访问的差距

6.2 业务示例：预分配合适的容量

6.3 反例：用 LinkedList 做"按位置频繁访问"

7. 完整可运行代码

8. Debug 观察点

9. 常见错误

错误 1：用 LinkedList 做按位置的循环访问

错误 2：ArrayList 频繁插入中间位置

错误 3：明明知道大小却不预分配

错误 4：以为 `ArrayList` 是线程安全的

10. 动手实验

11. 练习题

12. 参考答案

13. 掌握标准

14. 扩展资源

15. 下一步学习

前置知识

后续知识

ArrayList 与 LinkedList ​

1. 本节定位 ​

2. 学习目标 ​

3. 前置知识检查 ​

4. 为什么需要这个知识 ​

5. 核心概念 ​

5.1 两种结构 ​

5.2 实测数据 ​

5.3 ArrayList 的扩容 ​

5.4 那 LinkedList 还有什么用 ​

6. 递进示例 ​

6.1 最小示例：随机访问的差距 ​

6.2 业务示例：预分配合适的容量 ​

6.3 反例：用 LinkedList 做"按位置频繁访问" ​

7. 完整可运行代码 ​

8. Debug 观察点 ​

9. 常见错误 ​

错误 1：用 LinkedList 做按位置的循环访问 ​

错误 2：ArrayList 频繁插入中间位置 ​

错误 3：明明知道大小却不预分配 ​

错误 4：以为 ArrayList 是线程安全的 ​

10. 动手实验 ​

11. 练习题 ​

12. 参考答案 ​

13. 掌握标准 ​

14. 扩展资源 ​

15. 下一步学习 ​

前置知识

后续知识

ArrayList 与 LinkedList

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 两种结构

5.2 实测数据

5.3 ArrayList 的扩容

5.4 那 LinkedList 还有什么用

6. 递进示例

6.1 最小示例：随机访问的差距

6.2 业务示例：预分配合适的容量

6.3 反例：用 LinkedList 做"按位置频繁访问"

7. 完整可运行代码

8. Debug 观察点

9. 常见错误

错误 1：用 LinkedList 做按位置的循环访问

错误 2：ArrayList 频繁插入中间位置

错误 3：明明知道大小却不预分配

错误 4：以为 `ArrayList` 是线程安全的

10. 动手实验

11. 练习题

12. 参考答案

13. 掌握标准

14. 扩展资源

15. 下一步学习