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