算法系列之鏈表基本原理---超市購物隊列的故事
想了個生動的方式來解釋鏈表基本原理
想象你在一個超市排隊結賬，每個人都是一個節點，每個人手里拿著一張票據（數據），而每個人的背上都貼著一個指示牌，指示牌指向下一個排隊的人。這就是一個單向鏈表。
1. 什么是鏈表？
在現實中，鏈表就像排隊的人，每個人知道自己后面是誰，但不知道前面是誰。這個鏈表的特點是，每個人（節點）只知道下一個人（節點）的信息，而不知道前一個人。
2. 鏈表的類型
單向鏈表：
- 每個人（節點）只知道下一個人（節點）的信息。
雙向鏈表：
- 每個人（節點）不僅知道下一個人（節點），還知道前一個人（節點）的信息，就像每個人都可以和前后兩個人聊天。
循環鏈表：
- 最后一個人（節點）知道第一個人（節點），這樣隊伍就首尾相連，形成一個圈。
3. 鏈表的基本操作
3.1 創建鏈表
我們先創建一個空的隊伍：
class Node: def __init__(self, data): self.data = data # 票據（數據） self.next = None # 指向下一個人的指示牌（指針） class LinkedList: def __init__(self): self.head = None # 隊伍的第一個人（頭節點）
3.2 在隊伍尾部加入新的人
每當有新人加入隊伍，我們需要找到隊伍的末尾，然后把新人加進去：
def append(self, data): new_node = Node(data) # 新人拿著票據 if not self.head: # 如果隊伍是空的 self.head = new_node # 新人成為第一個人 return last = self.head while last.next: # 找到隊伍的末尾 last = last.next last.next = new_node # 把新人加到隊伍的末尾
3.3 在隊伍頭部插入新的人
如果你是VIP，你可以插隊到隊伍的最前面：
def insert_at_head(self, data):
new_node = Node(data) # 新人拿著票據
new_node.next = self.head # 新人指向原來的第一個人
self.head = new_node # 新人成為第一個人
3.4 刪除特定的人
假設有人決定不排隊了，我們需要把他從隊伍中移除：
def delete_node(self, key): temp = self.head if temp is not None: if temp.data == key: self.head = temp.next # 第一個人離開隊伍 temp = None return while temp is not None: if temp.data == key: # 找到想要離開隊伍的人 break prev = temp temp = temp.next if temp == None: return prev.next = temp.next # 把他從隊伍中移除 temp = None
3.5 打印隊伍中的所有人
為了查看隊伍中的所有人，我們從第一個人開始，依次看每個人的票據：
def print_list(self): temp = self.head while temp: print(temp.data, end=" -> ") # 打印每個人的票據 temp = temp.next print("None")
4. 鏈表的應用
鏈表在很多地方都有應用，比如：
- 實現棧和隊列：像超市排隊一樣，可以用鏈表實現先進先出的隊列和后進先出的棧。
- 內存管理：操作系統用鏈表來管理空閑內存塊，就像管理空閑的停車位。
- 圖的表示：用鏈表來存儲圖的鄰接表，每個節點都知道自己的鄰居。
5. 鏈表的優缺點
優點：
- 動態大小：隊伍可以根據需要動態調整長度。
- 高效插入/刪除：在隊伍中插入或刪除某個人非常高效。
缺點：
- 隨機訪問效率低：要找到某個人需要從第一個人開始一個個找下去。
- 額外內存開銷：每個人需要額外的空間來存儲指示牌（指針）。
浙公網安備 33010602011771號