用了两年 ArrayList,被问「它为什么能自动变长」却答不上来。最好的回答方式:自己写一个。两个迷你实现加起来不到百行,写完集合的选型直觉直接换代。
ArrayList 内部就是一个 Object 数组加一个 size 计数器。装满了怎么办?换个大数组,把旧家当全体搬过去:
class MyArrayList {
private Object[] data = new Object[10];
private int size = 0; // 已装个数,不是数组长度
public void add(Object e) {
if (size == data.length) grow(); // 满了先搬家
data[size++] = e; // 放进去,size 后移
}
private void grow() {
data = Arrays.copyOf(data, data.length + (data.length >> 1));
}
}
grow 那行右移一位就是除以二,新容量即 1.5 倍。查询和删除是另外两员主力:
public Object get(int index) {
if (index >= size) throw new IndexOutOfBoundsException();
return data[index]; // 下标直取:O(1)
}
public void remove(int index) {
System.arraycopy(data, index + 1, data, index, size - index - 1);
data[--size] = null; // 尾巴置 null,帮 GC
}
三个设计点值得咂摸:
get(size) 才越界,get(数组长度内但 ≥ size) 拿到的是已删的旧数据——所以必须用 size 判界JDK 真货多了优化(懒初始化、指定容量构造),骨架与此无异。
class MyLinkedList {
private static class Node { // 静态内部类(3.4 节刚学的用法)
Object item; Node prev; Node next; // 双向手拉手
Node(Node prev, Object item, Node next) {
this.prev = prev; this.item = item; this.next = next;
}
}
private Node first, last;
private int size = 0;
}
节点是个三格包裹:一格装货,两格攥着前后邻居的手;整条链表只记着头尾两个门牌。addLast 把新节点接到尾巴:
public void addLast(Object e) {
Node l = last;
Node n = new Node(l, e, null); // 新节点接在尾巴后面
last = n;
if (l == null) first = n; // 空表:它既是头也是尾
else l.next = n;
size++;
}
头插和头删是对称动作,指针照着镜像接一遍:
public void addFirst(Object e) { // 头插
Node f = first;
Node n = new Node(null, e, f);
first = n;
if (f == null) last = n; else f.prev = n;
size++;
}
public Object removeFirst() {
Object v = first.item;
first = first.next; // 头节点直接断开
if (first == null) last = null; else first.prev = null;
return v;
}
头尾增删只是改两个指针,O(1)——这是它唯一的看家本领。
public Object get(int index) {
check(index);
Node x = first;
for (int i = 0; i < index; i++) x = x.next; // 一节节数过去
return x.item; // O(n)!
}
真实 LinkedList 做了个小优化(index 在前半就从 first 数,后半从 last 倒着数),但本质还是数。list.get(i) 在链表上是隐藏的循环——外面再套个 for 就是循环套循环,数据一大数据结构课白学。
| 操作 | ArrayList | LinkedList |
|---|---|---|
| get(i) 随机访问 | O(1) 直取 | O(n) 逐节数 |
| 尾部 add | 均摊 O(1) | O(1) |
| 头部插入 | O(n) 全体搬家 | O(1) 改指针 |
| 中间插入 | 搬家 O(n) | 数过去 O(n) + 改指针 |
| 每个元素内存 | 紧凑连续 | 每个多 prev/next 两指针 |
注意中间插入那行:链表也快不过数组——「找到那个位置」本身就是 O(n)。所以结论干脆:默认 ArrayList;只有「当队列用、只在头尾进出」(如任务队列)才考虑 LinkedList 或 ArrayDeque。
表格不用背,记两个画面就够:ArrayList 是电影院连排座位,坐满了服务员开一排更大的厅把人整体请过去;LinkedList 是排队的人互相牵手——中途插队容易,但找第 100 个人得从队头一个个问过去。
「ArrayList 还是 LinkedList」,满分答法分三层:先给结论——绝大多数场景 ArrayList;再给理由——随机访问 O(1)、内存连续缓存友好,链表找位置 O(n) 拖后腿;最后补边界——头尾频繁进出的队列场景才考虑链表或 ArrayDeque。结论、理由、边界——这个三层骨架是答一切选型题的模板,往后数据库选型、缓存选型,全是同一副腔调。
表格里的 O(1)、O(n) 是时间复杂度——数据量上涨时耗时的涨法。O(1) 恒定:数组按下标取值,一万个元素也是一步到位。O(n) 线性:链表找第 i 个,有多少节数多少节。O(n²) 平方:循环套循环,数据翻十倍、耗时翻一百倍。
它不问「具体几毫秒」,只问「涨得有多凶」。这正是选容器的依据:业务怎么访问数据,决定哪种涨法能接受。排序记一档:常数最好,对数(红黑树的 O(log n))次之,线性要警惕,平方基本是事故。
搬家明明是 O(n),凭什么说尾部添加是 O(1)?答案是均摊:搬一次家的成本,被之前十几次免搬的添加分摊了。像手机套餐:每天月租很便宜,偶尔一天国际漫游贵一次,拉平到每天看依然便宜。准确说法叫「均摊 O(1)」——偶尔贵一次,长期常数级。这个思路在动态数组、StringBuilder 扩容、HashMap 搬格子(rehash)里全是一个模子,第 6 章讲 HashMap 时它还会出场。
4.2 说 ArrayDeque 既当栈又当队列,看完实现就明白凭什么:内部是循环数组,两头各留指针。当栈用,push 和 pop 操作同一头;当队列用,offer 一头进、poll 另一头出。两头操作全是挪指针,都是 O(1)。再加上它没有链表的节点开销、内存连续对 CPU 缓存友好——单线程要栈或队列,闭眼选它。
新手容易觉得链表「插入快」就该全用它。但数据结构是组合拳:找位置 O(n) 拖后腿,每个节点多付两个指针的内存,散落的地址还让 CPU 缓存频繁失效。连续内存对现代 CPU 极度友好——顺序扫一遍数组比顺链数一遍快好几倍,不是玄学,是缓存局部性。所以工程默认连续存储,链表只在「频繁头尾进出」这道窄门里赢。
合上代码问自己五个问题:size 和数组长度为什么分开记?grow 为什么 1.5 倍?get 为什么用 size 判界?remove 为什么要置 null?链表 get 为什么慢?全能秒答,这两个容器就算拆明白了。以后再被问「ArrayList 默认容量、扩容几倍」,你答的是理解,不是背书。
new ArrayList<>(100000) 一步到位ArrayList 是会按 1.5 倍搬家的数组,随机访问 O(1);LinkedList 是双向手拉手的节点链,头尾 O(1) 但找位置要数——默认 ArrayList,纯头尾操作才轮到链表。