第14课：集合框架 - List

🎯 学习目标

• 理解 Collection 体系结构
• 掌握 ArrayList、LinkedList、Vector 的使用
• 理解三种 List 的区别和适用场景
• 掌握 List 的常用方法
• 理解迭代器模式

---

📖 一、集合框架概述

C vs Java 集合

C 语言：

// 需要手动实现或使用第三方库
struct ArrayList {
    int* data;
    int size;
    int capacity;
};

void add(struct ArrayList* list, int value) {
    if (list->size >= list->capacity) {
        // 手动扩容
        list->capacity *= 2;
        list->data = realloc(list->data, list->capacity * sizeof(int));
    }
    list->data[list->size++] = value;
}

Java：

// 内置强大的集合框架
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
System.out.println(list.get(0));  // 10

Collection 体系结构

Collection (接口)
├── List (接口) - 有序、可重复
│   ├── ArrayList - 数组实现
│   ├── LinkedList - 链表实现
│   └── Vector - 线程安全的 ArrayList
├── Set (接口) - 无序、不可重复
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
└── Queue (接口) - 队列
    ├── PriorityQueue
    └── Deque

---

📖 二、ArrayList - 动态数组

1. 基本使用

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

// 创建 ArrayList
List<String> list = new ArrayList<>();

// 添加元素
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add(1, "Orange");  // 在索引1插入

// 获取元素
String first = list.get(0);  // "Apple"
String second = list.get(1); // "Orange"

// 修改元素
list.set(0, "Grape");  // 将索引0改为 "Grape"

// 删除元素
list.remove(0);           // 删除索引0
list.remove("Banana");    // 删除指定元素

// 大小
int size = list.size();

// 判断是否包含
boolean contains = list.contains("Cherry");

// 清空
list.clear();

2. 遍历方式

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

// 方式1：for 循环
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 方式2：增强 for 循环（推荐）
for (String item : list) {
    System.out.println(item);
}

// 方式3：迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    System.out.println(item);
}

// 方式4：forEach + Lambda（Java 8+）
list.forEach(item -> System.out.println(item));

// 方式5：Stream（Java 8+）
list.stream().forEach(System.out::println);

3. ArrayList 内部原理

// 底层是 Object[] 数组
transient Object[] elementData;

// 默认容量
private static final int DEFAULT_CAPACITY = 10;

// 扩容机制
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 扩容1.5倍
    elementData = Arrays.copyOf(elementData, newCapacity);
}

特点：

• ✅ 随机访问快（O(1)）
• ✅ 尾部添加快（摊销O(1)）
• ❌ 中间插入/删除慢（O(n)）
• ❌ 扩容需要复制数组

---

📖 三、LinkedList - 双向链表

1. 基本使用

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();

// 添加元素
list.add("A");
list.addFirst("Start");   // 头部添加
list.addLast("End");      // 尾部添加

// 获取元素
String first = list.getFirst();
String last = list.getLast();

// 删除元素
list.removeFirst();
list.removeLast();

// 队列操作
list.offer("X");      // 添加到队尾
String head = list.poll();  // 移除队头

// 栈操作
list.push("Y");       // 压栈
String top = list.pop();    // 出栈

2. LinkedList 内部原理

// 节点结构
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

// 头尾指针
transient Node<E> first;
transient Node<E> last;

特点：

• ✅ 头尾插入/删除快（O(1)）
• ✅ 中间插入/删除快（找到位置后O(1)）
• ❌ 随机访问慢（O(n)）
• ❌ 占用内存多（需要存储前后指针）

---

📖 四、Vector - 线程安全的 ArrayList

import java.util.Vector;

Vector<String> vector = new Vector<>();
vector.add("A");
vector.add("B");

// 所有方法都是 synchronized 的
public synchronized boolean add(E e) {
    // ...
}

特点：

• ✅ 线程安全
• ❌ 性能较低（同步开销）
• ❌ 已过时，推荐使用 CopyOnWriteArrayList

---

📖 五、三种 List 对比

特性	ArrayList	LinkedList	Vector
底层实现	数组	双向链表	数组
随机访问	O(1) 快	O(n) 慢	O(1) 快
插入/删除	O(n) 慢	O(1) 快	O(n) 慢
内存占用	少	多	少
线程安全	否	否	是
扩容机制	1.5倍	无需扩容	2倍
推荐使用	✅ 最常用	特定场景	❌ 已过时

选择指南

// 场景1：大量随机访问 → ArrayList
List<String> names = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    String name = names.get(random.nextInt(names.size()));
}

// 场景2：频繁头尾操作 → LinkedList
LinkedList<Task> queue = new LinkedList<>();
queue.addLast(task);  // 入队
Task next = queue.removeFirst();  // 出队

// 场景3：线程安全 + 读多写少 → CopyOnWriteArrayList
List<String> list = new CopyOnWriteArrayList<>();

---

📖 六、List 常用方法

