一、重复的空表判断
这一篇对应官方 Lecture 5(SLLists, Nested Classes, Sentinel Nodes)。
裸 IntList 的问题不是难写,而是每写一个方法,都要重复一遍空表判断。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| public class NoSentinel { private static class IntNode { int item; IntNode next; IntNode(int i) { item = i; } }
private IntNode first;
public NoSentinel() { first = null; }
public void addLast(int x) { if (first == null) { first = new IntNode(x); return; } IntNode p = first; while (p.next != null) { p = p.next; } p.next = new IntNode(x); }
public int getLast() { if (first == null) { throw new IllegalStateException("空链表没有 last"); } IntNode p = first; while (p.next != null) { p = p.next; } return p.item; }
public static void main(String[] args) { NoSentinel L = new NoSentinel(); L.addLast(1); L.addLast(2); L.addLast(3); System.out.println("无哨兵版 getLast = " + L.getLast()); System.out.println("每新增一个方法,都要多写一次 first == null 的分支"); } }
|
输出:
1 2
| 无哨兵版 getLast = 3 每新增一个方法,都要多写一次 first == null 的分支
|
两个坏味道很明显:
first 有两个含义——「指向首节点」和「表示链表为空」。同一个字段承担两种语义,读代码时必须在脑子里做二次解释。
- 空表是特例。特例意味着漏判的风险,方法越多风险越大。
二、封装:把节点藏进内部
第一层改进是封装。调用方只需要 SLList 这个抽象,不该看见 IntNode。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| public class SLList { private static class IntNode { int item; IntNode next; IntNode(int i, IntNode n) { item = i; next = n; } }
private IntNode sentinel; private int size;
public SLList() { sentinel = new IntNode(63, null); size = 0; }
public SLList(int x) { sentinel = new IntNode(63, null); sentinel.next = new IntNode(x, null); size = 1; }
public void addFirst(int x) { sentinel.next = new IntNode(x, sentinel.next); size += 1; }
public void addLast(int x) { IntNode p = sentinel; while (p.next != null) { p = p.next; } p.next = new IntNode(x, null); size += 1; }
public int getFirst() { return sentinel.next.item; }
public int size() { return size; }
@Override public String toString() { StringBuilder sb = new StringBuilder("["); IntNode p = sentinel.next; while (p != null) { sb.append(p.item); if (p.next != null) { sb.append(", "); } p = p.next; } return sb.append("]").toString(); }
public static void main(String[] args) { SLList empty = new SLList(); System.out.println("空表 " + empty + ",size = " + empty.size()); empty.addLast(7); System.out.println("空表 addLast(7) 后 " + empty + ",size = " + empty.size());
SLList L = new SLList(5); L.addFirst(10); L.addLast(15); System.out.println("L = " + L); System.out.println("getFirst = " + L.getFirst() + ",size = " + L.size()); } }
|
输出:
1 2 3 4
| 空表 [],size = 0 空表 addLast(7) 后 [7],size = 1 L = [10, 5, 15] getFirst = 10,size = 3
|
注意 addLast 里没有空表分支。空表加元素、非空表加元素,走的是同一条路径。
三、哨兵节点做了什么
sentinel 是一个永远存在、但不装真实数据的节点。它带来的效果是:sentinel.next 恒为真实首节点——空表时它是 null,非空时它指向第一个节点。
flowchart LR
S["sentinel<br/>(占位,不装真实数据)"] --> N1["10"]
N1 --> N2["5"]
N2 --> N3["15"]
N3 --> NIL["null"]
于是:
first 这个词消失了。 首节点统一用 sentinel.next 表达,含义唯一。
- 空表不再是特例。
addLast 从哨兵出发走 next,空表时循环一次都不执行,直接接在哨兵后面。
getFirst 也不需要判空。 直接返回 sentinel.next.item,空表时自然抛 NPE,语义由调用方决定。
哨兵节点里那个 63 只是个占位数字,永远不会被读到。取这个值只是为了在调试时一眼认出「这不是真实数据」。
四、为什么要用 static 嵌套类
IntNode 声明成 private static class,这个 static 不是装饰。
| 写法 |
语义 |
能不能访问 SLList.this |
static class IntNode |
只是一个「放在 SLList 内部的普通类」 |
不能 |
class IntNode(非静态内部类) |
每个实例都隐含持有外部 SLList 实例的引用 |
能 |
非静态内部类会额外持有外部实例引用,一个节点就多一份指针开销,而且让两个类的生命周期互相绑定。链表节点不需要知道「我属于哪个链表」,所以用 static。
这也是一个通用判据:嵌套类如果不需要访问外部实例的成员,就一律加 static。
五、size 值不值得缓存
size() 直接返回 int size 字段,O(1)。如果要遍历数长度,每次调用都是 O(N)。链表类几乎总会被频繁问长度,所以 size 字段值得维护——代价是每个修改操作都要记得维护它。
这也留下一个隐患:任何一处忘了同步更新 size,缓存就是错的。所以 addFirst / addLast 里 size += 1 都紧跟在指针操作后面,放在同一个方法里,避免漏改。
六、小结
| 概念 |
一句话 |
证据 |
| 封装 |
IntNode 设为 private static 嵌套类,调用方看不到 |
外部只能用 addFirst / getFirst |
| 哨兵节点 |
sentinel.next 恒为真实首节点,消除空表特例 |
空表 addLast 无需判空 |
| 静态嵌套类 |
不持有外部实例引用,节点不该绑定链表 |
private static class IntNode |
size 缓存 |
用字段换 O(1),代价是每处修改都要维护 |
size() 返回 3,与元素数一致 |
| 哨兵取值 |
63 只是肉眼可辨的占位值 |
永不被读取 |
三条能带走的:
- 哨兵的实质是「用一个不装数据的节点,把空表和非空表统一成同一种形态」。 凡是「空 / 非空」分两套逻辑的地方,都值得问一句能不能用哨兵抹平。
- 嵌套类的
static 是设计决策,不是语法细节。 不需要访问外部实例就写成静态,否则白白多一份引用。
- 缓存字段换来 O(1),但把一致性责任推给了所有写操作。 这类「用空间和正确性风险换速度」的取舍,在后面维护树高、桶数、集合大小时会反复出现。