算法系列之链表基本原理---超市购物队列的故事
想了个生动的方式来解释链表基本原理
想象你在一个超市排队结账，每个人都是一个节点，每个人手里拿着一张票据（数据），而每个人的背上都贴着一个指示牌，指示牌指向下一个排队的人。这就是一个单向链表。
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. 链表的优缺点
优点：
- 动态大小：队伍可以根据需要动态调整长度。
- 高效插入/删除：在队伍中插入或删除某个人非常高效。
缺点：
- 随机访问效率低：要找到某个人需要从第一个人开始一个个找下去。
- 额外内存开销：每个人需要额外的空间来存储指示牌（指针）。