当前位置：首页 > news >正文

python数据结构之链表

news 2026/5/11 22:33:06

python中的数据结构，通过类来实现。

一、链表基础概念

概念

链表是一种线性数据结构，但它不像列表（数组）那样在内存中连续存储，而是通过节点（Node）串联而成的。

节点是链表的基本单元，其中包含两部分。data：存储的数据；next/prev：指针（引用），指向链表中的下一个 / 上一个节点。

链表的优缺点

链表的优点：插入 / 删除元素时无需移动其他元素（只需修改指针），效率高。

链表的缺点：访问元素需要从头遍历（无法像列表那样随机访问），查询效率低。

二、单链表（SingleLinkList）

概念

单链表是最简单的链表结构，每个节点只有一个指针（next），指向下一个节点，最后一个节点的 next 为 None，链表有一个头节点（head）作为入口。

代码实现

（核心功能：初始化、添加节点、遍历、删除节点）。

# 通过定义类来实现链表和链表的节点 class Node: # 单链表的节点类 def __init__(self, data): self.data = data # 节点存储的数据 self.next = None # 指向下一个节点的指针，初始为None class LinkList: # 单链表类 def __init__(self): self.head = None # 头节点，初始为空 # 尾插节点 def add(self, data): # 在链表尾部添加节点 # 插入操作，先判断链表是否为空再决定插入 node = Node(data) # 如果链表为空，头节点直接指向新节点 if self.head is None: self.head = node return # 链表不为空，则遍历到最后一个节点 current = self.head while current.next: current = current.next current.next = node def travel(self): # 遍历链表并打印所有节点数据 current = self.head while current: print(current.data) current = current.next def delete(self, key): # 删除指定值的节点 # 因为头节点和别的节点结构有差异，所以需要单独判断 current = self.head # 情况1：删除头节点 # 头节点不为空且为要删除的点 if current and current.data == key: self.head = current.next #设置下一个节点为头节点 current = None return # 情况2：删除中间/尾部节点 prev = None # 需要定义一个前缀节点方便删除 # 循环的意思是，未遇见要删除的节点时，前缀节点和当前节点都往后走 while current and current.data != key: prev = current current = current.next # 如果没找到要删除的节点 if current is None: return # 断开指针，删除节点 prev.next = current.next current = None # 测试单链表 if __name__ == "__main__": linkList = LinkList() linkList.add(10) linkList.(20) print("初始链表：") linkList.travel() # 输出：10 20 30 linkList.delete(20) # 删除值为20的节点 linkList.travel() # 输出：10 -> 30

三、双链表（DoubleLinkList）

概念

双链表的每个节点有两个指针，next：指向下一个节点，prev：指向上一个节点。

头节点的 prev 为 None，尾节点的 next 为 None。

优缺点

优点：可以双向遍历，删除节点时无需像单链表那样找前驱节点（效率更高）；

缺点：节点结构更复杂，占用更多内存。

代码实现

（核心功能：头部添加、尾部添加、双向遍历、删除节点）。

# 定义双链表节点类 class DoubleNode: # 双链表节点类 def __init__(self, data): self.data = data self.next = None # 指向下一个节点 self.prev = None # 指向上一个节点 class DoubleLinkList: # 双链表类 def __init__(self): self.head = None self.tail = None # 设置尾节点，方便尾部操作 def add_head(self, data): # 在头部添加节点(头插)，每次插入需要将插入的节点作为头节点 node = DoubleNode(data) if self.head is None: # 链表为空时 self.head = node # 头尾节点都为这个节点 self.tail = node else: # 链表不为空时 node.next = self.head self.head.prev = node self.head = node def add_tail(self, data): # 在尾部添加节点（设置了尾节点，可以利用tail，无需遍历） # 每次尾插，需要将插入的节点设置为尾节点 node = DoubleNode(data) if self.tail is None: # 链表为空 self.head = node self.tail = node else: node.prev = self.tail self.tail.next = node self.tail = node def travel(self): #从头节点到尾节点遍历 current = self.head while current: print(current.data) current = current.next def delete(self, key): # 删除指定值的节点 current = self.head # 找到目标节点 while current and current.data != key: current = current.next if current is None: # 没找到 return # 情况1：删除头节点 if current == self.head: self.head = current.next if self.head: # 如果链表还有节点 self.head.prev = None else: # 链表只剩一个节点 self.tail = None # 情况2：删除尾节点 elif current == self.tail: self.tail = current.prev self.tail.next = None # 情况3：删除中间节点 else: current.prev.next = current.next current.next.prev = current.prev current = None # 测试双链表 if __name__ == "__main__": dll = DoubleLinkList() dll.add_head(20) dll.add_head(10) dll.add_tail(30) dll.travel() # 输出：正向遍历：10 20 30 dll.delete_node(20) # 删除值为20的节点 dll.traverse_forward() # 输出：10 30

四、循环链表（Circular Linked List）

概念

循环链表是单链表 / 双链表的变体，最后一个节点的 next 指针不指向 None，而是指向头节点（双循环链表的头节点 prev 指向尾节点）。可以理解为首尾相接的火车。

特点：没有 “末尾” 的概念，遍历可以从任意节点开始，直到回到起点；常用于需要循环处理的场景（如约瑟夫环问题）。

代码实现

（单循环链表，核心功能：添加节点、遍历、判断是否循环）。

class CircularNode: # 循环链表节点类（基于单链表设计的循环单链表） def __init__(self, data): self.data = data self.next = None class CircularLinkedList: # 循环单链表类 def __init__(self): self.head = None def add_end(self, data): # 在尾部添加节点（尾节点next指向头节点） node = CircularNode(data) if self.head is None: self.head = node node.next = self.head # 第一个节点指向自己，形成循环 else: current = self.head # 遍历到最后一个节点（next指向head的节点） while current.next != self.head: current = current.next current.next = node node.next = self.head # 新节点next指向头节点 def travel(self): # 遍历循环链表(从head开始，回到head结束) if self.head is None: # 先判空 print("链表为空") return current = self.head while True: print(current.data) current = current.next if current == self.head: # 回到头节点，结束遍历 print(f"(回到{self.head.data})") break def is_circular(self): """判断是否为循环链表（验证核心特征）""" if self.head is None: return False current = self.head.next while current and current != self.head: current = current.next return current == self.head # 测试循环链表 if __name__ == "__main__": cll = CircularLinkedList() cll.add_end(10) cll.add_end(20) cll.add_end(30) cll.traverse() # 输出：循环链表遍历：10 20 30 (回到10) print("是否为循环链表：", cll.is_circular()) # 输出：True