Python数据结构双向链表

本文转载自微信公众号《python与大数据分析》，作者是一只小鸟。转载本文请联系python与大数据分析公众号。双向链表也叫双向链表，是链表的一种。其中的每个数据节点都有两个指针，分别指向直接后继者和直接前驱者。因此，从双向链表中的任意一个节点开始，都可以方便地访问到它的前驱节点和后继节点。双链表和单链表在查找和遍历上没有区别。添加节点、添加节点、删除节点时，需要注意前后节点的修改。比单链表复杂，一不小心就会搞糊涂。方法与单链表相同。isempty(self)链表是否为空length(self)链表的长度travel(self)遍历整个链表add(self,item)向链表头部添加元素append(self,item)向链表尾部添加元素insert(self,item,index)在指定位置添加元素deletebyitem(self,item)根据数据项删除节点deletebyindex(self,index)根据某项删除节点indexpositionsearch(self,item)根据某个数据项查找节点是否存在update(self,index,item)暂无实现getitem(self,index)获取index位置对应的数据项getindex(self,item)获取数据项对应的索引位置如下：#!/usr/bin/envpython#-*-coding:UTF-8-*-#_ooOoo_#o8888888o#88"."88#(|-_-|)#O\=/O#____/`---'\____#.'\\||//`.#/\\|||:|||//\#/_|||||-:-|||||-\#||\\\-///||#|\_|'\--/''|_/|#\.-\__`-`___/-./#___`..'/--.--\`..__#.""'<`.___\_<|>_/___.'>'"".#||:`-\`.;`\_/`;.`/-`:||#\\`-.\___\/___/.-`//#==`-.____`-.___\_____/___.-`____.-'==#`=---=''''@Project:pythonalgorithms@File:doublelinklist.py@Author:winLife喝醉了@Date:2021/7/1323:00'''classNode(object):def__init__(self,data):self.prev=Noneself.data=dataself.next=NoneclassDoubleLinkList(object):def__init__(self):self.header=Noneself.currentnum=0defisempty(self):returnsself.header==Nonedeftravel(self):tempnode=self.headerwhiletempnode!=None:print("{}".format(tempnode.data),end="")tempnode=tempnode.nextprint("\r")defadd(self,item):node=Node(item)ifself.isempty():self.header=nodeself.currentnum+=1returnnode.next=self.headerself.header.prev=nodeself.header=nodeself.currentnum+=1defappend(self,item):ifself.isempty():self.add(item)self.currentnum+=1returntempnode=self.headerwhiletempnode.nextisnotNone:tempnode=tempnode.nextnode=Node(item)node.prev=tempnodetempnode.next=nodeself。currentnum+=1deflength(self):length=0tempnode=self.headerwhiletempnodeisnotNone:length+=1tempnode=tempnode.nextreturnlengthdefsearch(self,item):tempnode=self.headerwhiletempnode!=None:iftempnode.data==item:returnTrueelse:tempnode=tempnode。nextreturnFalsedefupdate(self,index,item):passdefgetitem(self,index):ifindex>self.currentnumorindex<=0:raiseIndexError("{}isnotfindinLinklist".格式(index))tempnode=self.headeri=1whileself.currentnum+1orindex<=0:raiseIndexError("{}isnotfindinLinklist".format(index))#指定位置为第一个即在头部插入ifindex==1:self.add(item)elifindex>self.currentnum-1:self.append(item)else:node=Node(item)foriinrange(1,index-1):tempnode=tempnode.nextnode.next=tempnode.nextnode.prev=tempnodetempnode.next.prev=nodetempnode.next=nodeself.currentnum+=1defdeletebyitem(self,item):tempnode=self.headerwhiletempnode!=None:iftempnode.data==item:self.currentnum-=1iftempnode==self.header:self.header=self.header.nextiftempnode.next:tempnode.next.prev=Nonereturniftempnode.nextisNone:tempnode.prev.next=临时节点.nextreturntempnode.prev.next=tempnode.nexttempnode.next.prev=tempnode.prevreturntempnode=tempnode.nextdefdeletebyindex(self,index):ifindex>self.currentnumorindex<=0:raiseIndexError("{}isnotfindinLinklist".format(index))i=1tempnode=self.headerifindex==1:self.header=tempnode.nextiftempnode.next:tempnode.prev=Noneself.currentnum-=1returnwhiletempnode.nextandi