Python实现双向链表基本操作

第Python实现双向链表基本操作双向链表的基本操作的实现，供大家参考，具体内容如下

在之前的博客中介绍了三种链表，分别是单链表、单向循环链表以及双向链表。本篇博客将用Python来实现双向链表的如下操作。（用到的工具是Python3)

is_empty():判断链表是否为空

length():返回链表的长度

travel():遍历

add(item):在头部添加一个节点

append(item):在尾部添加一个节点

insert(pos,item):在指定位置pos添加一个节点

remove(item):删除一个节点

search(item):查找节点是否存在

Python实现

classNode(object):

'''双向链表节点'''

def__init__(self,item):

self.item=item

self.next=None

self.prev=None

classDoubleLink(object):

'''双向链表'''

def__init__(self):

self._head=None

defis_empty(self):

'''判断是否为空'''

returnself._head==None

deflength(self):

'''返回链表的长度'''

cur=self._head

count=0

whilecur!=None:

count+=1

cur=cur.next

returncount

deftravel(self):

'''遍历链表'''

cur=self._head

whilecur!=None:

print(cur.item)

cur=cur.next

print("")

defadd(self,item):

'''头部插入元素'''

node=Node(item)

ifself.is_empty():

#如果是空链表，将_head指向None

self._head=node

else:

#将node的next指向_head的头节点

node.next=self._head

#将_head的头节点的prev指向node

self._head.prev=node

#将_head指向node

self._head=node

defappend(self,item):

'''尾部插入元素'''

node=Node(item)

ifself.is_empty():

self._head=node

else:

#移动到链表尾部

cur=self._head

whilecur.next!=None:

cur=cur.next

#将尾结点cur的next指向node

cur.next=node

#将node的prev指向cur

node.prev=cur

defsearch(self,item):

'''查找元素是否存在'''

cur=self._head

whilecur!=None:

ifcur.item==item:

returnTrue

cur=cur.next

returnFalse

指定位置插入节点

在该操作中，要注意链的指向的先后顺序。

definsert(self,pos,item):

'''在指定位置添加节点'''

ifpos=0:

self.add(item)

elifpos(self.length()-1):

self.append(item)

else:

node=Node()

cur=self._head()

count=0

#移动到指定的前一个位置

whilecurpos-1:

count+=1

cur=cur.next

#将node的prev指向cur

node.prev=cur

#将node的next指向cur的下一个节点

node.next=cur.next

#将cur的下一个节点的prev指向node

cur.next.prev=node

#将cur.next指向node

cur.next=node

删除元素

defremove(self,item):

'''删除元素'''

ifself.is_empty():return

else:

cur=self._head

ifcur.item==item:

#如果首节点的元素是要删除的元素

ifcur.next==None:

#如果链表中只有一个节点

self._head=None

else:

cur.next.prev=None

self._head=cur.next

return

whilecur!=None:

ifcur.item==item: