本文链表维护了 head、tail、size 三个属性功能包含增、删删除单个和删除多个、查、反转、清除、重写魔法方法等。详见下文代码块后续实现企业级哨兵节点dummy head链表实现# 节点类classListNode:# 每一个单个的节点初始化的时候数值域必须有值指针域为Nonedef__init__(self,value):# 数值域self.valuevalue# 指针域self.nextNone# 链表类classLinkedList: 初始化链表类链表类我们设置三个对象属性 头head 尾tail 大小size 注意在操作链表时需要维护这三个属性 让 head 始终指向链表的第一个元素 tail 始终指向链表的最后一个元素 size 始终是当前更改后链表的大小 def__init__(self,nodeNone):self.headnode self.tailnode self.size0# 节点存在 需要遍历ifnode:self.size1# 这里注意一个细节# while判断cur.next是否是空 最后cur获取到的就是最后一个节点# while判断cur是否是空 最后cur获取到的就是Nonecurnodewhilecur.next:self.size1curcur.nextself.tailcur# 判空defis_empty(self):returnself.headisNone# 获取链表所有的值defget_values(self):node_values[]curself.headwhilecur:node_values.append(cur.value)curcur.nextreturnnode_values# 头部插入注意要维护head、size、taildefprepend(self,value):new_nodeListNode(value)# 空链表需要维护tailifself.is_empty():self.headnew_node self.tailnew_node# 维护链表大小self.size1return# 新插入节点的指针域 指向旧头节点new_node.nextself.head# 头指向新节点self.headnew_node# 维护链表大小self.size1# 尾部插入注意要维护head、size、taildefappend(self,value):new_nodeListNode(value)# 空ifself.is_empty():self.headnew_node self.tailnew_node self.size1return# 非空self.tail.nextnew_node# 旧尾节点挂上新节点self.tailnew_node# 更新尾指针为新节点self.size1# 根据值删除单个节点注意要维护head、size、taildefremove(self,value):# 空ifself.is_empty():return# 情况1 删除的是头节点ifself.headandself.head.valuevalue:# 如果链表只有一个节点 维护tailifself.size1:self.headNoneself.tailNoneelse:self.headself.head.nextself.size-1return# 情况2删除的是中间节点/尾节点prevself.head curself.head.nextwhilecur:# 找到了ifcur.valuevalue:prev.nextcur.nextself.size-1# 删除的是尾节点ifcur.nextisNone:self.tailprevreturn# 未找到 后移prevcur curcur.next# 根据值删除所有重复节点 注意要维护head、size、taildefremove_all(self,value):# 空ifself.is_empty():return# 情况1 删除的是头节点whileself.headisnotNoneandself.head.valuevalue:# 如果链表只有一个节点 维护tailifself.size1:self.headNoneself.tailNoneelse:self.headself.head.nextself.size-1# 删除完直接退出ifself.is_empty():return# 情况2删除的是中间节点/尾节点prevself.head curself.head.nextwhilecur:# 找到了ifcur.valuevalue:prev.nextcur.nextself.size-1# 删除的是尾节点ifcur.nextisNone:self.tailprev curprev.nextelse:# 未找到 后移prevcur curcur.next# 在指定位置插入元素注意要维护head、size、taildefinsert(self,index,value):# 判断是否越界ifindex0orindexself.size:raiseIndexError(index out of range)# 在开始节点插入ifindex0:self.prepend(value)return# 在结束节点插入ifindexself.size:self.append(value)return# 在中间插入new_nodeListNode(value)curself.headfor_inrange(index-1):curcur.nextnew_node.nextcur.nextcur.nextnew_node self.size1# 链表反转注意要维护head、taildefreverse(self):ifself.is_empty()orself.size1:return# 双指针prevNonecurself.head old_first_nodeself.headwhilecur:tempcur.nextcur.nextprev# 后移prevcur curtemp self.headprev self.tailold_first_node# 根据值查找元素是否存在defsearch(self,value):curself.headwhilecur:ifcur.valuevalue:returnTruecurcur.nextreturnFalse# 清除链表defclear(self):self.headNoneself.tailNoneself.size0# 重写len魔法方法def__len__(self):returnself.size# 重写str魔法方法 方法中的map和join方法详细介绍见结尾扩展知识def__str__(self):# 获取链表中所有的值node_valuesself.get_values()# 1. map(str, val_list)迭代器把每个数字转字符串 必须要转否则抛TypeErrornode_str_valuesmap(str,node_values)# 2. -.join(迭代器)直接遍历迭代器拼接无需转列表return-.join(node_str_values)if__name____main__:node1ListNode(2)node2ListNode(2)node3ListNode(1)node4ListNode(2)node5ListNode(3)node1.nextnode2 node2.nextnode3 node3.nextnode4 node4.nextnode5 llLinkedList(node1)print(初始\t,ll,长度,len(ll))ll.remove(2)print(删第一个2\t,ll,长度,len(ll))ll.remove_all(2)print(删除全部2\t,ll,长度,len(ll))ll.insert(1,99)print(下标1插入99\t,ll,长度,len(ll))ll.reverse()print(反转链表\t,ll,长度,len(ll))ll.append(666)print(尾部追加验证tail\t,ll,长度,len(ll))print(查找99,ll.search(99))复杂度方法时间复杂度空间复杂度prependO(1)O(1)appendO(1)O(1)removeO(n)O(1)remove_allO(n)O(1)insertO(n)O(1)reverseO(n)O(1)searchO(n)O(1)get_valuesO(n)O(n)map和join扩展 map方法介绍 语法 map(function, *iterables) 参数 参数1: 处理函数内置函数/自定义/lambda 参数2: 任何可迭代的对象列表、元组、迭代器 返回值 map 迭代器惰性求值节省内存只能遍历 1 次 核心作用 把可迭代对象里每一个元素依次传入 function 执行批量转换数据 join方法介绍 语法 分割字符串.join(iterable) 调用者 字符串作为拼接分隔符--、- 参数 任意可迭代对象列表、元组、map迭代器、生成器 强制要求 可迭代对象里的每一个元素必须是字符串类型否则抛TypeError 核心作用 用指定分隔符把一组字符串拼成一整段字符串 # ---------------------- map方法 -----------------------# 批量转字符串vals[1,2,3]str_valsmap(str,vals)# 记着返回的是迭代器# print(next(str_vals))# print(next(str_vals))# print(next(str_vals))print(list(str_vals))# [1, 2, 3]# 疑问list也能取迭代器吗# 回答任意迭代器map、生成器、range、文件对象等都能直接丢进 list()一次性把迭代器里所有元素取出转为普通列表。# 自定义 lambda 处理vals[1,2,3]resmap(lambdax:x**2,vals)print(list(res))# [1,4,9]# 多个可迭代对象并行映射a[1,2]b[10,20]resmap(lambdax,y:xy,a,b)print(list(res))# [11,22]# 注意点 迭代器只能遍历一次demo[1,2,3]resmap(lambdax:x**2,demo)print(list(res))# [1,4,9]print(list(res))# [] 耗尽无元素# ------------------------ join方法 ----------------------# 普通列表拼接arr[1,2,3]s-.join(arr)print(s)# 1-2-3# 配合 map 解决非字符串报错-.join([1,2,3])# 报错列表里是数字不是字符串-.join(map(str,[1,2,3]))# 1-2-3 map把所有数字转字符串再join# 空可迭代对象返回空字符串-.join([])# # 常见报错原因# 报错int不是str-.join([1,2,3])# 解决map(str, 容器) 统一转为字符串