对象与链表
一、[7, 9] is [7, 9] 为什么是 False
- 这一篇对应官方 Lecture 13(Objects)与 Lecture 14(Linked Lists),先讲「一切皆对象」和
is/==的区别,
很多人会愣一下:两个列表长得一模一样,凭什么不「是」同一个?
因为 is 问的根本不是「内容一样吗」,而是「是不是同一个对象」。两个字面量各自造了一个新列表,长得像不等于就是同一份。
这一篇先把这条区分讲清楚,因为它是链表、可变性、环境图题目的共同地基。
二、is 与 ==
1 | a = [7, 9] |
输出:
1 | True False True |
| 运算符 | 比什么 | a = [7, 9]; b = [7, 9] |
用在哪 |
|---|---|---|---|
== |
内容相等 | a == b → True |
判断两串数据是否等值 |
is |
身份相同(同一对象) | a is b → False |
判断「是不是它本身」 |
两个空列表也是两个对象,所以 e1 is e2 为 False。最后那行 x is y 为 True,是因为 CPython 对小整数做了驻留(缓存 -5 到 256)。
但这是实现细节,不是语言语义。 256 is 256 为 True、257 is 257 通常为 False,纯属 CPython 的缓存策略。判身份时只问「它俩是不是同一个对象」,不应拿小整数缓存当推理依据。
三、用函数表示数据
61A 有一个让人拍案的设计:数据不一定非要用数据结构来表示。
1 | def pair(x, y): |
输出:
1 | 3 4 |
pair 里没有任何数据结构——没有列表、没有元组、没有字典。它返回的只是一个闭包,靠 dispatch 这个「传消息」的参数决定往外吐哪个值。但对外看,first(p) 和 second(p) 的行为跟一个真二元组完全一样。
这就是消息传递(message passing)式的数据抽象:数据被表示成「一个接收消息的函数」。它提醒你,pair 的接口(first / second)才是抽象屏障;里面是列表、元组还是函数,调用方不需要知道——这正是抽象屏障思想在数据上的落地。
四、链表:递归定义的数据结构
链表的定义是一句递归的话:
一个链表,要么是空哨兵,要么由「第一个元素 + 剩下的那个链表」构成。
注意后半句——rest 本身又是一个链表。这正是在递归那一篇讲过的「同类子问题」:数据结构自己长了递归的形状,处理它的函数自然也该是递归的。
1 | class Link: |
输出:
1 | Link(1, Link(2, Link(3))) |
几个设计细节值得注意:
rest=empty用类属性当默认值。empty = ()是一个共享的哨兵对象,整个系列中所有空链表都是同一个()。这里用不可变的()当默认值很安全——不像rest=[],那样所有实例会共享同一个列表,是个经典 bug。__repr__递归输出。Link(1, Link(2, Link(3)))这行字是repr一层层拼出来的——f"{self.first}, {self.rest}"里的{self.rest}又触发了下一层的__repr__。empty是唯一表示。判空必须用is Link.empty,不要用t == ()——后者在值层面比较,语义不对。
五、递归遍历链表
1 | class Link: |
输出:
1 | 10 4 |
这两个函数是递归三件套的标准形态:递归基是「遇到空链表」,递归步骤是「处理 first + 递归处理 rest」。跟 count_partitions 是同一套思路,只是数据换了。
链表是递归数据结构,处理它的函数就该是递归的。 你几乎不需要多想。
flowchart LR
A["Link(1, ·)"] -->|rest| B["Link(2, ·)"]
B -->|rest| C["Link(3, ·)"]
C -->|rest| D["Link.empty = ()"]
A -.->|"first = 1"| A1["1"]
B -.->|"first = 2"| B1["2"]
C -.->|"first = 3"| C1["3"]
六、就地反转:指针游戏
链表反转的关键在于「三个指针同时挪」:
1 | class Link: |
输出:
1 | Link(3, Link(2, Link(1))) |
关键是这一行的平行赋值:
1 | cur.rest, prev, cur = prev, cur, cur.rest |
右边三件事先全部求值(此刻 cur.rest 还是老值),再一起赋回去。等价于三条语句:
1 | nxt = cur.rest # 先保存下一个,否则下一句就丢失了 |
顺序错了就断链。 这是链表题最经典的易错点:先改 cur.rest 再想记 nxt,后半截链表就找不回来了。
七、改一个,全跟着变
链表节点是可变对象,rest 只是指向它,所以就地改动会波及所有引用:
1 | class Link: |
输出:
1 | Link(9, Link(100, Link(2))) |
b 的尾巴跟着 a 一起变了,因为 b.rest is a。这正好呼应第二篇讲的浅拷贝——这是同一个对象被两个名字指着,不是两份数据。环境图最需要留意这种「共享结构」。
八、小结
| 概念 | 一句话 | 证据 |
|---|---|---|
is vs == |
身份 vs 内容 | [7,9] is [7,9] → False |
| 数据即函数 | 靠闭包 + dispatch 表示二元组 |
pair(3, 4) → first 得 3 |
| 链表定义 | 空哨兵,或 first + rest 链表 |
Link.empty 全系列唯一 |
| 判空 | 用 is Link.empty |
不要用 t == () |
| 遍历 | 撞空返回基值,否则 first + 递归 |
sum_links / length |
| 反转 | 三指针平行赋值,先记 nxt |
reverse(Link(1, Link(2, Link(3)))) |
| 共享结构 | rest 指向同一对象,改动会传播 |
改 a.first,b 也变 |
三条能带走的:
is问「是不是它」,==问「长得一样吗」。 判身份别拿小整数缓存当依据。- 链表是递归结构,遍历就写递归;要改结构就动指针。 判空永远用
is Link.empty。 - 链表节点是可变对象,
rest是引用不是副本。 改一处、动全身,画环境图最稳。

