03.1 — List 体系
定位: 有序、可重复的集合 — ArrayList 和 LinkedList 的数据结构对决 面试高频度: ⭐⭐⭐⭐ 考查方式: ArrayList 扩容机制、LinkedList 数据结构、两者选择依据
一、这是什么？为什么需要它？
List 接口 = 有序集合（允许重复）
├── ArrayList — 动态数组（查询快，插入慢）
├── LinkedList — 双向链表（插入快，随机访问慢）
└── Vector — 线程安全版 ArrayList（已过时）
└── Stack — 后进先出栈（已过时）为什么需要 List？
数组长度固定，而日常开发中很少知道确切数据量。
- 数组：
int[] arr = new int[10];— 长度固定 - ArrayList：自动扩容，开发者不用关心容量
二、原理拆解
2.1 ArrayList — 动态数组
java
public class ArrayList<E> {
// 底层用数组存储
private transient Object[] elementData;
private int size; // 实际元素数量
}扩容机制：
初始容量 = 10 (JDK7+ 懒加载：第一次 add 才分配)
add(e) → size+1 > elementData.length?
├── 否 → 直接放入 elementData[size] O(1)
└── 是 → 扩容
├── 新容量 = 旧容量 * 1.5 (oldCapacity + (oldCapacity >> 1))
├── 创建新数组
├── System.arraycopy() 复制旧数据 O(n)
└── 添加新元素
扩容因子 = 1.5
为什么是 1.5？—— 兼顾空间利用率和扩容频率
2.0 → 浪费空间（有一半空闲）
1.25 → 频繁扩容（复制开销大）
1.5 → 经验最优值扩容性能影响：
假设初始容量 10，最终 10,000 个元素：
log(1.5)(10000/10) ≈ 17 次扩容
每次扩容复制数据 → 总复制量 ≈ O(n)
但均摊到每个元素 → O(1) （均摊分析）2.2 LinkedList — 双向链表
java
private static class Node<E> {
E item;
Node<E> next; // 后驱
Node<E> prev; // 前驱
}链表结构：
null ←── [prev|item|next] ←──→ [prev|item|next] ←──→ [prev|item|next] ──→ null
↑ first ↑ lastLinkedList 既实现了 List 又实现了 Deque：
java
// 作为 List
list.add(e); // 尾部添加 O(1)
list.get(index); // 遍历到索引位置 O(n)
// 作为 Deque/Queue
list.addFirst(e); // 头部添加 O(1)
list.removeFirst(); // 头部删除 O(1)2.3 ArrayList vs LinkedList 详尽对比
| 操作 | ArrayList | LinkedList |
|---|---|---|
| get(i) | O(1) — 直接数组寻址 | O(n) — 从头/尾遍历 |
| add(E) 尾部 | O(1) 均摊（扩容时 O(n)） | O(1) — 改 last 指针 |
| add(i, E) 中间 | O(n) — 移动后续所有元素 | O(n) — 先找到位置，改指针 O(1) |
| remove(i) | O(n) — 移动后续元素 | O(n) — 查找 O(n) + 改指针 O(1) |
| 内存开销 | 连续数组，几乎没有额外开销 | 每个节点多 2 个指针 (16-24 字节) |
| 迭代效率 | 连续内存，CPU 缓存友好 | 非连续内存，缓存不友好 |
| 适合场景 | 随机访问多，尾部追加多 | 频繁头尾操作，作为队列使用 |
实战建议：绝大多数场景用 ArrayList。
除非你明确需要 Deque 接口或头部频繁操作，否则 ArrayList 通常更快（CPU 缓存友好 + 内存连续）。
2.4 Vector / Stack — 过时集合
Vector 和 ArrayList 的区别：
- Vector 方法加了 synchronized（线程安全）
- Vector 扩容 = 2 倍（可设置增量）
- Vector 从 JDK1.0 就有，ArrayList 从 JDK2 才有
为什么不推荐用 Vector？
- 全方法加锁，并发效率低
- 更好的选择：
✅ 单线程 → ArrayList
✅ 多线程 → CopyOnWriteArrayList 或 Collections.synchronizedList()三、图解全景
┌─────────────────────────────────────────────────────────────┐
│ ArrayList 扩容流程图 │
│ │
│ add(e) │
│ │ │
│ ▼ │
│ ensureCapacityInternal(size + 1) │
│ │ │
│ ▼ │
│ size + 1 > elementData.length? │
│ │ │ │
│ 否 是 │
│ │ │ │
│ ▼ ▼ │
│ elementData[size] grow() │
│ = e; │ │
│ oldCapacity + (oldCapacity >> 1) │
│ │ (1.5 倍) │
│ ▼ │
│ return true new Object[newCapacity] │
│ System.arraycopy(旧数据 → 新数据) │
│ elementData = newArray │
│ │ │
│ ▼ │
│ elementData[size] = e │
└─────────────────────────────────────────────────────────────┘四、实战验证
4.1 ArrayList 扩容验证
java
// 看源码验证扩容
ArrayList<Integer> list = new ArrayList<>();
System.out.println("初始容量: 0 (懒加载)");
for (int i = 0; i < 12; i++) {
list.add(i);
}
// 第 11 个元素加入时触发扩容：扩容为 10 * 1.5 = 15
// 预估容量优化
ArrayList<Integer> list2 = new ArrayList<>(1000);
// 已知最终会有 1000 个元素时，指定初始容量避免多次扩容4.2 ArrayList vs LinkedList 性能对比
java
int N = 100000;
// 头部插入
long start = System.nanoTime();
List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < N; i++) arrayList.add(0, i);
long arrayTime = System.nanoTime() - start; // 非常慢！O(n^2)
start = System.nanoTime();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < N; i++) linkedList.add(0, i);
long linkedTime = System.nanoTime() - start; // 快！O(1) 每插入
// 随机访问
start = System.nanoTime();
for (int i = 0; i < N; i++) arrayList.get(i);
arrayTime = System.nanoTime() - start; // 快！O(1)
start = System.nanoTime();
for (int i = 0; i < N; i++) linkedList.get(i);
linkedTime = System.nanoTime() - start; // 非常慢！O(n^2)五、面试视角
| 追问 | 答案要点 |
|---|---|
| ArrayList 扩容多少倍？为什么？ | 1.5 倍。平衡空间利用率和扩容频率 |
| ArrayList 插入删除为什么慢？ | 需要 System.arraycopy 移动后续元素 O(n) |
| LinkedList 什么时候比 ArrayList 快？ | 头部频繁插入删除、作为队列使用时 |
| ArrayList 的 size() 是 O(1) 吗？ | 是，直接返回 size 字段 |
| 线程安全的 List 怎么实现？ | CopyOnWriteArrayList（读多写少）/ Collections.synchronizedList |
📚 相关链接
- **HashMap核心原理** — Map 体系的核心
- **ConcurrentHashMap** — 并发集合的实现
- ← 返回 **集合索引**