鏈表用節點之間的參照儲存序列,而不是把元素放在連續陣列位置。它的主要局部優點,是已取得相關節點後,只須改動少量連結,毋須移動序列其餘元素。但這句話有條件:找到節點可能很昂貴,而正確連結必須保留一條完整串列,不能只剩幾個互不相連的環。
本節以一個含哨兵的循環環表示雙向鏈表。哨兵是一個真正的節點,用來標記邊界,卻不代表序列元素。這令空串列插入與兩端插入都能使用同一局部規則。之後我們會在兩條串列之間移動節點,指出必須小心處理的別名情況,並說明較大範圍拼接中,哪些工作是常數時間、哪些不是。
分清節點身分與儲存的值
每個數據節點有數值、prev 參照及 next 參照。兩個節點即使儲存相等數值,仍可以是不同物件。節點參照(handle)是指向某個特定節點的參照;使用它的操作不會先按數值搜尋。
辨認哨兵靠的是物件身分,而不是特殊數值。實作中它儲存 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() 需要 時間和輸出空間,不屬於常數時間更新的聲稱。串列本身佔 節點空間,另加一個哨兵。
不要隱藏尋找節點的成本
給定節點參照的插入或刪除只需 指標工作,但在第 個元素的位置插入,不會自動變成 :操作可能須先找到該元素。對合法零起始下標 ,從較近的一端走過去需要
時間;尋找中間位置的最壞成本仍為線性。搜尋特定數值一般也要線性時間,而相同數值可以對應多個不同節點身分。
這說明鏈結節點適合甚麼情況。若另一個結構已提供相關節點參照,串列就能局部重排,而毋須移動大量項目。若工作主要是任意下標存取,陣列的常數時間索引可能更合適。操作的完整成本包括找到引數,而不只是最後幾次連結賦值。
範圍拼接揭示另一項隱藏成本
假設一段非空、沿向前次序連續的數據節點範圍,由 first 到 last,中途不經過來源哨兵。目的錨點不在該範圍內。範圍內部連結已具有所需次序,所以毋須改動。
先把 first.prev 與 last.next 雙向接起,切開來源邊界。然後在切開後的環取得 anchor.prev,把它與 first 雙向連接,再把 last 與 anchor 雙向連接。這只需六次參照欄位寫入,與被移動節點數 無關。同一串列中,若錨點就是範圍原本的下一節點,在切開後重新取得其前一鄰居,便能正確還原原次序。
但跨串列移動範圍,亦會令兩邊儲存長度改變 。知道兩個端點的節點參照,本身不代表已知道 。遍歷計數需要 ;掃描以驗證連續性或所屬關係也需要時間。因此,常數時間邊界重接,並不保證任意範圍的完整驗證及長度維護介面也是常數時間。要作此聲稱,必須預先有長度或其他支援結構。以上實作只移動一個節點,對長度的影響已知為一。
例題 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 會有危險?
解答 · 答案
兩種請求都已符合目前位置。若錨點就是 ,它會被脫離,不再是有效目的錨點。若錨點是下一節點,其舊 prev 就是正在脫離的 ;重用該快取可能經被移除節點連接,而不是接到剩餘環。應先辨認不改動情況,真正移動時則在移除後重新取得目的鄰居。
快速檢查
(指出互逆指標不能證明甚麼)
兩個互不相連的循環分量,都滿足 next.prev 與 prev.next 互逆。為甚麼不足以證明它們是一條具有指定哨兵的串列?哪項表示條件補上欠缺的事實?
解答 · 答案
等式只描述局部互逆連接,不能證明哨兵可到達所有應有成員。單一環可達性要求從哨兵遍歷,恰好訪問所有數據成員一次再返回,並使儲存長度符合該集合。第二個不連通分量違反這個整體條件。
快速檢查
(比較已知節點與下標位置)
刪除只改動兩條鄰接連結,成本為常數。這是否令裸鏈表按數值下標刪除中間元素也成為常數時間?寫出合法零起始下標 k 的近端搜尋界限。
解答 · 答案
不是。除非已提供節點參照,否則必須先找到節點。長度 、 時,近端遍歷成本為 ,中間位置為 。只有之後的局部刪除是常數指標工作。
快速檢查
(分清範圍重接與長度維護)
在兩條有儲存長度的串列之間移動一段已知連續範圍,端點連結可用六次寫入重接。更新長度還需要哪個數字?若必須遍歷才能取得它,時間界限如何改變?
解答 · 答案
需要精確範圍長度 ,從來源長度減去,再加到目的長度。即使邊界重接為常數工作,遍歷範圍計數仍需 。只有端點節點參照,不能令這個數量自動在常數時間取得。