前言单链表是最基础的数据结构之一它由一系列节点组成每个节点包含数据域和指针域。相比数组链表在插入和删除操作上具有优势但随机访问能力较弱。本文将从零开始用Python完整实现单链表并详细讲解每个函数的设计思路。整体设计我们采用面向对象的设计方式将链表分为两个类Node节点类存储数据和指向下一个节点的指针LinkList链表类管理节点的增删改查操作我们使用带头节点的单链表即有一个哨兵节点作为链表的头部这样统一了空链表和非空链表的操作逻辑。节点类设计class Node: 单链表节点类 def __init__(self, data0, nextNone): self.__data data # 私有数据域 self.__next next # 私有指针域 property def data(self): 获取节点数据 return self.__data data.setter def data(self, value): 设置节点数据 self.__data value property def next(self): 获取下一个节点 return self.__next next.setter def next(self, value): 设置下一个节点 self.__next value设计思路使用property装饰器实现属性访问控制保证数据封装性私有属性__data和__next防止外部直接修改提供getter和setter方法便于后续扩展链表类基础功能1. 初始化class LinkList: def __init__(self): 初始化空链表创建哨兵节点 self.__head Node() # 头指针指向哨兵节点 self.__tail self.__head # 尾指针指向哨兵节点思路解析创建一个哨兵节点值为0简化边界处理同时维护头指针和尾指针提高尾插效率尾指针初始指向头节点表示空链表2. 判空操作def is_empty(self): 判断链表是否为空 return self.__head.next is None思路解析空链表判断标准头节点的next指向None时间复杂度O(1)3. 获取链表长度def __len__(self): 获取链表长度支持len()函数 count 0 p self.__head.next while p is not None: count 1 p p.next return count思路解析实现__len__魔法方法支持len(linklist)调用遍历所有节点进行计数时间复杂度O(n)插入操作4. 头插法def push_front(self, value): 在链表头部插入新节点 new_node Node(value, self.__head.next) self.__head.next new_node # 如果插入前链表为空更新尾指针 if self.__tail is self.__head: self.__tail new_node思路解析创建新节点将其next指向原来的第一个节点头节点的next指向新节点特殊处理如果链表为空新节点既是头也是尾5. 尾插法def push_back(self, value): 在链表尾部插入新节点 new_node Node(value) self.__tail.next new_node self.__tail new_node思路解析利用尾指针直接找到尾部O(1)时间复杂度创建新节点尾节点的next指向新节点更新尾指针指向新节点6. 指定位置插入def insert(self, pos, value): 在指定位置插入新节点 length len(self) # 参数合法性检查 if pos 0 or pos length: raise IndexError(f插入位置 {pos} 无效链表长度为 {length}) # 复用已有方法 if pos 0: self.push_front(value) return if pos length: self.push_back(value) return # 找到前驱节点 p self.__head for _ in range(pos): p p.next # 插入新节点 new_node Node(value, p.next) p.next new_node思路解析验证插入位置的合法性0 ≤ pos ≤ length利用push_front和push_back处理边界情况遍历找到第pos个节点的前驱修改指针完成插入删除操作7. 头删法def pop_front(self): 删除头部节点并返回其值 if self.is_empty(): print(链表为空) return None node_to_delete self.__head.next value node_to_delete.data # 如果只剩一个节点尾指针指向哨兵 if self.__tail is node_to_delete: self.__tail self.__head self.__head.next node_to_delete.next return value思路解析检查链表是否为空记录要删除的节点特殊处理删除最后一个节点时更新尾指针头节点跳过要删除的节点8. 尾删法def pop_back(self): 删除尾部节点并返回其值 if self.is_empty(): print(链表为空) return None value self.__tail.data # 如果只剩一个节点 if self.__head.next is self.__tail: self.__head.next None self.__tail self.__head else: # 找到倒数第二个节点 p self.__head while p.next is not self.__tail: p p.next p.next None self.__tail p return value思路解析检查链表是否为空保存尾节点数据特殊处理只剩一个节点时直接置空遍历找到倒数第二个节点时间复杂度O(n)更新尾指针9. 按值删除def delete_by_value(self, value): 删除所有值为value的节点返回删除个数 if self.is_empty(): return 0 count 0 p self.__head while p.next is not None: if p.next.data value: # 如果要删除的是尾节点更新尾指针 if p.next is self.__tail: self.__tail p p.next p.next.next count 1 else: p p.next return count思路解析使用前驱节点判断方便删除删除所有匹配的节点不只是第一个删除尾节点时更新尾指针返回删除节点个数查找与访问10. 按值查找def search(self, value): 查找值为value的节点位置返回第一个匹配的位置 pos 0 p self.__head.next while p is not None: if p.data value: return pos p p.next pos 1 return -1思路解析从第一个有效节点开始遍历匹配成功返回当前位置遍历结束返回-1表示未找到11. 索引访问支持负数索引def __getitem__(self, index): 支持通过下标访问节点值 length len(self) # 处理负数索引 if index 0: index length index if index 0 or index length: raise IndexError(f链表索引 {index} 越界长度为 {length}) p self.__head.next for _ in range(index): p p.next return p.data思路解析实现__getitem__魔法方法支持linklist[0]语法支持负数索引从末尾倒数进行边界检查12. 索引赋值def __setitem__(self, index, value): 支持通过下标修改节点值 length len(self) if index 0: index length index if index 0 or index length: raise IndexError(f链表索引 {index} 越界长度为 {length}) p self.__head.next for _ in range(index): p p.next p.data value思路解析实现__setitem__魔法方法支持linklist[0] value语法查找并修改指定位置的数据显示与调试13. 显示链表def show(self): 以可视化方式显示链表 if self.is_empty(): print(链表为空) return elements [] p self.__head.next while p is not None: elements.append(str(p.data)) p p.next print( - .join(elements))思路解析遍历所有节点收集数据到列表用箭头连接显示例如1 - 2 - 3 - 4完整测试if __name__ __main__: # 创建链表 ll LinkList() # 测试头插 print( 头插测试 ) ll.push_front(1) ll.push_front(2) ll.push_front(3) ll.show() # 3 - 2 - 1 # 测试尾插 print(\n 尾插测试 ) ll.push_back(4) ll.push_back(5) ll.show() # 3 - 2 - 1 - 4 - 5 # 测试长度 print(f\n链表长度: {len(ll)}) # 5 # 测试索引访问 print(\n 索引访问 ) print(fll[0] {ll[0]}) print(fll[-1] {ll[-1]}) # 测试索引赋值 print(\n 索引赋值 ) ll[1] 99 ll.show() # 3 - 99 - 1 - 4 - 5 # 测试插入 print(\n 指定位置插入 ) ll.insert(2, 88) ll.show() # 3 - 99 - 88 - 1 - 4 - 5 # 测试按值删除 print(\n 按值删除 ) ll.delete_by_value(88) ll.show() # 3 - 99 - 1 - 4 - 5 # 测试搜索 print(\n 搜索 ) print(f查找99的位置: {ll.search(99)}) print(f查找100的位置: {ll.search(100)}) # 测试头删 print(\n 头删 ) print(f删除: {ll.pop_front()}) # 3 ll.show() # 99 - 1 - 4 - 5 # 测试尾删 print(\n 尾删 ) print(f删除: {ll.pop_back()}) # 5 ll.show() # 99 - 1 - 4时间复杂度总结操作时间复杂度说明头插O(1)直接在头部插入尾插O(1)利用尾指针头删O(1)直接在头部删除尾删O(n)需要遍历到倒数第二个节点指定位置插入O(n)需要遍历到指定位置按值删除O(n)需要遍历查找按值查找O(n)需要遍历查找索引访问O(n)需要遍历到指定位置核心要点总结哨兵节点的妙用带头节点的链表简化了边界处理无需特殊判断空链表情况双指针维护同时维护头指针和尾指针让尾插操作达到O(1)复杂度Python魔法方法通过实现__len__、__getitem__、__setitem__让链表使用体验接近Python内置列表封装性使用私有属性配合property装饰器既保护了数据又提供了友好的访问接口异常处理在索引越界时抛出标准异常符合Python编程习惯学习建议画图理解链表操作的核心是指针操作建议在纸上画图模拟每个步骤调试技巧善用show()方法可视化链表状态快速发现bug扩展练习实现链表反转检测链表中是否有环找到链表的中间节点实现双向链表性能思考理解每种操作的时间复杂度在合适的场景选择合适的数据结构结语通过完整的代码实现和详细的思路解析我们构建了一个功能完善的单链表。这个实现不仅包含了基础的增删改查还通过Python魔法方法提供了类似内置列表的使用体验。希望这篇博文能帮助你深入理解单链表的原理和实现为后续学习更复杂的数据结构打下坚实基础 
长河君 · 2026/8/14 13:48:12 · 阅读 1.2k Python实现数据结构单链表
前言单链表是最基础的数据结构之一它由一系列节点组成每个节点包含数据域和指针域。相比数组链表在插入和删除操作上具有优势但随机访问能力较弱。本文将从零开始用Python完整实现单链表并详细讲解每个函数的设计思路。整体设计我们采用面向对象的设计方式将链表分为两个类Node节点类存储数据和指向下一个节点的指针LinkList链表类管理节点的增删改查操作我们使用带头节点的单链表即有一个哨兵节点作为链表的头部这样统一了空链表和非空链表的操作逻辑。节点类设计class Node: 单链表节点类 def __init__(self, data0, nextNone): self.__data data # 私有数据域 self.__next next # 私有指针域 property def data(self): 获取节点数据 return self.__data data.setter def data(self, value): 设置节点数据 self.__data value property def next(self): 获取下一个节点 return self.__next next.setter def next(self, value): 设置下一个节点 self.__next value设计思路使用property装饰器实现属性访问控制保证数据封装性私有属性__data和__next防止外部直接修改提供getter和setter方法便于后续扩展链表类基础功能1. 初始化class LinkList: def __init__(self): 初始化空链表创建哨兵节点 self.__head Node() # 头指针指向哨兵节点 self.__tail self.__head # 尾指针指向哨兵节点思路解析创建一个哨兵节点值为0简化边界处理同时维护头指针和尾指针提高尾插效率尾指针初始指向头节点表示空链表2. 判空操作def is_empty(self): 判断链表是否为空 return self.__head.next is None思路解析空链表判断标准头节点的next指向None时间复杂度O(1)3. 获取链表长度def __len__(self): 获取链表长度支持len()函数 count 0 p self.__head.next while p is not None: count 1 p p.next return count思路解析实现__len__魔法方法支持len(linklist)调用遍历所有节点进行计数时间复杂度O(n)插入操作4. 头插法def push_front(self, value): 在链表头部插入新节点 new_node Node(value, self.__head.next) self.__head.next new_node # 如果插入前链表为空更新尾指针 if self.__tail is self.__head: self.__tail new_node思路解析创建新节点将其next指向原来的第一个节点头节点的next指向新节点特殊处理如果链表为空新节点既是头也是尾5. 尾插法def push_back(self, value): 在链表尾部插入新节点 new_node Node(value) self.__tail.next new_node self.__tail new_node思路解析利用尾指针直接找到尾部O(1)时间复杂度创建新节点尾节点的next指向新节点更新尾指针指向新节点6. 指定位置插入def insert(self, pos, value): 在指定位置插入新节点 length len(self) # 参数合法性检查 if pos 0 or pos length: raise IndexError(f插入位置 {pos} 无效链表长度为 {length}) # 复用已有方法 if pos 0: self.push_front(value) return if pos length: self.push_back(value) return # 找到前驱节点 p self.__head for _ in range(pos): p p.next # 插入新节点 new_node Node(value, p.next) p.next new_node思路解析验证插入位置的合法性0 ≤ pos ≤ length利用push_front和push_back处理边界情况遍历找到第pos个节点的前驱修改指针完成插入删除操作7. 头删法def pop_front(self): 删除头部节点并返回其值 if self.is_empty(): print(链表为空) return None node_to_delete self.__head.next value node_to_delete.data # 如果只剩一个节点尾指针指向哨兵 if self.__tail is node_to_delete: self.__tail self.__head self.__head.next node_to_delete.next return value思路解析检查链表是否为空记录要删除的节点特殊处理删除最后一个节点时更新尾指针头节点跳过要删除的节点8. 尾删法def pop_back(self): 删除尾部节点并返回其值 if self.is_empty(): print(链表为空) return None value self.__tail.data # 如果只剩一个节点 if self.__head.next is self.__tail: self.__head.next None self.__tail self.__head else: # 找到倒数第二个节点 p self.__head while p.next is not self.__tail: p p.next p.next None self.__tail p return value思路解析检查链表是否为空保存尾节点数据特殊处理只剩一个节点时直接置空遍历找到倒数第二个节点时间复杂度O(n)更新尾指针9. 按值删除def delete_by_value(self, value): 删除所有值为value的节点返回删除个数 if self.is_empty(): return 0 count 0 p self.__head while p.next is not None: if p.next.data value: # 如果要删除的是尾节点更新尾指针 if p.next is self.__tail: self.__tail p p.next p.next.next count 1 else: p p.next return count思路解析使用前驱节点判断方便删除删除所有匹配的节点不只是第一个删除尾节点时更新尾指针返回删除节点个数查找与访问10. 按值查找def search(self, value): 查找值为value的节点位置返回第一个匹配的位置 pos 0 p self.__head.next while p is not None: if p.data value: return pos p p.next pos 1 return -1思路解析从第一个有效节点开始遍历匹配成功返回当前位置遍历结束返回-1表示未找到11. 索引访问支持负数索引def __getitem__(self, index): 支持通过下标访问节点值 length len(self) # 处理负数索引 if index 0: index length index if index 0 or index length: raise IndexError(f链表索引 {index} 越界长度为 {length}) p self.__head.next for _ in range(index): p p.next return p.data思路解析实现__getitem__魔法方法支持linklist[0]语法支持负数索引从末尾倒数进行边界检查12. 索引赋值def __setitem__(self, index, value): 支持通过下标修改节点值 length len(self) if index 0: index length index if index 0 or index length: raise IndexError(f链表索引 {index} 越界长度为 {length}) p self.__head.next for _ in range(index): p p.next p.data value思路解析实现__setitem__魔法方法支持linklist[0] value语法查找并修改指定位置的数据显示与调试13. 显示链表def show(self): 以可视化方式显示链表 if self.is_empty(): print(链表为空) return elements [] p self.__head.next while p is not None: elements.append(str(p.data)) p p.next print( - .join(elements))思路解析遍历所有节点收集数据到列表用箭头连接显示例如1 - 2 - 3 - 4完整测试if __name__ __main__: # 创建链表 ll LinkList() # 测试头插 print( 头插测试 ) ll.push_front(1) ll.push_front(2) ll.push_front(3) ll.show() # 3 - 2 - 1 # 测试尾插 print(\n 尾插测试 ) ll.push_back(4) ll.push_back(5) ll.show() # 3 - 2 - 1 - 4 - 5 # 测试长度 print(f\n链表长度: {len(ll)}) # 5 # 测试索引访问 print(\n 索引访问 ) print(fll[0] {ll[0]}) print(fll[-1] {ll[-1]}) # 测试索引赋值 print(\n 索引赋值 ) ll[1] 99 ll.show() # 3 - 99 - 1 - 4 - 5 # 测试插入 print(\n 指定位置插入 ) ll.insert(2, 88) ll.show() # 3 - 99 - 88 - 1 - 4 - 5 # 测试按值删除 print(\n 按值删除 ) ll.delete_by_value(88) ll.show() # 3 - 99 - 1 - 4 - 5 # 测试搜索 print(\n 搜索 ) print(f查找99的位置: {ll.search(99)}) print(f查找100的位置: {ll.search(100)}) # 测试头删 print(\n 头删 ) print(f删除: {ll.pop_front()}) # 3 ll.show() # 99 - 1 - 4 - 5 # 测试尾删 print(\n 尾删 ) print(f删除: {ll.pop_back()}) # 5 ll.show() # 99 - 1 - 4时间复杂度总结操作时间复杂度说明头插O(1)直接在头部插入尾插O(1)利用尾指针头删O(1)直接在头部删除尾删O(n)需要遍历到倒数第二个节点指定位置插入O(n)需要遍历到指定位置按值删除O(n)需要遍历查找按值查找O(n)需要遍历查找索引访问O(n)需要遍历到指定位置核心要点总结哨兵节点的妙用带头节点的链表简化了边界处理无需特殊判断空链表情况双指针维护同时维护头指针和尾指针让尾插操作达到O(1)复杂度Python魔法方法通过实现__len__、__getitem__、__setitem__让链表使用体验接近Python内置列表封装性使用私有属性配合property装饰器既保护了数据又提供了友好的访问接口异常处理在索引越界时抛出标准异常符合Python编程习惯学习建议画图理解链表操作的核心是指针操作建议在纸上画图模拟每个步骤调试技巧善用show()方法可视化链表状态快速发现bug扩展练习实现链表反转检测链表中是否有环找到链表的中间节点实现双向链表性能思考理解每种操作的时间复杂度在合适的场景选择合适的数据结构结语通过完整的代码实现和详细的思路解析我们构建了一个功能完善的单链表。这个实现不仅包含了基础的增删改查还通过Python魔法方法提供了类似内置列表的使用体验。希望这篇博文能帮助你深入理解单链表的原理和实现为后续学习更复杂的数据结构打下坚实基础