### 6.5.1 鏈表 如前所述，列表是由許多數據按次序排列形成的一種數據結構，列表成員之間的邏輯關 系是由他們的排列次序表示的。例如，如果一群人按姓氏筆畫坐在一排相鄰的椅子上，那么 這些人的排列次序就表示了他們姓氏筆畫的關系，排在 1 號座位的人肯定是筆畫最少的，排 在 i 號座位上的人肯定比排在 i+1 號座位上的人筆畫要少（參見圖 6.4）。  圖 6.4 用排列次序表示數據間邏輯關系 這種連續排列的數據結構的優點是：僅憑排列次序（或相鄰關系）就知道成員數據之間的邏輯關系，而不需要另外存儲表示成員間邏輯關系的信息；可以通過位置信息（索引）對 任何成員進行隨機訪問，而不需要從頭開始一個一個查看。但連續存儲結構有也有缺點：如 果需要增加新成員，必須移動大量數據以便為新成員騰出空間；如果要刪除某個數據，刪除 后必須移動大量數據以便填補空缺、保持連續性。仍以圖 6.4 所示場景為例，如果新來了一 個姓“馮”的人要加入隊列，按數據邏輯關系他應當坐在“王”“孫”之間，因此必須使“王” 以后的所有人向右移動一個座位；如果“鄭”離開了，那么“周”和其后的所有人必須左移 一個座位。可見，插入、刪除操作的代價很大。 再看另一種場景：仍然是一群人要按姓氏筆畫順序排列，但這些人是東一個西一個隨便 站立著的，因此無法僅憑這些人所處的位置來判斷誰筆畫多誰筆畫少。這種情形下還有沒有 辦法表示他們的姓氏筆畫順序信息呢？當然有，例如我們可以讓每個人用手指著應該排在他 后面的那個人（圖 6.5）。這樣，雖然這群人站得雜亂無章，但是通過他們的手指，事實上形 成了一個有序的排列。注意，最后一個人沒有可指的對象，我們不妨讓他以手指地，表示這 是排列的末尾。  圖 6.5 用鏈接表示數據間邏輯關系 圖 6.5 形象地表示了一種以鏈接方式組織的列表，這種數據結構稱為鏈表（linked list）。 在鏈表中，成員之間的邏輯關系不是通過存儲位置的相鄰來表示，而是通過專門的鏈接信息 來表示。我們將鏈表中的成員稱為結點，每個結點都由兩部分信息組成：結點的數據和結點 的鏈接。結點的數據是實際應用要處理的數據，而結點的鏈接是對另一個結點的引用（或稱 指針），用于表示數據間的邏輯關系。鏈表中最后一個成員的鏈接必須設置為表示“無所指” 的某個特殊值。鏈表結構的第一個結點是整個鏈表的入口，通常用一個專門的變量來記錄鏈 表入口。鏈表的形狀如圖 6.6 所示。  圖 6.6 鏈表 鏈表可以很好地解決連續存儲列表的缺點。例如，如果圖 6.5 中新來了“馮”，那我們 只需讓“王”的手指改為指向“馮”，并讓“馮”指向“孫”；如果“鄭”要離開，我們只需 讓“吳”的手指改為指向“周”！ 然而，與普通列表相比，鏈表在訪問其成員數據時比較麻煩，因為無法通過位置信息來 隨機訪問鏈表成員。例如，我們無法直接讀取“鏈表的第 5 個結點”，為了進行這個操作， 必須從鏈表的頭開始，順著鏈接向后逐個檢查結點。 編程實例：鏈表的表示和處理 有的編程語言提供了指針類型（存儲單元的物理地址），可以很方便地表示鏈表結點之間的鏈接。但鏈接實際上是邏輯層的概念，不必非得用物理層的指針來實現。下面通過前述 按姓氏筆畫排序的例子來說明鏈表的表示及操作方法，其中鏈接是以結點在列表中的位置索 引實現的。 我們用包含兩個成員的列表[(name,strokes),link]來表示結點，其中第一個成員本身是二 元組，分別存儲姓氏 name 和筆畫數 strokes，第二個成員是鏈接 link。所有結點存儲在列表people 中，這里 people 相當于動態分配的存儲空間，結點在 people 中的位置索引就是結點 的“存儲地址”，結點的 link 值就是另一個結點的位置索引。因此，雖然結點是按隨機次序 存儲的，但所有結點按其 link 值前后相連就形成了一個鏈表。圖 6.7(a)展示了存儲空間中各 結點的物理存儲次序和由鏈接決定的邏輯次序，其中各個結點的值如圖 6.7(b)所示。我們另 外用變量 head 指向鏈表頭（此處即索引為 3 的“孫”結點）。  (a) (b) 圖 6.7 鏈表的表示 讀者應該注意到，people 中存儲的第一個結點很特別，這是我們設計的代表鏈表尾的特 殊結點。鏈表尾結點包含一個筆畫數高達 100 的假想姓氏 X，目的是使將來新結點總能在鏈 表尾之前找到插入位置，這樣可以使程序代碼更簡明。 現在來看如何在鏈表中插入新結點。我們首先利用 people.append()方法在存儲空間的尾 部建立新結點 N，然后再將 N 插入到鏈表中。具體插入過程是：從鏈表頭 head 開始，沿著 鏈接 link 查看鏈表，將沿途各結點與 N 比較，直至找到第一個筆畫數大于 N 的結點 M。然 后使 N 的 link 指向 M，而原先指向 M 的結點改為指向 N（參見圖 6.8）。這樣的 M 肯定能 找到，因為最壞情況下會找到鏈表尾，而那里有一個筆畫數為 100 的結點①。  圖 6.8 向鏈表中插入新結點 如圖 6.8 所示，為了在結點 L 和結點 M 之間插入結點 N，需要調整 L 和 N 的 link 值， 為此需要在查找鏈表的過程中記下連續兩個結點 L 和 M 的地址，這正是下列代碼中變量 p 和 q 的任務。插入結點的主要代碼如下： ``` p = head q = -1 while True: if people[p][0][1] <= people[tail][0][1]: q = p p = people[p][1] else: people[tail][1] = p if q &gt;= 0: people[q][1] = tail else: head = tail break ```  > ① 據說筆畫數最多的漢字是由四個“龍”組成的，共 64 畫。 解決了結點插入鏈表的問題，則鏈表的創建問題就變得很平凡了。從空鏈表（實際上有 一個特殊的鏈表尾結點）開始，每次根據用戶輸入的姓氏和筆畫數建立新結點，并調用結點 插入算法，重復這個過程即可創建整個鏈表。程序 6.4 實現了這個功能。 【程序 6.4】linkedlist.py ``` from string import split def insert(llist,head,tail): p = head q = -1 while True: if llist[p][0][1] <= llist[tail][0][1]: q = p p = llist[p][1] else: llist[tail][1] = p if q >= 0: llist[q][1] = tail else: head = tail break return head def main(): people = [[('X',100),-1]] head = 0 s = raw_input("Enter name and strokes: ") while s != "": s2 = split(s,',') name,strokes = s2[0],eval(s2[1]) people.append([(name,strokes),-1]) tail = len(people)-1 head = insert(people,head,tail) s = raw_input("Enter name and strokes: ") print "Physical order:", for i in range(1,len(people)): print people[i][0][0], print print "Logical order:", p = head while people[p][1] >= 0: print people[p][0][0], p = people[p][1] main() ``` 主程序首先創建空鏈表（實際上包含特殊的鏈表尾結點），然后由用戶按“姓氏，筆畫”格 式輸入數據，程序在 people 末尾建立對應的新結點（相對于為新結點分配存儲空間），接著 調用 insert 函數將新結點插入到鏈表中。重復輸入數據、存儲新結點、插入新結點的過程直 至輸入為空，最后分別按 people 中的結點次序（物理存儲次序）和鏈接的次序（邏輯次序） 顯示所有結點的姓氏。下面是程序的一次執行過程和結果： ``` Enter name and strokes: 趙,9 Enter name and strokes: 錢,10 Enter name and strokes: 孫,6 Enter name and strokes: 李,7 Enter name and strokes: 周,8 Enter name and strokes: 吳,7 Enter name and strokes: 鄭,8 Enter name and strokes: 王,4 Enter name and strokes: Physical order: 趙 錢 孫 李 周 吳 鄭 王 Logical order: 王 孫 李 吳 周 鄭 趙 錢 ``` 圖 6.9 是最終結果的示意圖。  圖 6.9 輸入 8 個姓氏之后的結果 程序 6.4 只實現了鏈表的插入功能，作為練習，讀者可以嘗試為程序增加查找、刪除等 功能。 以上介紹的是最簡單的單鏈表。為了更有效地處理鏈表，還可以設計雙鏈表、循環鏈表 等結構。事實上，利用鏈接，還可以設計各種各樣的非線性數據結構，如樹和圖等等。有關 內容可閱讀數據結構教材。