簡(jiǎn)介：
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。
節(jié)點(diǎn)：
class Node():
""" 節(jié)點(diǎn) """
????def __int__(self,item):
????????self.itme = item
????????self.next = next
雙向鏈表:?
.class Single_cycle_link_list(object,SingleLinkList):
“”“單向循環(huán)鏈表”“”
? ??def __init__(self,node=None):
? ??????self.__head = node
????????if node: ?#如果節(jié)點(diǎn)不為空，則節(jié)點(diǎn)后繼指向鏈表頭，完成循環(huán)
? ??????????ode.next = self.__head
判空方法：
def is_empty(self):
“”“判斷鏈表是否為空”“”
? ??:return: self.__head == None
求鏈表長(zhǎng)度：
def length(self):
“”“返回鏈表長(zhǎng)度”“”
????if self.is_empty():
? ??????return True
? ??else:
????????cur = self.__head
????????count = 1
? ??????while cur.next != self.__head: #如果游標(biāo)不等于鏈表頭，一直偏移數(shù)數(shù)
? ??????????count += 1
? ??????????cur = cur.next
????????return count
打印元素展示
def travel():
“”“打印鏈表元素”“”
? ??if self.is_empty():
? ??????return None
? ??cur = self.__head # 游標(biāo)
? ??while cur.next != self.__head:
? ??????print(cur.elem,end='')
? ??????cur = cur.next
? ??print(cur.elem) #退出循環(huán)，游標(biāo)偏移停止的時(shí)候，再打印最后的元素
尾部插入：
def append(self,item):
“”“尾部插入”“”
????node = Node()
????if self.is_empty():
? ??????self.__head = node
? ??????node.next = self.__head
? ? else:
? ??????cur = self.__head
? ??????while cur.next != self.__head: #游標(biāo)位置未指向頭結(jié)點(diǎn)，則繼續(xù)偏移
? ??????????cur = cur.next ???
? ??????node.next = self.__head ???#退出循環(huán)后，游標(biāo)位置則為最后?
????????cur.next = node
頭插法：
def add(self,item):
“”“頭部插入元素”“”
? ??node = Node() #實(shí)例化節(jié)點(diǎn)
????if self.is_empty: #如果是空鏈表則：空節(jié)點(diǎn)next指向頭結(jié)點(diǎn)? ??
? ??????self.__head = node
? ??????node.next = self.__head
? ??else:
? ??????while cur.next != self.__head: #只要指針不是指向首節(jié)點(diǎn)
? ??????cur = cur.next #開始偏移
? ??????#當(dāng)退出循環(huán)，游標(biāo)cur當(dāng)前指向是尾節(jié)點(diǎn)
? ??????node.next = self.__head
位置插入:
def insert(self,pos,item):
""索引位置進(jìn)行插入""
????if pos <= 0:? ??
? ??????self.add(item)
? ? elif?pos > (self.length()-1)::
? ??????self.append(item)
? ? else:
? ? ? ? cur = self.__head
? ? ? ? count = 0
? ? ? ? while count < pos:
? ? ? ? ? ? count += 1
? ? ? ? ? ? cur = cur.next ? #偏移到末尾
? ? ? ? node = Node(item)
? ? ? ? node.next = cur?
? ? ? ? node.perv = cur.perv
? ? ? ? cur.perv.next = cur.perv
? ? ? ? cur.perv = node?
查找元素：
def search(self,item):
“”“查找元素”“”
????if self.is_empty(): #判斷鏈表是否為空
? ??????return False
? ??cur = self.__head
? ??while cur.next != self.__head:
? ??????if cur.elem == item:
? ??????????return True
? ? ? ? else:
? ??????????cur = cur.next?
? ??#如果單節(jié)點(diǎn)，且next是指向首節(jié)點(diǎn)，則不進(jìn)入循環(huán)，再加判斷
????if cur.elem == item:
? ??????return True
? ??return False
刪除元素
def remove(self,pos,item):
“”“刪除元素”“”
????cur = self.__head
? ??per = None
? ??while cur.next != self.__head：?#如果游標(biāo)的next不是指向鏈表頭（尾節(jié)點(diǎn)），則進(jìn)入循環(huán)偏移
? ??????if cur.elem == item: #如果游標(biāo)指向的元素恰巧是傳入的參數(shù)
? ??????????if cur == self.__head： #再判斷是不是頭節(jié)點(diǎn) ??
? ??????????????self.__head = cur.next
? ? ? ? ? ? else: ?#中間節(jié)點(diǎn)的情況
? ??????????????per.next = cur.next
? ? ? ? ? ? break
? ? ? ? else:
? ??????????#如果不是指向傳入的參數(shù)，游標(biāo)per指向游標(biāo)curs
? ??????????per = cur
? ??????????cur = cur.next
? ??#直到退出循環(huán)，游標(biāo)遍歷位置是指向尾節(jié)點(diǎn)
? ??if cur.elem == item: #如果是尾節(jié)點(diǎn)，是不會(huì)進(jìn)入上面的循環(huán)，再加判斷
? ??????if cur == self.__head: #如果只有一個(gè)節(jié)點(diǎn)
? ??????????self.__head = None
? ??????else:
? ??????????pre.next = cur.next
