python 第15课 高级 （链表 以及单链表的代码）

链表本质与实现链表采用彻底的分离式存储结构节点内存地址完全不连续仅通过指针/地址串联。Python中通过节点对象的引用实现链接。内存特点每个节点独立存在于内存任意位置节点间通过存储的地址建立联系唯一入口是头指针head丢失则无法访问后续节点节点结构实现节点是最小存储单元包含两个核心部分classListNode:def__init__(self,val0,nextNone):self.valval# 数据域存储实际内容self.nextnext# 指针域存储下一节点引用新创建节点时next默认为None表示当前节点是链表的末端节点。单向链表整体架构典型单向链表结构示意head → 节点A → 节点B → 节点C → Nonehead指针指向首节点每个节点的next指向后续节点末节点next为None标识链表结束链表管理类链表类负责维护整体结构classSinglyLinkedList:def__init__(self):self.headNone# 初始空链表self.size0# 节点计数器核心操作方法判空检查defis_empty(self):returnself.headisNone长度计算deflength(self):curself.head count0whilecur:count1curcur.nextreturncount遍历输出deftraverse(self):result[]curself.headwhilecur:result.append(str(cur.val))curcur.nextprint( - .join(result) - NULL)头部插入defadd(self,item):new_nodeListNode(item)new_node.nextself.head self.headnew_node尾部追加defappend(self,val):new_nodeListNode(val)ifnotself.head:self.headnew_nodeelse:curself.headwhilecur.next:curcur.nextcur.nextnew_node内存存储特性链表在内存中的实际形态每个节点占据独立内存块节点地址随机分布无连续性节点间仅通过指针关联与传统数组对比数组需要连续内存空间链表充分利用内存碎片数组支持随机访问链表必须顺序遍历复杂度分析时间复杂度头部插入/删除O(1)按索引访问O(n)尾部操作O(n)空间特性每个节点额外存储指针无预分配内存机制动态增长无容量限制双向链表实现总结双向链表节点类classDoubleNode(object):def__init__(self,item):self.itemitem# 数据域self.prevNone# 前驱指针默认指空self.nextNone# 后继指针默认指空双向链表类classDoubleLinkList(object):def__init__(self):self.headNone# 头指针self.tailNone# 尾指针方便尾部操作defis_empty(self):returnself.headisNonedeflength(self):curself.head count0whilecur:count1curcur.nextreturncountdeftravel_front(self):curself.headwhilecur:print(cur.item,end - )curcur.nextprint(NULL)deftravel_back(self):curself.tailwhilecur:print(cur.item,end - )curcur.prevprint(NULL)defadd(self,item):nodeDoubleNode(item)ifself.is_empty():self.headnode self.tailnodeelse:node.nextself.head self.head.prevnode self.headnodedefappend(self,item):nodeDoubleNode(item)ifself.is_empty():self.headnode self.tailnodeelse:self.tail.nextnode node.prevself.tail self.tailnodedefinsert(self,pos,item):ifpos0:self.add(item)elifposself.length():self.append(item)else:curself.head count0whilecountpos:curcur.nextcount1nodeDoubleNode(item)node.prevcur.prev node.nextcur cur.prev.nextnode cur.prevnodedefremove(self,item):curself.headwhilecur:ifcur.itemitem:ifcurself.head:self.headcur.nextifself.head:self.head.prevNoneelse:self.tailNoneelifcurself.tail:self.tailcur.prev self.tail.nextNoneelse:cur.prev.nextcur.nextcur.next.prevcur.prevreturnelse:curcur.nextdefsearch(self,item):curself.headwhilecur:ifcur.itemitem:returnTruecurcur.nextreturnFalse测试代码if__name____main__:dllDoubleLinkList()print( 空链表 )dll.travel_front()dll.add(10)dll.add(20)print(\n 头插 20,10 )dll.travel_front()dll.append(30)dll.append(40)print(\n 尾插 30,40 )dll.travel_front()print(\n 反向遍历 )dll.travel_back()dll.insert(2,25)print(\n 在位置2插入25 )dll.travel_front()dll.remove(25)print(\n 删除25后 )dll.travel_front()print(\n查找 30:,dll.search(30))print(链表长度:,dll.length())核心知识点双向链表节点包含三个部分数据域item、前驱指针prev和后继指针next。双向链表可以从头到尾或从尾到头遍历插入和删除操作比单向链表更方便因为可以直接访问前驱节点。双向链表的内存占用比单向链表稍大因为每个节点多了一个指针。插入操作需要修改四个指针新节点的prev和next以及前后节点的相应指针。删除操作只需要让前后节点互相指向跳过被删除节点。单向链表与双向链表对比指针数量单向链表有一个next指针双向链表有prev和next两个指针遍历方向单向链表只能从头到尾双向链表可以双向遍历插入/删除效率双向链表更高效内存占用双向链表稍大实现难度双向链表更复杂