淺談鏈表–數據結構的重要根基
- 2019 年 11 月 13 日
- 筆記
鏈表是什麼
鏈表、列表，說起來有點相似，作用也有點類似，但可別傻傻分不清楚。我們一般說的列表，是一個連續的序列，用來存儲一組數據。而鏈表，雖然也是有序的存儲結構，但它不限定要「連續」的。
打個比方：列表就好像火車，每一節車廂連在一起，如果你知道車頭在哪裡，大致就也能知道第8節車廂在哪。
而鏈表，就像是去往同個目的地的車隊，有很多輛車，大家排着隊行駛。雖是一個整體，但隊伍的順序是可以很容易調整的。
從概念定義上來說，鏈表是一種以線性順序存儲的數據結構，但並不要求按順序存儲。它由節點組成，每個節點除了儲存自身數據外，還包含一個指向下一個節點的引用（或指針）。
這就是一個包含5個節點的鏈表示意圖：
通常，我們會有一個 head 引用指向鏈表的開頭，而鏈表的結尾，下一個節點則指向空值 None。
除了上圖演示的單向鏈表外，還存在雙向鏈表（每個節點還增加一個指向前一個節點的引用）和循環鏈表（最後一個節點的下一個節點會指向第一個節點）。
鏈表有什麼用
老問題又來了：為什麼要有鏈表？
鏈表相較順序存儲列表，最大的好處就是很容易往序列中添加和刪除元素，單看插入和刪除操作，最優可達到O(1)的複雜度。這個從上面舉的火車和車隊的例子就可以想像出來。另外，鏈表的好處還有不需要連續的存儲空間，且不需要預先知道數據集的大小。
但鏈表也有它的不足，就是如果你要查找某個節點，或訪問指定序號的節點，效率則比較低。
所以，鏈表更適合需要頻繁增刪元素但很少查找元素，或者無法預知數據規模的場景。
舉一個例子：玩過格鬥遊戲的人，都知道有個「搓招」的設定，就是你按下一定順序的按鍵（如 →↓↘→AB），就會觸發角色的特殊招式。當玩家操作角色時，會不停按下各個按鍵，這時如果你想判斷最近的按鍵組合是否符合某一固定招式，就可以用鏈表來記錄最近的按鍵歷史，並且在過程中不斷更新。
那麼，為何我們標題說鏈表是數據結構的重要根基呢？因為從上面的描述我們可以看出，鏈表的節點是非常靈活的，可以組織成不同的結構。例如我們上次提到的棧，就完全可以改為用鏈表實現。其他的一些數據結構，如隊列、樹、圖，一些算法，如 LRU（最近最少使用算法），文件系統等，均會用到鏈表這種數據結構。
最近又火起來的概念：區塊鏈，它也是某種意義上的鏈表。
鏈表的實現
我們用 Python 語言來自己實現一個單向鏈表結構，以加深理解。
功能需求：
創建一個 SingleLinkedList 類，具備以下功能：
- SingleLinkedList() – 創建新的單鏈表，不需要參數，返回空鏈表。
- addFirst(item) – 將元素添加到鏈表頭，需要參數，無返回值。
- remove(item) – 刪除鏈表內元素，需要參數，並修改單鏈表的內容。
- isEmpty() – 檢查單鏈表是否為空，不需要參數，返回布爾值。
- length() – 返回單鏈表中元素個數，不需要參數，返回整數。
開發思路：
照例先來幾張示意圖，理一下上述幾個功能：
1. 創建節點、單鏈表並 addFirst(item)
2. 繼續 addFirst(item) 添加節點。
3. 多次添加節點後就會出現我們開頭的單鏈表。
4. 刪除儲存數據為4的頭部節點
5. 刪除鏈表中間儲存元素為2的中間節點
在刪除鏈表元素的過程包含兩個步驟：
1. 遍歷鏈表，找到刪除的元素。我們從 head 節點找起，直到 next 節點為 None 的尾部節點
2. 當找到元素後，將其前一個節點的 next 節點指向它原本的 next 節點，也就實現了從列表中刪除元素
代碼實現：
class Node: def __init__(self, initdata): self.data = initdata self.next = None def __str__(self): # 方便後續輸出觀察數據 return str(self.data) class SingleLinkedList: def __init__(self): self.head = None # 記錄頭部節點 self.size = 0 # 記錄鏈表長度 def isEmpty(self): return self.head == None def addFirst(self, item): temp = Node(item) # 創建節點 temp.next = self.head # 新節點指向原先的頭節點 self.head = temp # 重新指向頭節點 self.size += 1 def remove(self, item): currentNode = self.head # 查找節點，從頭部節點開始 found = False # False 表示還沒找到要刪除的節點 previous = None # 記錄當前節點的前一個節點，當刪除節點為頭節點時，previous 等於 None while currentNode != None and not found: # 尾節點指向 None，所以currentNode != None, 表示鏈表還沒有查找完。 if currentNode.data == item: # 發現數據 found = True else: # 沒有找到節點，就接着向下一個節點尋找 previous = currentNode # 記錄當前節點的上一個節點 currentNode = currentNode.next # 將當前節點向下一個節點移動 if not found: # 數據不存在鏈表中 raise raise ValueError('SingleLinkedList.remove(item): item not in SingleLinkedList') if previous == None: # 發現要刪除的節點是頭節點 self.head = currentNode.next else: # 要刪除的節點是中間節點或尾部節點 previous.next = currentNode.next # 將當前節點的上一個節點指向當前節點的下一個節點 self.size -= 1 def length(self): return self.size if __name__ == '__main__': u = SingleLinkedList() u.isEmpty() print(u.head) u.addFirst(4) print(u.head) u.addFirst('dog') print(u.head) u.addFirst(True) print(u.head) u.addFirst('ok') print(u.head) u.remove('dog') print(u.head) u.length()
以上便是一個單鏈表的 Python 實現。
