Python链表实现与操作

【Python链表实现与操作】# 链表是一种常见的基础数据结构由一系列节点组成每个节点包含数据和指向下一个节点的指针。# Python 标准列表底层是动态数组而链表在插入和删除操作上具有优势。# 单向链表 class Node:链表节点类def __init__(self, data):self.data data # 节点存储的数据self.next None # 指向下一个节点的指针class SinglyLinkedList:单向链表实现def __init__(self):self.head None # 头节点初始化为空self._size 0 # 链表长度def append(self, data):在链表尾部追加节点new_node Node(data)if not self.head: # 链表为空时直接设为头节点self.head new_nodeelse:current self.headwhile current.next: # 遍历到最后一个节点current current.nextcurrent.next new_nodeself._size 1def insert(self, index, data):在指定位置插入节点索引从0开始if index 0 or index self._size:raise IndexError(索引超出范围)new_node Node(data)if index 0: # 在头部插入new_node.next self.headself.head new_nodeelse:current self.headfor _ in range(index - 1):current current.nextnew_node.next current.nextcurrent.next new_nodeself._size 1def delete(self, data):删除第一个值为data的节点if not self.head:return Falseif self.head.data data: # 头节点就是要删除的self.head self.head.nextself._size - 1return Truecurrent self.headwhile current.next:if current.next.data data:current.next current.next.nextself._size - 1return Truecurrent current.nextreturn False # 未找到该值def search(self, data):搜索值返回是否存在current self.headwhile current:if current.data data:return Truecurrent current.nextreturn Falsedef __len__(self):return self._sizedef __iter__(self):使链表可迭代方便遍历current self.headwhile current:yield current.datacurrent current.next# 双向链表 class DoublyNode:双向链表节点def __init__(self, data):self.data dataself.prev None # 前驱指针self.next None # 后继指针class DoublyLinkedList:双向链表实现支持双向遍历def __init__(self):self.head Noneself.tail None # 尾指针方便尾部操作self._size 0def append(self, data):尾部追加new_node DoublyNode(data)if not self.head:self.head self.tail new_nodeelse:self.tail.next new_nodenew_node.prev self.tailself.tail new_nodeself._size 1def delete(self, data):删除指定值的节点current self.headwhile current:if current.data data:if current.prev: # 不是头节点current.prev.next current.nextelse:self.head current.next # 是头节点if current.next: # 不是尾节点current.next.prev current.prevelse:self.tail current.prev # 是尾节点self._size - 1return Truecurrent current.nextreturn Falsedef __len__(self):return self._size# 性能对比链表 vs Python列表 import timedef benchmark_list_vs_linkedlist(n10000):对比列表和链表在头部插入的性能# Python 列表在头部插入 O(n)py_list []start time.perf_counter()for i in range(n):py_list.insert(0, i) # 每次插入都要移动所有元素list_time time.perf_counter() - start# 链表在头部插入 O(1)ll SinglyLinkedList()start time.perf_counter()for i in range(n):ll.insert(0, i) # 只需修改头指针ll_time time.perf_counter() - startprint(f列表头部插入{n}次: {list_time:.4f}秒)print(f链表头部插入{n}次: {ll_time:.4f}秒)print(f链表快了约{list_time/ll_time:.1f}倍)# benchmark_list_vs_linkedlist() # 取消注释运行# 使用示例 if __name__ __main__:sll SinglyLinkedList()sll.append(10)sll.append(20)sll.insert(1, 15) # 在索引1插入15 - [10, 15, 20]print(链表元素:, list(sll)) # 输出: [10, 15, 20]print(查找15:, sll.search(15)) # 输出: Truesll.delete(15)print(删除15后:, list(sll)) # 输出: [10, 20]dll DoublyLinkedList()dll.append(A)dll.append(B)dll.append(C)dll.delete(B)print(f双向链表长度: {len(dll)}) # 输出: 2