# code:utf-8 # createTime:2023.8.17 # ----------------------------------------------------------------------------- class Node: """ 节点类，每个数据就是一个节点， 包含一个数据位和一个指针位， 指针指向下一个数据的内存地址 """ def __init__(self, data=None): # 数据位 self.data = data # 指针位 self.next = None # 输出节点的值 def __str__(self): return str(self.data) # ----------------------------------------------------------------------------- # 为链表定义的错误类型 ---所需删除元素未找到 class DeleteNotFindError(Exception): def __init__(self, message): super().__init__(message) # ----------------------------------------------------------------------------- class Link: """单向链表""" def __init__(self): self.head = None # 头指针 self.END = None # 尾指针 self._size = 0 # 链表大小的计数变量 # function -> 追加数据 def append(self, data)->None: # 初始化一个节点 node = Node(data = data) # 判断链表是否为空，如果链表不为空 if self.END: self.END.next = node # 将指针指向下一个位置 self.END = node # 将数据存入内存 # 如果链表为空 else: self.head = node # 头指针指向第一个数据 self.END = node # 尾指针指向第一个数据 # 计数变量的自增 self._size += 1 # function -> 获取链表大小 def getsize(self)->int: return int(self._size) # 返回生成器 def __iter__(self): insert = self.head # 获取头指针 # 判断下一个内存地址是否存在 while insert: val = insert.data # 获取内存地址处存放的数据 insert = insert.next # 将指针指向下一个地址 yield val # 使用生成器yield返回数据 # function -> 删除节点 def delete(self, data): # 此处采用双指针模式进行查找 insert = self.head # 前指针，指向查找元素的前一位 end = self.head # 后指针，指向查找元素 # 顺着链表查下去，时间复杂度位 O(n),如果后指针有值 while end: # 如果值相等 if end.data == data: # 如果需查找元素在开头 if end == self.head: self.head = self.head.next # 直接修改头指针的指向 else: insert.next = end.next # 将前指针的指向修改为后指针的下一位 self._size -= 1 # 计数变量自减 # 利用return结束循环 return # 双指针依次指向所有节点，知道查找到 insert = end end = end.next else: # 输出错误提示 raise DeleteNotFindError(f"Not find {data} in Link") # function -> 搜索节点 def find(self, data)->bool: # 这里直接套用iter方法 for i in self.__iter__(): # 找到节点 if i == data: return True # 返回True else: return False # 未找到节点返回False # function -> 清空链表 def clear(self): """clear the entire Linklist""" self.head = None self.END = None self._size = 0 # ----------------------------------------------------------------------------- class Nodes(object): def __init__(self, data=None, next=None, prev=None): self.data = data # 节点数据 self.next = next # 下一节点指针 self.prev = prev # 上一节点指针 # ----------------------------------------------------------------------------- class DoubleLink(object): def __init__(self): self.head = None # 头节点 self.end = None # 尾节点 self._size = 0 # 计数 # function -> 添加元素 def append(self, data): nodes = Nodes(data, None, None) if self.head is None: self.head = nodes self.end = self.head else: nodes.prev = self.end self.end.next = nodes self.end = nodes self._size += 1 # function -> 删除元素 def delete(self, data): # 删除元素分为四种不同的情况，这里要进行分类讨论 # 第一种，链表为空 current = self.head if current is None: # 输出错误提示 raise DeleteNotFindError(f"Not find {data} in DoubleLink") # 第二种，要删除的节点位于链表头部 elif current.data == data: self.head = current.next self.head.prev = None self._size -= 1 elif self.end.data == data: self.end = self.end.prev self.end.next = None self._size -= 1 else: while current: if current.data == data: current.prev.next = current.next current.next.prev = current.prev self._size -= 1 return current = current.next else: raise DeleteNotFindError(f"Not find {data} in DoubleLink") # function -> 获取链表节点数 def getsize(self): return int(self._size) # 返回生成器 def __iter__(self): insert = self.head # 获取头指针 # 判断下一个内存地址是否存在 while insert: val = insert.data # 获取内存地址处存放的数据 insert = insert.next # 将指针指向下一个地址 yield val # 使用生成器yield返回数据
说明：Node是单向链表的节点类，Nodes则是双向节点类
使用实例：
from main import * # 导入链表代码所在文件 # 单链表 test = Link() for i in range(1,10): test.append(i) for i in test: print(i) print("__________________________") # 双链表 test = DoubleLink() for i in range(1,10): test.append(i) test.delete(5) for i in test: print(i)
结果：
1
2
3
4
5
6
7
8
9
__________________________
1
2
3
4
6
7
8
9