python双向链表（python双向链表的概念介绍）

说明

1    
    
   、更复杂的链表是双向链表或双面链表    
    
   。每个节点有两个链接:一个指向前一个节点    
    
   ，这个节点是第一个 


     


     

。

2 


     


     

、一个节点指向空值 


     


     

，另一个指向下一个节点

 




 




，当该节点指向最后一个节点时指向空值

 




 




。

操作方法

is_empty()链表是否为空   

   

  。

length(链表长度  

     

     
。

travel)经历链表


  




  




。

添加add(item)链表头部  


  


 。

添加到append(item)链表的尾部   
     
     。

添加insert(pos

 




 




、item)指定位置



   




   




。

remove删除节点 



 



。

搜索节点是否存在              。

实例

classNode(object): def__init__(self,elem): """ :paramelem:表元素域 next：下一结点链接域 cursor(cur)：游标 """ self.elem=elem #定义next指向空 self.next=None #定义next指向空 self.prev=None classDoubleLinkList(object): """ 一种更复杂的链表是“双向链表"或“双面链表"




    




    



。每个节点有两个链接:一个指向前一个节点   

   

  ，当此节点为第 一个节点时  

     

     
，指向空值;而另一个指向下一个节点


  




  




，当此节点为最后一个节点时  


  


 ，指向空值









。 """ def__init__(self,node=None): self._head=node#node.elemnode.next defis_empty(self): """链表是否为空""" returnself._headisNone deflength(self): """链表长度""" #cur游标   
     
     ，用来移动遍历节点 cur=self._head count=0 whilecurisnotNone: count+=1 cur=cur.next #count记录数量 returncount deftravel(self): """遍历整个链表""" cur=self._head whilecurisnotNone: print(cur.elem,end=) cur=cur.next defadd(self,item): """链表头部添加元素：头插法""" node=Node(item) #node的next指向_head node.next=self._head #_head指向新节点 self._head=node node.next.prev=node defappend(self,item): """链表尾部添加元素:尾插法""" node=Node(item) #下一结点链接域不为空 ifself.is_empty(): self._head=node else: cur=self._head whilecur.nextisnotNone: cur=cur.next cur.next=node node.prev=cur definsert(self,pos,item): """ pos:pos从0开始 pre:指定节点前一节点



   




   




，相当于游标 node：插入的指定节点 指定位置添加元素 """ #ifpos<=0头插法 ifpos<=0: self.add(item) #elifpos>(self.length()-1)尾插法 elifpos>(self.length()-1): self.append(item) #else插入法 else: cur=self._head count=0 #当循环退出后 



 



，cur指向pos whilecount<pos: count+=1 cur=cur.next #当循环退出后              ，cur指向pos位置 node=Node(item) #方式1： node.next=cur node.prev=cur.prev cur.prev.next=node cur.prev=node #方式2： #node.next=cur #node.prev=cur.prev #cur.prev=node #node.prev.next=node defremove(self,item): """删除元素""" #考虑删除头部   

   

  、尾部  

     

     
、中间节点 cur=self._head whilecurisnotNone: ifcur.elem==item: #先判断是否是头节点 ifcur==self._head: self._head=cur.next ifcur.next:#判断链表表是否只有一个节点 cur.next.prev=None else: cur.prev.next=cur.next ifcur.next:#判断链表是否是最后一个节点 cur.next.prev=cur.prev break else: cur=cur.next defsearch(self,item): """查找节点是否存在""" #1.创建游标 cur=self._head #2.遍历游标 whilecurisnotNone: #3.cur.elem=item ifcur.elem==item: returnTrue else: cur=cur.next returnFalse if__name__==__main__: DLL=DoubleLinkList() DLL.is_empty() l1=DLL.length() print(l1) DLL.append(55) DLL.is_empty() l2=DLL.length() print(l2) DLL.append(2) DLL.add(8) DLL.append(3) DLL.append(4) DLL.append(5) #5518234 DLL.insert(-1,9)#98552182345 DLL.insert(2,100)#98100552182345 DLL.travel()

以上就是python双向链表的概念介绍




    




    



，希望对大家有所帮助              。更多Python学习指路：Python基础教程