链表通过节点之间的引用存储序列,而不是将元素放在连续的数组位置。它的一个局部优势是:若已经得到所需节点,操作便可只改动少量链接,而不必移动序列中的其他元素。不过,这一说法需要限定:寻找节点可能代价很高;而正确的链接必须保持一个连贯的链表,不能形成几个互不连通的环。
我们用含一个哨兵的循环环表示双向链表。哨兵是标记边界的真实节点,但不承载序列元素。这样,空链表的插入以及两端插入都遵循同一条局部规则。接下来我们会在链表之间移动节点,辨别必须小心处理的别名情况,并说明较大区间的拼接有哪些部分是常数时间,哪些不是。
区分节点身份与存储的值
每个数据节点都有一个值,以及 prev 和 next 引用。两个节点即使存储相等的值,仍可以是不同对象。句柄是指向某个特定节点的引用;使用句柄的操作无需先按值搜索。
哨兵通过对象身份识别,而不是通过某个特殊值识别。在下面的实现中,哨兵存储 None,但普通数据节点也可以存储 None。若用值判断代替身份判断,就会错误地把这样的合法数据节点当作边界。
常见错误
(用值来识别哨兵)
假设 values() 在 node.value is None 时停止,而不是在 node is self.root 时停止。执行 a.append(None) 和 a.append(3) 后,链表有两个数据节点,长度为 ;但遍历从第一个数据节点开始,看到值 None 就立即停止,返回空序列。身份判断则返回 [None, 3]。数据值绝不能决定某个节点是不是边界。
定义 10.1.1
(哨兵环的表示不变量)
设 是唯一哨兵, 是表示该链表的数据节点集合。要求以下条件全部成立:
- 从 出发不断沿
next前进,恰好访问 的每个成员一次,然后返回 ,且不访问其他节点。 - 对 中每个节点 ,两个链接互为逆向链接:
- 存储的
size是 ,不包括哨兵。不同链表对象的数据节点集合互不相交,且哨兵不同。
空链表中, 为空,size 为零,哨兵的两个链接都指回 自身。
抽象序列就是从哨兵之后依次遇到的数据值。不变量所说的不只是“每个节点都有两个引用”:它还规定了可达性、顺序、边界行为和元素数量。
反例模式
局部互逆的链接仍可能形成错误的全局结构
构造一个包含哨兵和部分节点的循环环,再构造另一个与之不相交的循环环,其中放置本应属于同一链表的其他节点。两个环里的每个节点都可以满足上面的互逆等式。
仅凭这些等式,不能说明从哨兵可以到达所有预期成员。证明链表更新正确时,除了附近的链接等式,也必须保持单环成员条件。检查某个节点的两个邻居,也不能证明它属于调用者提供的链表。
在已知锚点之前插入
锚点是目标环中的一个成员,也可以是其哨兵。在哨兵之前插入相当于在末尾追加;在第一个数据节点之前插入相当于在开头添加。链表为空时,这两个位置重合。
设 是锚点,。对于一个新建的、尚未连接的数据节点 ,将相邻连接 替换为
依次设置 x.prev = left、x.next = anchor、left.next = x 和 anchor.prev = x,然后将长度加一。覆盖用于识别邻居的链接之前,应先保存该邻居。
命题 10.1.2
(在锚点之前插入)
设环满足表示不变量, 是其成员(哨兵或数据节点), 是已脱离的节点。先保存 ,再设置 x.prev = left、x.next = anchor、left.next = x、anchor.prev = x,并将长度加一。环仍满足不变量,其序列就是旧序列,在 之前紧接插入 。
证明
(拆分一条连接)
新节点原先不属于任何环。所有旧节点的相对顺序保持不变,只是从 到 的连接现在经过 。因此,向前遍历恰好多访问一个节点,并仍返回同一个哨兵。
四次赋值使两条新连接都满足互逆关系,而未受影响的连接保留原来的引用。长度加一与数据节点集合的增加相符。这个论证同样适用于空链表:此时 ,结果是由 和 构成的双节点环。
哨兵消除了改接规则中对两端的特殊处理,但仍需说明锚点有效、插入的节点未连接。下面的教学实现会为公开插入操作创建新节点,因此该操作自动满足未连接条件。
删除已知数据节点
对于属于源链表的数据节点句柄 ,保存 和 。设置 left.next = right 和 right.prev = left,绕过 ,并将长度减一。随后辅助函数将 的两个链接设为 None,标记它已脱离链表。
命题 10.1.3
(删除数据节点)
设环满足不变量, 是其中一个数据节点。先保存 和 ,设置 left.next = right 和 right.prev = left,并将长度减一。环仍满足不变量,其序列就是旧序列去掉 。
证明
(绕过一个节点)
原来的遍历依次经过 ;新的遍历依次经过 ,其余成员的顺序不变。替换后的连接满足互逆关系,可达的数据节点集合恰好失去 。
如果 是唯一的数据节点,那么两个邻居都是哨兵;赋值会恢复哨兵的两个自链接。绝不能删除哨兵本身,因为它定义环的边界,而不代表一个元素。
证明透视
为何局部更新能保持整体不变量
仅靠互逆的链接并不能推出单一环,上面的反例已说明这一点。两个证明是从改动的形状得到整体条件的:插入把连接 换成路径 ,删除则把两条连接组成的路径换成一条。两种情况下,从哨兵出发的向前遍历,都是旧遍历恰好多一个或少一个节点,所以单一环的成员条件得以继承。互逆性只需在被改动的连接上重新检查,因为没有写入其他节点的链接。赋值顺序也是同样的原因:必须在覆写 anchor.prev 之前读取 ,并在清除 的链接之前读取 。
脱离链表的句柄仍然引用一个存活的节点对象。它的值仍然存在,但它已不是成员,不能再合法地传给只接受成员的操作。清除它的链接并不能证明另一个任意句柄属于正确的链表。
例题 10.1.4
(空环:先插入,再删除)
从空链表开始:root.prev = root.next = root,长度为 。调用 insert_before(root, 5) 先保存 ,设 、,然后 left.next = x 使 ,anchor.prev = x 使 。长度为 ,values() 是 。再执行 erase(x):保存的两个邻居都是哨兵,所以 left.next = right 与 right.prev = left 恢复哨兵的两个自链接;长度回到 , 的链接为 None。同样的赋值规则在空环上与在长环上一样适用,不需要两端的分支。
不复制值地移动一个节点
要将成员 从源链表 移到目标链表 的锚点 之前,先从源环中拆下 ,再把同一个节点接到目标环中 的前面。当 时,源长度减一,目标长度加一。在同一个链表内移动时,长度不变。
同一链表内有两种请求本来就描述现有顺序:
- 将 移到它自己之前,是空操作。
- 将 移到它当前的下一个节点之前,也是空操作,包括该下一个节点是哨兵的情况。
应在拆下节点之前识别这些情况。其他情况下,必须在拆下节点之后取得目标位置的前驱。原环中缓存的前驱可能正是正在移动的节点,也可能与已被删除操作改变的连接有关。
反例模式
在拆下之前缓存左邻居
假设移动写成:先读 left = anchor.prev,再拆下 ,然后把 接在 left 与 anchor 之间。取哨兵为 、数据节点为 的链表,把 移到其当前后继 之前。此时 ,正是被移动的节点。拆下 后剩下 。接入时先设 、,再由 left.next = p 使 ,并设 。结果 ,但 ,而 是 无法到达的自环,所以两个条件都不成立。实现避免这个问题的方法,是当锚点是 或其后继时提前返回,并且只在拆下之后才读取 anchor.prev。
例题 10.1.5
(句柄随节点在不同序列之间移动)
设链表 的节点 依次存储 ,链表 的节点 存储 2。
| 操作 | A 中的值 | B 中的值 | 长度 (A, B) |
|---|---|---|---|
| 初始状态 | |||
| 将 q 从 A 移到 B 的哨兵之前 | |||
| 将 q 从 B 移到 A 的 p 之前 | |||
| 在 A 中将 q 移到自身之前 | |||
| 将 q 移到它的下一个节点 p 之前 | |||
| 从 A 删除 p |
句柄 始终指向同一个节点;它所属的链表发生变化,但没有通过复制值来创建替代节点。删除 后,它的值仍是 4,两个链接均为 None。再次将 传给 erase 会违反该操作的成员前提。
一个明确规定句柄前提的小型实现
对于 insert_before,锚点必须属于该链表,也允许其哨兵。对于 erase 和 move_before,源节点必须是源链表当前的数据成员。移动操作的锚点必须属于目标链表,也允许目标哨兵。这些归属条件是前提,不是代码执行的全局检查。显式的哨兵检查不能验证任意句柄的归属。
class Node:
__slots__ = ("value", "prev", "next")
def __init__(self, value):
self.value = value
self.prev = self.next = None
class SentinelList:
def __init__(self):
self.root = Node(None)
self.root.prev = self.root.next = self.root
self.size = 0
@staticmethod
def _attach_before(anchor, node):
left = anchor.prev
node.prev = left
node.next = anchor
left.next = node
anchor.prev = node
@staticmethod
def _detach(node):
left, right = node.prev, node.next
left.next = right
right.prev = left
node.prev = node.next = None
def insert_before(self, anchor, value):
node = Node(value)
self._attach_before(anchor, node)
self.size += 1
return node
def append(self, value):
return self.insert_before(self.root, value)
def erase(self, node):
if node is self.root:
raise ValueError("the sentinel is not a data node")
self._detach(node)
self.size -= 1
return node.value
def move_before(self, node, target, anchor):
if node is self.root:
raise ValueError("the sentinel is not a movable data node")
if self is target and (anchor is node or anchor is node.next):
return
self._detach(node)
self._attach_before(anchor, node)
if self is not target:
self.size -= 1
target.size += 1
def values(self):
result = []
node = self.root.next
while node is not self.root:
result.append(node.value)
node = node.next
return result
在上例中,创建 a = SentinelList() 和 b = SentinelList(),然后依次使用 p = a.append(4)、q = a.append(7)、u = a.append(9) 和 t = b.append(2)。两次转移分别是 a.move_before(q, b, b.root) 和 b.move_before(q, a, p)。之后 a.values() 为 [7,4,9],b.values() 为 [2]。
对于有效句柄,每次更新只执行常数次引用读取和写入。插入新节点还需要分配一个节点。对于长度为 的链表,枚举序列的 values() 需要 时间和输出存储;它不属于常数时间更新的断言。链表本身使用 节点存储和一个额外哨兵。
不要忽略寻找节点的成本
基于句柄的插入或删除只需 的指针工作。在第 个元素的位置插入并不自动是 :操作可能必须先找到该元素。对于从零开始的有效下标 ,从较近的一端行走需要
时间;寻找中间位置在最坏情况下需要线性时间。搜索特定值通常也需要线性时间,而相等的值可能对应多个身份不同的节点。
这说明了链式节点何时有用。如果另一个结构已经提供所需句柄,链表就可以局部调整顺序,而无需移动大量元素。如果工作负载主要请求任意下标的元素,数组的常数时间索引可能更有用。操作的总成本包括定位其参数,而不只是最后几次链接赋值。
区间拼接揭示另一项隐藏成本
设一个非空、沿 next 连续的数据节点区间从 first 延伸至 last,途中不经过源哨兵。目标锚点位于该区间之外。区间内部的链接已经具有所需顺序,因此无须更改。
将 first.prev 与 last.next 双向连接,切开源边界。然后在切开后的环中取得 anchor.prev,把该节点与 first 双向连接,并把 last 与 anchor 双向连接。这一过程写入六个引用字段,与移动的节点数 无关。如果锚点是同一链表中该区间原来的下一个节点,切开后重新计算其前驱会正确地恢复原有顺序。
但在两个链表之间移动区间,还须将各自存储的长度改变 。仅知道两个端点句柄本身,并不能得到 。遍历计数需要 ;扫描以验证连续性或归属也需要时间。因此,边界改接是常数时间,并不保证一个对任意区间进行完整验证并维护长度的 API 也是常数时间。要声称后者为常数时间,必须事先知道长度或有额外的支持结构。上面的实现只移动一个节点,长度变化已知为一。
例题 10.1.6
(在两个链表之间移动两个节点的区间)
设 是 ,节点为 ,哨兵为 ; 是 ,节点为 ,哨兵为 。把从 到 的区间移到 之前。切开源链表,连接 ,得 。目标位置的邻居是 ;连接 与 ,得 。共六次写入:n1.next、n4.prev、m.next、n2.prev、n3.next、r_B.prev。取 ,长度由 变为 ,而 是从 走到 数得的,需要 。
同一链表中的边界情形:把同一区间移到其原来的后继 之前。切开后 ,重新取得 ,连接 和 ,就还原为 。
练习与详解
快速检查
(不使用端点特例,向空环插入)
哨兵的两个链接都指向自身。在它之前插入新节点 x。写出两个节点各自的 next 和 prev 引用。如果 x 的数据值是 None,它会成为哨兵吗?
解答 · 答案
哨兵的两个链接都指向 ,而 的两个链接都指向哨兵。存储的长度变成一。数据值 None 不会使 成为哨兵:哨兵是特定的 root 对象,通过身份识别。
快速检查
(跟踪例子中转移的句柄)
先将 q 移到 B,再移到 A 的 p 之前后,两个序列及其长度分别是什么?删除 p 后,仍保留的句柄指向什么?按契约能否再次从 A 删除它?
解答 · 答案
两次转移后,、,长度分别为三和一。删除 后, 变成 ,长度为二。句柄仍指向包含 4 的脱离节点,两个链接均为 None;它不再是成员,故再次从 删除会违反前提。
快速检查
(识别单节点移动的两种空操作)
为什么在同一链表中,将 x 移到自己之前或移到当前下一个节点之前都是空操作?如果通过拆下再接回处理后一种情况,为什么在拆下之前缓存 anchor.prev 很危险?
解答 · 答案
两种情况中,请求的位置都与现有顺序一致。如果锚点是 自身,拆下后它不再是有效的目标锚点。如果锚点是下一个节点,它原来的前驱是正在被拆下的 ;重用该缓存引用可能通过已移除的节点连接,而不是连接剩余的环。应先识别空操作,并在真正移动时于移除后重新计算目标邻居。
快速检查
(判断互逆指针不能证明什么)
两个互不连通的循环分量各自都满足 next.prev 和 prev.next 的互逆关系。为什么这不足以证明它们构成以指定节点为哨兵的一个链表?哪个表示条件补足了缺失的信息?
解答 · 答案
这些等式描述局部的互逆连接,却不能证明哨兵可以到达所有预期成员。单环可达性条件要求从哨兵出发的遍历在返回前恰好访问每个数据成员一次,且存储的长度与该集合一致。不连通的第二个分量违反这一全局条件。
快速检查
(比较已知句柄和按下标定位)
删除操作以常数时间改变相邻的两个链接。这是否意味着在普通链表中按数字下标删除中间元素也是常数时间?写出有效零基下标 k 从较近端搜索的时间界。
解答 · 答案
不是。除非已提供句柄,否则必须先找到节点。对于长度 和 ,从较近端遍历需要 ,寻找中间位置为 。只有随后的局部删除使用常数次指针操作。
快速检查
(区分区间改接与长度维护)
一个已知连续区间在两个存储长度的链表之间移动,其端点链接可以用六次写入改接。更新长度还需要哪个数?如果必须遍历才能得知,时间界会怎样?
解答 · 答案
需要区间的精确长度 :从源长度减去 ,再给目标长度加上 。尽管边界改接是常数时间,遍历区间计数需要 。仅有端点句柄,并不能在常数时间内得到该数量。