前面几篇，我刻意没让你碰"改掉一个已有的值"。因为**可变性（mutability）**是 CS61A 乃至整个编程里"便利"和"灾难"同一个源头。
它能让代码更短更自然，也能让 bug 在最意想不到的地方炸——而且炸得毫无痕迹。
本篇先把"可变 vs 不可变"这条生死线划清，再看别名、容器，最后动手实现 CS61A 两尊经典递归结构：Link 与 Tree。

一、可变 vs 不可变：一条分界生死线

是什么：

  • 不可变（immutable）：创建后内容不能改。int、float、str、tuple、frozenset 都在此列。你做的任何"修改"其实是生成新对象。
  • 可变（mutable）：创建后内部可改。list、dict、set、以及你自己写的类实例都在此列。改的是"同一个对象"。
1
2
3
4
5
s = "abc"
# s[0] = "x"        # 报错：str 不可变
lst = [1, 2, 3]
lst[0] = 99         # list 可变，OK
print(lst)          # [99, 2, 3]

输出：

1
[99, 2, 3]

坑（最反直觉的一点）：字符串"看起来"被改了，其实是返回了新字符串。下面这段代码暴露了无数人的误解：

1
2
3
4
def bad(s):
    s.upper()           # 返回新字符串，但没接住
    return s
print(bad("hi"))        # "hi"  —— 原串根本没变！

upper() 不改原串，只是返回新串。忘记"接住返回值"是字符串处理里最高频的 bug。正确写法是 s = s.upper() 或 return s.upper()。

本质一句话：不可变 = 改即新建；可变 = 改即原地。分清两者，就避开了大半"值怎么不对了"的灵异事件。

二、别名与共享引用：盒子与指针模型

是什么：可变对象最坑的特性是别名（aliasing）——两个名字指向同一个对象。改其中一个，另一个"看"到的也变了，因为它们本来就是一个东西。

1
2
3
4
a ──┐
    ▼
  [1, 2, 3, 4]   ←── b      （a、b 共享同一对象）
c ──▶ [1, 2, 3, 4, 5]        （c 是独立副本）
1
2
3
4
5
6
7
8
a = [1, 2, 3]
b = a                # b 和 a 是同一个列表的别名（没复制！）
b.append(4)
print(a)             # [1, 2, 3, 4]   ← a 也变了！

c = a[:]             # 切片做出"浅副本"，不再是别名
c.append(5)
print(a, c)          # [1, 2, 3, 4] [1, 2, 3, 4, 5]

输出：

1
2
[1, 2, 3, 4]
[1, 2, 3, 4] [1, 2, 3, 4, 5]

判定是否共享：用 a is b（比身份/内存地址）才是真问"是不是同一个对象"；== 只比值是否相等。两个内容相同的不同列表，== 为真但 is 为假。

坑：函数参数也是按"引用"传的（准确说传的是对象）。你把一个列表传进函数，函数里对它 append，调用者的原列表也被改了——这常被当成"凭空出现的改动"。若不想被改，进函数时先 .copy()。

本质一句话：可变对象的别名 = 多个名字共享同一块内存；is 看身份、== 看值，想独立就得显式复制。

三、容器：dict 与 set

是什么：dict 是键值对（哈希表），set 是无序不重复集合，二者都是可变容器。

1
2
3
4
5
6
7
8
9
d = {"name": "Ada", "age": 36}
print(d["name"])          # Ada
d["age"] = 37             # 改值
d["lang"] = "Python"      # 增键

s = {1, 2, 2, 3}          # set 自动去重
print(s)                  # {1, 2, 3}
s.add(2)                  # 已有，静默忽略
print(len(s))             # 3

输出：

1
2
3
Ada
{1, 2, 3}
3

坑：dict 用 [] 访问不存在的键会抛 KeyError。安全取法是用 d.get(key, default)，键不存在时返回默认值而非崩溃。这是写健壮代码的基本功。

四、Link：CS61A 经典递归链表

是什么：Link 是 CS61A 自造的递归链表——每个节点由 first（首元素）和 rest（指向下一个 Link，或 Link.empty 表示结尾）组成。它和篇二讲的内置 list 不同，是自己定义的数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Link:
    empty = ()                       # 用空元组表示"没有更多"
    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest
    def __repr__(self):
        if self.rest is Link.empty:
            return f'Link({self.first})'
        return f'Link({self.first}, {self.rest})'

ll = Link(1, Link(2, Link(3)))
print(ll)                 # Link(1, Link(2, Link(3)))
print(ll.rest.first)      # 2

输出：

1
2
Link(1, Link(2, Link(3)))
2

它是递归数据结构：每个 rest 又是一个 Link，天然和递归遍历配对。比如"把链表里每个数翻倍"：

1
2
3
4
5
6
def double(ll):
    if ll is Link.empty:
        return Link.empty
    return Link(ll.first * 2, double(ll.rest))

print(double(ll))         # Link(2, Link(4, Link(6)))

坑：判断"链表到头"必须用 is Link.empty（身份比较），不能用 == 或判断 None——empty 是个哨兵对象，语义上是"类型层面"的结束标记。

本质一句话：Link 是"首元素 + 指向下一个的递归结构"，遍历用递归最自然，结尾用哨兵 empty 标识。

五、Tree：分支的递归结构

是什么：Tree 有一个 label（根的值）和若干 branches（子树的列表），是比链表更一般的递归结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Tree:
    def __init__(self, label, branches=()):
        self.label = label
        for b in branches:
            assert isinstance(b, Tree)     # 防御：分支必须也是 Tree
        self.branches = list(branches)
    def __repr__(self):
        if not self.branches:
            return f'Tree({self.label})'
        return f'Tree({self.label}, {self.branches})'

t = Tree(3, [Tree(1), Tree(2, [Tree(4)])])
print(t.label, [b.label for b in t.branches])   # 3 [1, 2]

输出：

1
3 [1, 2]

坑：__init__ 的默认参数 branches=() 用了不可变元组——这是对的。若写成 branches=[]（可变默认参数），所有没传分支的 Tree 会共享同一个列表，造成跨实例污染（参见篇二 lambda 之外的另一个"可变默认参数"大坑）。

本质一句话：Tree = 根标签 + 子树列表的递归结构；可变默认参数要用不可变占位，防共享污染。

小结

  • 不可变（int/str/tuple）：改即新建；可变（list/dict/set/实例）：改即原地。
  • 别名让多个名字共享同一对象，改一处影响多处；is 比身份、== 比值，独立需显式复制。
  • dict 用 get 防 KeyError；set 自动去重。
  • Link / Tree 是递归结构，遍历用递归最自然；结尾哨兵用 is 判断，默认参数用不可变。