python如何实现双链表(python,开发技术)

实现双链表需要注意的地方

1、如何插入元素，考虑特殊情况：头节点位置，尾节点位置；一般情况：中间位置
2、如何删除元素，考虑特殊情况：头结点位置，尾节点位置；一般情况：中间位置

代码实现

1.构造节点的类和链表类

classNode:def__init__(self,data):self.data=dataself.next=Noneself.previous=NoneclassDoubleLinkList:'''双链表'''def__init__(self,node=None):self._head=node

以下方法均在链表类中实现

2. 判断链表是否为空

defis_empty(self):returnself._headisNone

3. 输出链表的长度

deflength(self):count=0ifself.is_empty():returncountelse:current=self._headwhilecurrentisnotNone:count+=1current=current.nextreturncount

4. 遍历链表

deftravel(self):current=self._headwhilecurrentisnotNone:print("{0}".format(current.data),end="")current=current.nextprint("")

5.头插法增加新元素

defadd(self,item):node=Node(item)#如果链表为空，让头指针指向当前节点ifself.is_empty():self._head=node#注意插入的顺序，else:node.next=self._headself._head.previous=nodeself._head=node

6. 尾插法增加新元素

defappend(self,item):node=Node(item)#如果链表为空，则直接让头指针指向该节点ifself.is_empty():self._head=node#需要找到尾节点，然后让尾节点的与新的节点进行连接else:current=self._headwhilecurrent.nextisnotNone:current=current.nextcurrent.next=nodenode.previous=current

7. 查找元素是否存在链表中

defsearch(self,item):current=self._headfound=FalsewhilecurrentisnotNoneandnotfound:ifcurrent.data==item:found=Trueelse:current=current.nextreturnfound

8. 在某个位置中插入元素

definsert(self,item,pos):#特殊位置，在第一个位置的时候，头插法ifpos<=0:self.add(item)#在尾部的时候，使用尾插法elifpos>self.length()-1:self.append(item)#中间位置else:node=Node(item)current=self._headcount=0whilecount<pos-1:current=current.nextcount+=1#找到了要插入位置的前驱之后，进行如下操作node.previous=currentnode.next=current.nextcurrent.next.previous=nodecurrent.next=node

#换一个顺序也可以进行definsert2(self,item,pos):ifpos<=0:self.add(item)elifpos>self.length()-1:self.append(item)else:node=Node(item)current=self._headcount=0whilecount<pos:current=current.nextcount+=1node.next=currentnode.previous=current.previouscurrent.previous.next=nodecurrent.previous=node

9. 删除元素

defremove(self,item):current=self._headifself.is_empty():returnelifcurrent.data==item:#第一个节点就是目标节点，那么需要将下一个节点的前驱改为None然后再将head指向下一个节点current.next.previous=Noneself._head=current.nextelse:#找到要删除的元素节点whilecurrentisnotNoneandcurrent.data!=item:current=current.nextifcurrentisNone:print("notfound{0}".format(item))#如果尾节点是目标节点，让前驱节点指向Noneelifcurrent.nextisNone:current.previous.next=None#中间位置，因为是双链表，可以用前驱指针操作else:current.previous.next=current.nextcurrent.next.previous=current.previous

#第二种写法defremove2(self,item):"""删除元素"""ifself.is_empty():returnelse:cur=self._headifcur.data==item:#如果首节点的元素即是要删除的元素ifcur.nextisNone:#如果链表只有这一个节点self._head=Noneelse:#将第二个节点的prev设置为Nonecur.next.prev=None#将_head指向第二个节点self._head=cur.nextreturnwhilecurisnotNone:ifcur.data==item:#将cur的前一个节点的next指向cur的后一个节点cur.prev.next=cur.next#将cur的后一个节点的prev指向cur的前一个节点cur.next.prev=cur.prevbreakcur=cur.next

10. 演示

my_list=DoubleLinkList()print("add操作")my_list.add(98)my_list.add(99)my_list.add(100)my_list.travel()print("{:#^50}".format(""))print("append操作")my_list.append(86)my_list.append(85)my_list.append(88)my_list.travel()print("{:#^50}".format(""))print("insert2操作")my_list.insert2(66,3)my_list.insert2(77,0)my_list.insert2(55,10)my_list.travel()print("{:#^50}".format(""))print("insert操作")my_list.insert(90,4)my_list.insert(123,5)my_list.travel()print("{:#^50}".format(""))print("search操作")print(my_list.search(100))print(my_list.search(1998))print("{:#^50}".format(""))print("remove操作")my_list.remove(56)my_list.remove(123)my_list.remove(77)my_list.remove(55)my_list.travel()print("{:#^50}".format(""))print("remove2操作")my_list.travel()my_list.remove2(100)my_list.remove2(99)my_list.remove2(98)my_list.travel()