Python實(shí)現(xiàn)雙向鏈表基本操作

第Python實(shí)現(xiàn)雙向鏈表基本操作雙向鏈表的基本操作的實(shí)現(xiàn)，供大家參考，具體內(nèi)容如下

在之前的博客中介紹了三種鏈表，分別是單鏈表、單向循環(huán)鏈表以及雙向鏈表。本篇博客將用Python來實(shí)現(xiàn)雙向鏈表的如下操作。（用到的工具是Python3)

is_empty():判斷鏈表是否為空

length():返回鏈表的長(zhǎng)度

travel():遍歷

add(item):在頭部添加一個(gè)節(jié)點(diǎn)

append(item):在尾部添加一個(gè)節(jié)點(diǎn)

insert(pos,item):在指定位置pos添加一個(gè)節(jié)點(diǎn)

remove(item):刪除一個(gè)節(jié)點(diǎn)

search(item):查找節(jié)點(diǎn)是否存在

Python實(shí)現(xiàn)

classNode(object):

'''雙向鏈表節(jié)點(diǎn)'''

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):

'''返回鏈表的長(zhǎng)度'''

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的頭節(jié)點(diǎn)

node.next=self._head

#將_head的頭節(jié)點(diǎn)的prev指向node

self._head.prev=node

#將_head指向node

self._head=node

defappend(self,item):

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

node=Node(item)

ifself.is_empty():

self._head=node

else:

#移動(dòng)到鏈表尾部

cur=self._head

whilecur.next!=None:

cur=cur.next

#將尾結(jié)點(diǎn)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

指定位置插入節(jié)點(diǎn)

在該操作中，要注意鏈的指向的先后順序。

definsert(self,pos,item):

'''在指定位置添加節(jié)點(diǎn)'''

ifpos=0:

self.add(item)

elifpos(self.length()-1):

self.append(item)

else:

node=Node()

cur=self._head()

count=0

#移動(dòng)到指定的前一個(gè)位置

whilecurpos-1:

count+=1

cur=cur.next

#將node的prev指向cur

node.prev=cur

#將node的next指向cur的下一個(gè)節(jié)點(diǎn)

node.next=cur.next

#將cur的下一個(gè)節(jié)點(diǎn)的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:

#如果首節(jié)點(diǎn)的元素是要?jiǎng)h除的元素

ifcur.next==None:

#如果鏈表中只有一個(gè)節(jié)點(diǎn)

self._head=None

else:

cur.next.prev=None

self._head=cur.next

return

whilecur!=None:

ifcur.item==item: