数据结构编程实践20讲(Python版)—02链表

往期链接

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_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_nodedef insert_at_position(self, data, position):"""在指定位置插入新节点"""new_node = Node(data)if position == 0:new_node.next = self.headself.head = new_nodereturncurrent = self.headfor _ in range(position - 1):if current is None:raise IndexError("Position out of bounds")current = current.nextnew_node.next = current.nextcurrent.next = new_nodedef delete(self, key):"""删除链表中指定值的节点"""current = self.headif current and current.data == key:self.head = current.nextreturnprev = Nonewhile current and current.data != key:prev = currentcurrent = current.nextif current is None:return  # 未找到要删除的节点prev.next = current.nextdef find(self, key):"""查找链表中是否存在指定值"""current = self.headwhile current:if current.data == key:return Truecurrent = current.nextreturn Falsedef display(self):"""遍历并打印链表中的所有节点"""current = self.headwhile current:print(current.data, end=" -> ")current = current.nextprint("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 插入 4print("插入 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_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_nodenew_node.prev = currentdef insert_at_position(self, data, position):"""在指定位置插入新节点"""new_node = Node(data)if position == 0:new_node.next = self.headif self.head:self.head.prev = new_nodeself.head = new_nodereturncurrent = self.headfor _ in range(position - 1):if current is None:raise IndexError("Position out of bounds")current = current.nextnew_node.next = current.nextnew_node.prev = currentif current.next:current.next.prev = new_nodecurrent.next = new_nodedef delete(self, key):"""删除链表中指定值的节点"""current = self.headif current and current.data == key:self.head = current.nextif self.head:self.head.prev = Nonereturnwhile current and current.data != key:current = current.nextif current is None:return  # 未找到要删除的节点if current.next:current.next.prev = current.previf current.prev:current.prev.next = current.nextdef find(self, key):"""查找链表中是否存在指定值"""current = self.headwhile current:if current.data == key:return Truecurrent = current.nextreturn Falsedef display(self):"""遍历并打印链表中的所有节点"""current = self.headwhile current:print(current.data, end=" <=> ")current = current.nextprint("None")def reverse_display(self):"""反向遍历并打印链表中的所有节点"""current = self.headwhile current and current.next:current = current.nextwhile current:print(current.data, end=" <=> ")current = current.prevprint("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 插入 4print("插入 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_nodenew_node.next = self.head  # 指向自己形成循环returncurrent = self.headwhile current.next != self.head:current = current.nextcurrent.next = new_nodenew_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_nodenew_node.next = self.headelse:current = self.headwhile current.next != self.head:current = current.nextcurrent.next = new_nodenew_node.next = self.headself.head = new_nodereturncurrent = self.headfor _ in range(position - 1):current = current.nextif current == self.head:raise IndexError("Position out of bounds")new_node.next = current.nextcurrent.next = new_nodedef delete(self, key):"""删除链表中指定值的节点"""if not self.head:return  # 链表为空current = self.headif current.data == key:  # 删除头节点if current.next == self.head:  # 只有一个节点的情况self.head = Nonereturnelse:while current.next != self.head:current = current.nextcurrent.next = self.head.nextself.head = self.head.nextreturnwhile current.next != self.head and current.next.data != key:current = current.nextif current.next == self.head:return  # 未找到要删除的节点current.next = current.next.nextdef find(self, key):"""查找链表中是否存在指定值"""if not self.head:return Falsecurrent = self.headwhile True:if current.data == key:return Truecurrent = current.nextif current == self.head:breakreturn Falsedef display(self):"""遍历并打印链表中的所有节点"""if not self.head:print("链表为空")returncurrent = self.headprint("链表内容:")while True:print(current.data, end=" -> ")current = current.nextif current == self.head:breakprint("头节点:", 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 插入 4print("插入 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_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_nodedef reverse(self):"""反转链表"""prev = Nonecurrent = self.headwhile current:next_node = current.next  # 保存下一个节点current.next = prev       # 反转指针prev = current            # 移动 prev 和 current 向前current = next_nodeself.head = prev  # 更新头节点def display(self):"""遍历并打印链表中的所有节点"""current = self.headwhile current:print(current.data, end=" -> ")current = current.nextprint("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  # 存储浏览的 URLself.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_nodeself.tail = new_nodeself.current = new_nodeelse:# 将当前节点的下一个节点指向新节点self.current.next = new_nodenew_node.prev = self.currentself.current = new_node  # 更新当前节点为新节点self.tail = new_node  # 更新尾节点def back(self):"""后退到上一个网页"""if self.current and self.current.prev:self.current = self.current.prevreturn self.current.urlreturn None  # 无法后退def forward(self):"""前进到下一个网页"""if self.current and self.current.next:self.current = self.current.nextreturn self.current.urlreturn None  # 无法前进def display_history(self):"""显示浏览历史"""current = self.headwhile current:print(current.url, end=" <-> ")current = current.nextprint("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_nodenew_node.next = self.head  # 指向自己形成循环else:current = self.headwhile current.next != self.head:  # 找到最后一个节点current = current.nextcurrent.next = new_node  # 将最后一个节点指向新节点new_node.next = self.head  # 新节点指向头节点def display_players(self):"""显示当前所有玩家，包括头节点"""if not self.head:print("没有玩家在游戏中")returncurrent = self.headplayers = []while True:if current == self.head:players.append(f"{current.player_name} (头节点)")  # 标记头节点else:players.append(current.player_name)current = current.nextif current == self.head:  # 如果回到头节点breakprint("当前玩家:", " -> ".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 -> (回到头节点)