1. 批量操作

List<String> list1 = new ArrayList<>();
list1.add("A");
list1.add("B");

List<String> list2 = new ArrayList<>();
list2.add("C");
list2.add("D");

// 添加集合
list1.addAll(list2);  // [A, B, C, D]

// 删除集合
list1.removeAll(list2);  // [A, B]

// 保留交集
list1.retainAll(list2);

// 判断包含所有元素
boolean containsAll = list1.containsAll(list2);

2. 排序与搜索

List<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);

// 排序
Collections.sort(numbers);  // [1, 2, 5, 8]

// 反转
Collections.reverse(numbers);  // [8, 5, 2, 1]

// 打乱
Collections.shuffle(numbers);

// 二分查找（需要先排序）
Collections.sort(numbers);
int index = Collections.binarySearch(numbers, 5);

3. 转换

// List → 数组
List<String> list = Arrays.asList("A", "B", "C");
String[] array = list.toArray(new String[0]);

// 数组 → List
String[] arr = {"A", "B", "C"};
List<String> list = Arrays.asList(arr);  // 固定大小，不能add/remove
List<String> list2 = new ArrayList<>(Arrays.asList(arr));  // 可变

// List → Set（去重）
List<Integer> list = Arrays.asList(1, 2, 2, 3, 3, 3);
Set<Integer> set = new HashSet<>(list);  // [1, 2, 3]

4. 子列表

List<String> list = Arrays.asList("A", "B", "C", "D", "E");

// 子列表（包含start，不包含end）
List<String> subList = list.subList(1, 4);  // [B, C, D]

// ⚠️ 注意：subList 是视图，修改会影响原列表
subList.set(0, "X");
System.out.println(list);  // [A, X, C, D, E]

---

📖 七、迭代器（Iterator）

1. 基本使用

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    System.out.println(item);
    
    // 删除当前元素
    if ("B".equals(item)) {
        iterator.remove();  // 安全删除
    }
}

2. 为什么需要迭代器？

// ❌ 错误：边遍历边删除会抛 ConcurrentModificationException
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (String item : list) {
    if ("B".equals(item)) {
        list.remove(item);  // ❌ 抛异常
    }
}

// ✅ 正确：使用迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if ("B".equals(item)) {
        iterator.remove();  // ✅ 安全
    }
}

// ✅ 或使用 removeIf（Java 8+）
list.removeIf(item -> "B".equals(item));

---

📖 八、性能测试

// 测试随机访问性能
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

// 填充100万个元素
for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// ArrayList 随机访问
long start = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    arrayList.get(500000);
}
long end = System.nanoTime();
System.out.println("ArrayList: " + (end - start) + " ns");  // 很快

// LinkedList 随机访问
start = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    linkedList.get(500000);
}
end = System.nanoTime();
System.out.println("LinkedList: " + (end - start) + " ns");  // 很慢

---

⚠️ 常见陷阱

陷阱1：遍历时直接 remove

使用增强 for 遍历时直接 list.remove() 可能触发 ConcurrentModificationException。需要使用 Iterator 的 remove() 或 removeIf()。

陷阱2：频繁在 ArrayList 头部插入

ArrayList 头部插入会移动大量元素，复杂度 O(n)。需要频繁头插时应重新评估数据结构。

陷阱3：误以为 LinkedList 总是更快

LinkedList 随机访问慢，节点对象也更占内存。大多数普通列表场景 ArrayList 更好。

陷阱4：subList 修改影响原列表

subList 是视图，不是独立副本。修改 subList 会影响原 List，原 List 结构变化也可能让 subList 失效。

---

🆚 Java vs C 对比

特性	C	Java List
动态数组	手写 realloc 管理	ArrayList 自动扩容
链表	手写节点和指针	LinkedList 封装
越界	未定义行为或手动检查	IndexOutOfBoundsException
泛型元素	void* 或宏	泛型类型安全

对 C 程序员来说，ArrayList 类似“自动扩容的数组”，LinkedList 类似“双向链表封装”。多数业务默认 ArrayList，只有明确需要链表特性时才考虑 LinkedList。

---

💡 最佳实践

1. 默认使用 ArrayList（90%的场景）
2. 需要频繁头尾操作用 LinkedList
3. 不要用 Vector（用 CopyOnWriteArrayList）
4. 指定初始容量（避免频繁扩容）

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

5. 使用迭代器删除元素
6. 用接口声明变量

   List<String> list = new ArrayList<>();  // ✅
   ArrayList<String> list = new ArrayList<>();  // ❌

---

📝 练习

完成 练习/Ex14_List.java：

1. ArrayList 基本操作
2. LinkedList 队列/栈操作
3. 三种 List 性能对比
4. 迭代器使用
5. 集合排序与搜索
6. 综合：学生管理系统

---

🎓 下一步

• 第15课：集合框架 - Set - HashSet、TreeSet、去重原理