引用语义、递归与裸链表
一、b = a 复制了什么
这一篇对应官方 Lecture 4(References, Recursion, and Lists)。
先看一段代码。a 是一个对象,b = a 之后修改 b,a 会变吗?
1 | public class WalrusDemo { |
输出:
1 | a.weight = 2000 |
b = a 之后 a.weight 也变成了 2000。原因只有一个:Java 的变量里装的是引用,不是对象本身。 赋值复制的是那串指向对象的位串,两个变量因此指向堆上的同一个对象。
二、引用的三条推论
从上面这一段可以推出三条贯穿全课的性质:
- 赋值不复制对象。
b = a只多了一个别名。想复制一份独立的对象,必须自己写拷贝逻辑,或者用new。 ==比较的是引用。b == c为false,尽管两个对象的weight相同,因为它们是两个不同的对象。- 默认
equals等同于==。 输出里b.equals(c)也是false,因为Object.equals的默认实现就是引用比较。要让「内容相等」成立,必须自己重写equals。
flowchart LR
subgraph S["栈上的变量"]
A["a"]
B["b"]
C["c"]
end
subgraph H["堆上的对象"]
O1["Walrus(2000)"]
O2["Walrus(2000)"]
end
A --> O1
B --> O1
C --> O2
a 与 b 指向同一个对象,所以 a == b。c 指向另一个对象,所以 b == c 为 false,哪怕内容一样。
三、用递归重写循环
有了引用,就可以定义「自己装自己」的结构。最朴素的形式是裸链表 IntList:一个节点装一个整数,再加一个指向下一个节点的引用。
1 | public class IntList { |
输出:
1 | L = 1 -> 2 -> 3 -> 4 -> 5 |
size 与 iterativeSize 结果一致,但思路完全不同:
- 迭代版用一个局部变量
p沿rest往前走,数到null为止。 - 递归版只回答一个问题:剩余部分有多长。长度 = 1 +
rest.size(),直到rest == null时返回 1。
关键在递归基。写成 if (this == null) return 0 是错的——this 永远不会是 null,方法能被执行说明对象一定存在。递归基必须写成 rest == null,也就是「我是最后一个节点」。
四、不可变与可变的分野
incrList 值得单独看。它不修改任何已有节点,而是从头到尾新建一条链,原链完全不动——调用 L.incrList(10) 拿到 M 之后,再打印 L 依旧是 1 -> 2 -> 3 -> 4 -> 5、L.first 依旧是 1,而 M 是 11 -> 12 -> 13 -> 14 -> 15。
这就是**不可变(immutable)**风格的递归数据结构:任何「修改」都表现为「返回一个新版本」。好处是调用方不需要担心自己的数据被别人改掉;代价是每次都要分配一整条新链。
对比之下,可变风格会直接改 L.rest = ...,省内存但需要调用方清楚「我的数据被改过了」。
| 风格 | 修改的表现 | 空间代价 | 调用方要担心什么 |
|---|---|---|---|
| 不可变 | 返回新链,原链不动 | 每次 O(N) 新节点 | 几乎不用担心 |
| 可变 | 直接改 rest 指针 |
O(1) | 引用别处会被连带改动 |
五、null 到底在什么时候触发异常
null 本身不会报错,解引用才会。
1 | public class NullPointer { |
输出:
1 | 声明 null 不报错,head == null -> true |
第二种比第一种更隐蔽。空链表的报错一眼可辨;而在一条长链上某个节点忘了初始化 next,报错位置和真正出错的位置可能隔着很远。链表代码写完,先用手画一遍指针走向,比直接跑测试更快定位。
六、小结
| 概念 | 一句话 | 证据 |
|---|---|---|
| 引用语义 | 变量装的是指针,赋值只复制指针 | b = a 后 a.weight 也变成 2000 |
== vs equals |
前者比地址,后者默认也比地址 | b.equals(c) → false |
| 递归基 | 必须判 rest == null,不能判 this == null |
size() 与 iterativeSize() 同为 5 |
| 不可变风格 | 修改 = 返回新链,原链不动 | M 变了,L.first 仍是 1 |
| NPE 触发点 | 解引用 null 才抛,声明不抛 |
head.value 抛,head == null 不抛 |
三条能带走的:
- Java 的变量是引用的持有者,不是对象的容器。 所有关于「赋值会不会影响另一个变量」的困惑,都从这一句出发。
- 链表这类结构的递归写法,递归基是「是不是最后一个节点」。 弄清楚这一点,
size、incrList到后面所有树形递归都是同一个模子。 - 不可变风格牺牲空间换取确定性。 后续的链表、树实现会反复在「改指针」与「造新节点」之间做这个取舍。

