元数据卡

项目	内容
前置知识	集合框架入门（上一页）
预计时间	25 分钟
完成标志	能说出 ArrayList 和 LinkedList 的核心差异及扩容机制，能写出正确的遍历删改代码

---

老陈递来一个账本："帮阿花整理工坊领料记录。每天上百条，有时加末尾，有时翻第 N 条，偶尔中间插一条。"

数组擅长度追加和按索引翻（O(1)），但中间插一条就要把后面全挪一遍。而且每天记录数不一样。数组的动态版本叫 ArrayList。另一种选择叫 LinkedList。它们的脾气完全不同。

ArrayList：动态数组

内部维护 Object[] elementData。装不下时：判断不够→创建更大数组→System.arraycopy() 全量复制。

扩容： 默认初始 10，新容量=旧+(旧>>1)=1.5倍。O(n) 全量复制。大数据量提前指定：new ArrayList<>(1000) 零次扩容。

// ArrayListDemo.java，javac && java 运行
import java.util.*;
public class ArrayListDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= 15; i++) list.add("领料单-" + i);
        System.out.println("总数: " + list.size() + ", 第5条: " + list.get(4));
        long t = System.nanoTime();
        list.add(0, "紧急插入"); // 头部插入
        System.out.println("头部插入: " + (System.nanoTime()-t)/1e6 + " ms");
        System.out.println("领料单-10 在: " + list.indexOf("领料单-10"));
} }

运行步骤： javac ArrayListDemo.java && java ArrayListDemo预期输出： 总数 15，第5条=领料单-5，头部插入约 0.01 ms，领料单-10 在 11

LinkedList：双向链表

每个元素是一个节点（数据+前驱+后继指针），不依赖连续内存，插入删除只调相邻节点指针。

// ListCompare.java，javac && java 运行
import java.util.*;
public class ListCompare {
    public static void main(String[] args) {
        int N = 100_000;
        List<String> a = new ArrayList<>();
        long t = System.nanoTime();
        for (int i=0;i<N;i++) a.add(0,"x");
        System.out.println("ArrayList 头部插入: "+(System.nanoTime()-t)/1e6+" ms");
        List<String> l = new LinkedList<>();
        t = System.nanoTime();
        for (int i=0;i<N;i++) l.add(0,"x");
        System.out.println("LinkedList 头部插入: "+(System.nanoTime()-t)/1e6+" ms");
        for(int i=0;i<N;i++){a.add("i");l.add("i");}
        Random r=new Random(42);
        t=System.nanoTime();
        for(int i=0;i<10000;i++) a.get(r.nextInt(N));
        System.out.println("ArrayList 随机读: "+(System.nanoTime()-t)/1e6+" ms");
        t=System.nanoTime();
        for(int i=0;i<10000;i++) l.get(r.nextInt(N));
        System.out.println("LinkedList 随机读: "+(System.nanoTime()-t)/1e6+" ms");
} }

运行及预期： javac ListCompare.java && java ListCompare → ArrayList 头插 ~3180 ms，LinkedList ~13 ms；ArrayList 随机读 ~5 ms，LinkedList ~2500 ms。左列全体后移 O(n)，右列只改指针 O(1)；左列直接算地址 O(1)，右列从头遍历 O(n)。

性能速查表

操作	ArrayList	LinkedList
尾部追加 add(E)	O(1)*	O(1)
头部插入 add(0,E)	O(n)	O(1)
按索引读取 get(i)	O(1)	O(n)
按值查找 indexOf	O(n)	O(n)
头部删除 remove(0)	O(n)	O(1)
内存开销	小（连续数组）	大（节点+双指针）

*尾部追加摊销 O(1)：满了才触发 O(n) 扩容，平均下来常数级。

常用 API

// ListMethods.java，javac && java 运行
import java.util.*;
public class ListMethods {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("木材"); list.add(0,"麻绳");
        list.addAll(Arrays.asList("皮革","铁锭"));
        list.get(0); list.indexOf("皮革"); list.contains("铁锭");
        list.set(1,"精金");
        list.remove("木材"); list.remove(0);
        Collections.sort(list);
        List<String> sub = list.subList(0,2); // 视图！
        System.out.println(list); } }

注意： subList 是原列表视图。独立副本：new ArrayList<>(list.subList(0, 2))。

遍历方式

// ListTraverse.java，javac && java 运行
import java.util.*;
public class ListTraverse {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("a","b","c","d","e");
        for (String s : list) System.out.print(s+" ");
        System.out.println(); // for-each
        for (int i=0; i<list.size(); i++) System.out.print(list.get(i)+" ");
        System.out.println(); // for+下标
        Iterator<String> it = list.iterator();
        while (it.hasNext()) System.out.print(it.next()+" ");
        System.out.println(); // Iterator
        list.forEach(s -> System.out.print(s+" "));
        System.out.println(); // Lambda
    }
}

预期输出： 四行 a b c d e

方式	适用场景	遍历中删除
for-each	只读	不能（抛异常）
for+下标	需索引	可以（倒序）
Iterator	遍历删除	能（it.remove()）
forEach+Lambda	简洁只读	不能

遍历时删除

List<String> list = new ArrayList<>(Arrays.asList("a","b","c","d","e"));
for (String s : list) { if (s.equals("c")) list.remove(s); } // ConcurrentModificationException！

增强 for 背后是 Iterator，维护 modCount。list.remove() 改了列表没通知 Iterator，下次 next() 检测不一致就抛异常。

正确做法：

// 1. Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) { String s = it.next(); if (s.equals("c")) it.remove(); }
// 2. removeIf（最推荐）
list.removeIf(s -> s.equals("c"));
// 3. 倒序遍历
for (int i = list.size()-1; i >= 0; i--) if (list.get(i).equals("c")) list.remove(i);

结果都是 [a, b, d, e]。

---

旅人笔记

ArrayList 连续数组，查询 O(1)、尾部追加摊销 O(1)、扩容 1.5 倍。LinkedList 双向链表，头尾插入 O(1)、查询 O(n)、内存更大。多数场景 ArrayList 够用。遍历删除用 removeIf 或 Iterator.remove()。

→ 下一步：Map 与 Set 详解

HashMap 为什么能 O(1) 查找？HashSet 去重的本质是什么？TreeMap 怎么自动排序的？

看 Map 与 Set →