本文目录
往期链接
| 01数组 |
|---|
02 链表 linked-list
S1 说明
链表是一种常见的数据结构，用于存储一系列元素。与数组不同，链表的元素（称为节点）在内存中不必是连续存储的。
基本特征
- 动态大小：链表的大小可以动态变化，不需要事先定义大小。
- 插入和删除效率：在链表中插入和删除节点的时间复杂度为 O(1)，这比数组更- 高效（数组在中间插入或删除元素时需要移动大量元素）。
- 顺序存储：元素通过指针相互连接，而不是通过索引。
节点：链表的基本单元
通常包含两个部分：
- 数据部分：存储实际的数据。
- 指针部分：指向下一个节点（在单向链表中）或前一个节点（在双向链表中）。
链表的分类
- 单向链表：每个节点只能指向下一个节点。
- 双向链表：每个节点既可以指向下一个节点，也可以指向前一个节点。
- 循环链表：最后一个节点指向第一个节点，形成一个环。
S2 示例
python中没有链表的数据结构，需要自己写函数定义。
单向链表
class Node:
"""链表节点类"""
def __init__(self, data):
self.data = data # 节点存储的数据
self.next = None # 指向下一个节点的指针
class LinkedList:
"""单向链表类"""
def __init__(self):
self.head = None # 链表头节点
def append(self, data):
"""在链表末尾添加新节点"""
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def insert_at_position(self, data, position):
"""在指定位置插入新节点"""
new_node = Node(data)
if position == 0:
new_node.next = self.head
self.head = new_node
return
current = self.head
for _ in range(position - 1):
if current is None:
raise IndexError("Position out of bounds")
current = current.next
new_node.next = current.next
current.next = new_node
def delete(self, key):
"""删除链表中指定值的节点"""
current = self.head
if current and current.data == key:
self.head = current.next
return
prev = None
while current and current.data != key:
prev = current
current = current.next
if current is None:
return # 未找到要删除的节点
prev.next = current.next
def find(self, key):
"""查找链表中是否存在指定值"""
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
def display(self):
"""遍历并打印链表中的所有节点"""
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# 使用示例
if __name__ == "__main__":
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
print("链表内容:")
ll.display()
ll.insert_at_position(4, 1) # 在位置 1 插入 4
print("插入 4 后的链表内容:")
ll.display()
ll.delete(2) # 删除值为 2 的节点
print("删除节点 2 后的链表内容:")
ll.display()
exists = ll.find(3) # 查找值为 3 的节点
print("查找值 3 存在:", exists)
输出
链表内容:
1 -> 2 -> 3 -> None
插入 4 后的链表内容:
1 -> 4 -> 2 -> 3 -> None
删除节点 2 后的链表内容:
1 -> 4 -> 3 -> None
查找值 3 存在: True
双向链表
class Node:
"""双向链表节点类"""
def __init__(self, data):
self.data = data # 节点存储的数据
self.prev = None # 指向前一个节点的指针
self.next = None # 指向下一个节点的指针
class DoublyLinkedList:
"""双向链表类"""
def __init__(self):
self.head = None # 链表头节点
def append(self, data):
"""在链表末尾添加新节点"""
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def insert_at_position(self, data, position):
"""在指定位置插入新节点"""
new_node = Node(data)
if position == 0:
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
return
current = self.head
for _ in range(position - 1):
if current is None:
raise IndexError("Position out of bounds")
current = current.next
new_node.next = current.next
new_node.prev = current
if current.next:
current.next.prev = new_node
current.next = new_node
def delete(self, key):
"""删除链表中指定值的节点"""
current = self.head
if current and current.data == key:
self.head = current.next
if self.head:
self.head.prev = None
return
while current and current.data != key:
current = current.next
if current is None:
return # 未找到要删除的节点
if current.next:
current.next.prev = current.prev
if current.prev:
current.prev.next = current.next
def find(self, key):
"""查找链表中是否存在指定值"""
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
def display(self):
"""遍历并打印链表中的所有节点"""
current = self.head
while current:
print(current.data, end=" <=> ")
current = current.next
print("None")
def reverse_display(self):
"""反向遍历并打印链表中的所有节点"""
current = self.head
while current and current.next:
current = current.next
while current:
print(current.data, end=" <=> ")
current = current.prev
print("None")
# 使用示例
if __name__ == "__main__":
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
print("链表内容:")
dll.display()
dll.insert_at_position(4, 1) # 在位置 1 插入 4
print("插入 4 后的链表内容:")
dll.display()
dll.delete(2) # 删除值为 2 的节点
print("删除节点 2 后的链表内容:")
dll.display()
exists = dll.find(3) # 查找值为 3 的节点
print("查找值 3 存在:", exists)
print("反向显示链表内容:")
dll.reverse_display()
输出
链表内容:
1 <=> 2 <=> 3 <=> None
插入 4 后的链表内容:
1 <=> 4 <=> 2 <=> 3 <=> None
删除节点 2 后的链表内容:
1 <=> 4 <=> 3 <=> None
查找值 3 存在: True
反向显示链表内容:
3 <=> 4 <=> 1 <=> None
循环链表
class Node:
"""循环链表节点类"""
def __init__(self, data):
self.data = data # 节点存储的数据
self.next = None # 指向下一个节点的指针
class CircularLinkedList:
"""循环链表类"""
def __init__(self):
self.head = None # 链表头节点
def append(self, data):
"""在链表末尾添加新节点"""
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head # 指向自己形成循环
return
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head # 新节点指向头节点
def insert_at_position(self, data, position):
"""在指定位置插入新节点"""
new_node = Node(data)
if position == 0: # 插入到头部
if not self.head:
self.head = new_node
new_node.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
self.head = new_node
return
current = self.head
for _ in range(position - 1):
current = current.next
if current == self.head:
raise IndexError("Position out of bounds")
new_node.next = current.next
current.next = new_node
def delete(self, key):
"""删除链表中指定值的节点"""
if not self.head:
return # 链表为空
current = self.head
if current.data == key: # 删除头节点
if current.next == self.head: # 只有一个节点的情况
self.head = None
return
else:
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
return
while current.next != self.head and current.next.data != key:
current = current.next
if current.next == self.head:
return # 未找到要删除的节点
current.next = current.next.next
def find(self, key):
"""查找链表中是否存在指定值"""
if not self.head:
return False
current = self.head
while True:
if current.data == key:
return True
current = current.next
if current == self.head:
break
return False
def display(self):
"""遍历并打印链表中的所有节点"""
if not self.head:
print("链表为空")
return
current = self.head
print("链表内容:")
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("头节点:", self.head.data) # 显示头节点的值
# 使用示例
if __name__ == "__main__":
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.display()
cll.insert_at_position(4, 1) # 在位置 1 插入 4
print("插入 4 后的链表内容:")
cll.display()
cll.delete(2) # 删除值为 2 的节点
print("删除节点 2 后的链表内容:")
cll.display()
exists = cll.find(3) # 查找值为 3 的节点
print("查找值 3 存在:", exists)
输出
链表内容:
1 -> 2 -> 3 -> 头节点: 1
插入 4 后的链表内容:
链表内容:
1 -> 4 -> 2 -> 3 -> 头节点: 1
删除节点 2 后的链表内容:
链表内容:
1 -> 4 -> 3 -> 头节点: 1
查找值 3 存在: True
S3 问题：反转单向链表
求解思路
- 初始化指针：使用三个指针：prev（前一个节点）、current（当前节点）、next_node（下一个节点）。
- 遍历链表：在遍历的过程中，逐步改变当前节点的next指针，使其指向前一个节点。
- 更新头节点：当遍历完成后，prev指针将指向新的头节点。
Python3程序
class Node:
"""链表节点类"""
def __init__(self, data):
self.data = data # 节点存储的数据
self.next = None # 指向下一个节点的指针
class LinkedList:
"""单向链表类"""
def __init__(self):
self.head = None # 链表头节点
def append(self, data):
"""在链表末尾添加新节点"""
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def reverse(self):
"""反转链表"""
prev = None
current = self.head
while current:
next_node = current.next # 保存下一个节点
current.next = prev # 反转指针
prev = current # 移动 prev 和 current 向前
current = next_node
self.head = prev # 更新头节点
def display(self):
"""遍历并打印链表中的所有节点"""
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# 使用示例
if __name__ == "__main__":
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
print("原链表内容:")
ll.display()
ll.reverse()
print("反转后的链表内容:")
ll.display()
输出
原链表内容:
1 -> 2 -> 3 -> 4 -> None
反转后的链表内容:
4 -> 3 -> 2 -> 1 -> None
S4 问题： 双向链表实现历史浏览网页
求解思路
定义管理浏览历史的类，包含头节点(打开的第一个网页)、尾节点(None)和当前节点(当前网页)。
- visit(url)：访问新网页，添加到链表中。
- back()：返回到上一个网页，更新当前节点。
- forward()：前进到下一个网页，更新当前节点。
Python3程序
class Node:
"""双向链表节点类"""
def __init__(self, url):
self.url = url # 存储浏览的 URL
self.prev = None # 指向前一个节点的指针
self.next = None # 指向下一个节点的指针
class BrowsingHistory:
"""浏览历史管理类"""
def __init__(self):
self.head = None # 链表头节点
self.tail = None # 链表尾节点
self.current = None # 当前浏览的节点
def visit(self, url):
"""访问新网页"""
new_node = Node(url)
if not self.head: # 如果链表为空
self.head = new_node
self.tail = new_node
self.current = new_node
else:
# 将当前节点的下一个节点指向新节点
self.current.next = new_node
new_node.prev = self.current
self.current = new_node # 更新当前节点为新节点
self.tail = new_node # 更新尾节点
def back(self):
"""后退到上一个网页"""
if self.current and self.current.prev:
self.current = self.current.prev
return self.current.url
return None # 无法后退
def forward(self):
"""前进到下一个网页"""
if self.current and self.current.next:
self.current = self.current.next
return self.current.url
return None # 无法前进
def display_history(self):
"""显示浏览历史"""
current = self.head
while current:
print(current.url, end=" <-> ")
current = current.next
print("None")
# 使用示例
if __name__ == "__main__":
history = BrowsingHistory()
history.visit("https://www.baidu.com")
history.visit("https://www.huawei.com")
history.visit("https://www.apple.com")
print("浏览历史:")
history.display_history()
print("后退到:", history.back()) # 返回到上一个网页
print("后退到:", history.back()) # 再返回到上一个网页
print("前进到:", history.forward()) # 前进到下一个网页
print("当前网页:", history.current.url) # 当前网页
输出
浏览历史:
https://www.baidu.com <-> https://www.huawei.com <-> https://www.apple.com <-> None
后退到: https://www.huawei.com
后退到: https://www.baidu.com
前进到: https://www.huawei.com
当前网页: https://www.huawei.com
S5 问题： 基于循环链表的玩家出牌顺序
求解思路
- Node 类：表示循环链表中的每个节点，包含玩家名字和指向下一个节点的指针。
- CircularLinkedList 类：管理循环链表的玩家顺序。
- add_player(player_name)：添加新玩家到循环链表。
- display_players()：遍历并打印当前所有玩家的名字，并标记头节点。
Python3程序
class Node:
"""循环链表节点类"""
def __init__(self, player_name):
self.player_name = player_name # 存储玩家名字
self.next = None # 指向下一个节点的指针
class CircularLinkedList:
"""循环链表类"""
def __init__(self):
self.head = None # 链表头节点
def add_player(self, player_name):
"""添加新玩家到循环链表"""
new_node = Node(player_name)
if not self.head: # 如果链表为空
self.head = new_node
new_node.next = self.head # 指向自己形成循环
else:
current = self.head
while current.next != self.head: # 找到最后一个节点
current = current.next
current.next = new_node # 将最后一个节点指向新节点
new_node.next = self.head # 新节点指向头节点
def display_players(self):
"""显示当前所有玩家，包括头节点"""
if not self.head:
print("没有玩家在游戏中")
return
current = self.head
players = []
while True:
if current == self.head:
players.append(f"{current.player_name} (头节点)") # 标记头节点
else:
players.append(current.player_name)
current = current.next
if current == self.head: # 如果回到头节点
break
print("当前玩家:", " -> ".join(players) + " -> (回到头节点)")
# 使用示例
if __name__ == "__main__":
game = CircularLinkedList()
game.add_player("Alice")
game.add_player("Bob")
game.add_player("Charlie")
print("当前玩家顺序:")
game.display_players()
# 添加更多玩家
game.add_player("David")
print("添加 David 后的玩家顺序:")
game.display_players()
输出
当前玩家顺序:
当前玩家: Alice (头节点) -> Bob -> Charlie -> (回到头节点)
添加 David 后的玩家顺序:
当前玩家: Alice (头节点) -> Bob -> Charlie -> David -> (回到头节点)