雙鏈表的每個(gè)節(jié)點(diǎn)都有兩個(gè)指針莫鸭，一個(gè)指向直接后繼，一個(gè)指向直接前驅(qū)横殴。在雙向鏈表的任意一個(gè)節(jié)點(diǎn)都能很方便的訪問(wèn)其前后節(jié)點(diǎn)被因。其基本結(jié)構(gòu)如下：
雙向鏈表結(jié)構(gòu)圖
1.構(gòu)造雙向循環(huán)鏈表
雙向鏈表和單向鏈表只有在insert、append衫仑、remove氏身、add方法上有差別，因此這里可以使用面向?qū)ο蟮乃枷?/strong>惑畴，繼承于單向鏈表，然后重寫這四種方法航徙。
1.1 構(gòu)造節(jié)點(diǎn)
雙向鏈表的節(jié)點(diǎn)比單向鏈表多一個(gè)prev指針指向前一個(gè)節(jié)點(diǎn)
# 定義節(jié)點(diǎn)
class Node(object):
"""節(jié)點(diǎn)"""
def __init__(self,item):
self.elem = item
self.next = None
self.prev = None
1.2 重寫add函數(shù)【頭插法】
作用：在鏈表頭部添加元素
- 傳入的item不是節(jié)點(diǎn)類型如贷，因此需要使用Node將其轉(zhuǎn)為節(jié)點(diǎn)。實(shí)例為node對(duì)象
- 讓node指向下一個(gè)元素的指針指向當(dāng)前的頭節(jié)點(diǎn)到踏，即self.__head杠袱。node.next = self.__head
- 將self.__head賦值為node。self.__head = node
-
讓node的下一個(gè)節(jié)點(diǎn)的prev指針指向node【與單向鏈表的區(qū)別】
【注意】 - 必須先讓node的下一個(gè)指針先指向當(dāng)前的頭節(jié)點(diǎn)窝稿，然后重新設(shè)置node為頭節(jié)點(diǎn)
add函數(shù)圖解
def add(self,item):
"""頭部添加"""
node = Node(item)
node.next = self.__head
self.__head = node
node.next.prev = node # 讓node的下一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向node
1.3 重寫insert函數(shù)
作用：在指定位置插入元素
- 創(chuàng)建一個(gè)cur游標(biāo),起使指向頭節(jié)點(diǎn)的位置楣富，即cur = self.__head
- 創(chuàng)建一個(gè)計(jì)數(shù)器count，用于記錄索引后和pos比較
- 當(dāng)count移動(dòng)到pos位置【區(qū)別于單向鏈表移動(dòng)到pos-1位置伴榔，因?yàn)榇嬖谇昂笾羔樜坪钥梢砸苿?dòng)到pos位置】
- 找到pos位置后庄萎，將node的next指針指向cur當(dāng)前節(jié)點(diǎn)；將cur當(dāng)前節(jié)點(diǎn)的next指針指向node塘安，node的prev指針指向cur的prev節(jié)點(diǎn)【先操作node糠涛，不改變?cè)湵斫Y(jié)構(gòu)】
- 讓node的prev指針指向當(dāng)前cur所在節(jié)點(diǎn)的prev節(jié)點(diǎn)
- 讓cur所在節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next指針指向node
- 讓cur當(dāng)前節(jié)點(diǎn)的prev指針指向node
【注意】 - 當(dāng)輸入的pos<=0時(shí)，視為其在頭部插入兼犯，直接調(diào)用add方法
- 當(dāng)輸入的pos>鏈表的長(zhǎng)度時(shí)忍捡，視為在尾部，直接調(diào)用append方法
insert函數(shù)圖解
def insert(self,pos,item):
"""在指定位置插入"""
if pos <=0:
self.add(item)
elif pos> (self.length() -1):
self.append(item)
else:
cur = self.__head
count = 0
# 游標(biāo)直接走到pos的位置
while count < pos :
count += 1
cur = cur.next
# 當(dāng)循環(huán)推出后切黔，cur指向pos的位置
node = Node(item)
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
1.4 重寫append函數(shù)【尾插法】
作用：在鏈表尾部添加元素
- 創(chuàng)建一個(gè)cur游標(biāo)砸脊，起使指向頭節(jié)點(diǎn)的位置，即cur = self.__head
- 當(dāng)cur.next為None時(shí)纬霞，則處于最后一個(gè)節(jié)點(diǎn)凌埂，因此遍歷條件為 while cur.next!=None
- 讓cur游標(biāo)遍歷到鏈表最后一個(gè)節(jié)點(diǎn)的位置，讓當(dāng)前節(jié)點(diǎn)next指針指向node
- 讓node的prev指針指向cur【與單向鏈表的區(qū)別】
【注意】 - 當(dāng)鏈表為空時(shí)险领，不存在cur.next侨舆，因此需要考慮鏈表為空的情況
-
當(dāng)鏈表為空時(shí)，直接將當(dāng)前的頭節(jié)點(diǎn)賦值為node
append函數(shù)圖解
def remove(self,item):
"""刪除節(jié)點(diǎn)"""
cur = self.__head
while cur != None:
if cur.elem == item:
# 先判斷此節(jié)點(diǎn)是否是頭節(jié)點(diǎn)
self.__head = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = None
else:
cur.prev.next = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = cur.prev
break
else:
cur = cur.next
1.5 重寫remove函數(shù)
作用：刪除指定位置元素
- 遍歷鏈表【while cur != None】,如果當(dāng)前節(jié)點(diǎn)不是要?jiǎng)h除的節(jié)點(diǎn)绢陌，則移動(dòng)cur
- 當(dāng)cur指向的元素等于要?jiǎng)h除的元素相等時(shí)挨下，先判斷是否是頭節(jié)點(diǎn)，如果是頭節(jié)點(diǎn)脐湾，直接讓self.__head = cur.next臭笆，讓cur.next.prev指向None【由于cur.next不一定存在，因此需要添加判斷條件if】
- 如果不為頭節(jié)點(diǎn)秤掌，則讓cur的前一個(gè)結(jié)點(diǎn)的next指針指向cur的下一個(gè)節(jié)點(diǎn)cur.prev.next = cur.next愁铺；讓cur的下一個(gè)節(jié)點(diǎn)的prev指針指向cur的前一個(gè)節(jié)點(diǎn) cur.next.prev = cur.prev【由于cur.next不一定存在，因此需要添加判斷條件if】
【注意】 - 如果要?jiǎng)h除的節(jié)點(diǎn)為頭節(jié)點(diǎn)闻鉴，即cur處于head的位置茵乱，則直接讓頭節(jié)點(diǎn)指向cur的下一個(gè)節(jié)點(diǎn)即可
remove函數(shù)圖解
def remove(self,item):
"""刪除節(jié)點(diǎn)"""
cur = self.__head
while cur != None:
if cur.elem == item:
# 先判斷此節(jié)點(diǎn)是否是頭節(jié)點(diǎn)
self.__head = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = None
else:
cur.prev.next = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = cur.prev
break
else:
cur = cur.next
2.完整代碼
# 雙向鏈表可以先繼承單向鏈表，然后重寫add孟岛、travel瓶竭、append、remove方法
class DoubleLinkList(SingleLinklist):
def add(self,item):
"""頭部添加"""
node = Node(item)
node.next = self.__head
self.__head = node
node.next.prev = node # 讓node的下一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向node
def append(self,item):
"""尾部添加元素渠羞，只比單鏈表的append方法多一行代碼"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head()
while cur.next != None:
cur = cur.next
cur.next = node
node.prev = cur
def insert(self,pos,item):
"""在指定位置插入"""
if pos <=0:
self.add(item)
elif pos> (self.length() -1):
self.append(item)
else:
cur = self.__head
count = 0
# 游標(biāo)直接走到pos的位置
while count < pos :
count += 1
cur = cur.next
# 當(dāng)循環(huán)推出后斤贰，cur指向pos的位置
node = Node(item)
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
def remove(self,item):
"""刪除節(jié)點(diǎn)"""
cur = self.__head
while cur != None:
if cur.elem == item:
# 先判斷此節(jié)點(diǎn)是否是頭節(jié)點(diǎn)
self.__head = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = None
else:
cur.prev.next = cur.next
# cur.next可能是None
if cur.next:
cur.next.prev = cur.prev
break
else:
