Python實現雙向鏈表
之前寫的單向鏈表和環形鏈表都隻是單向的，隻能單向遍歷，不能根據後面的節點獲取前面的節點，除非進行反轉操作。
雙向鏈表每個節點都有兩個指針，這兩個指針分別指向前後兩個節點，這樣就可以從任意一個節點從兩個方向獲取其他的所有節點，非常方便。但是由於每個節點有兩個指針，所以雙向鏈表比較消耗空間。
在設計雙向鏈表時，通常會加上一個鏈表頭指針，該鏈表頭指針的數據字段不存放任何數據。
雙向鏈表的可以是環形的，也可以不是環形的，如果是環形的話，那麼最後一個節點的一個指針將指向鏈表頭，鏈表頭的一個指針將指向最後一個節點；如果不是環形的話，那麼最後一個節點的一個指針和鏈表頭的一個指針都將指向None。
我在這裡實現的是一個環形的雙向鏈表，這樣我就可以從鏈表頭開始，從兩個方向中任意選擇一個方向來進行操作。
我在這裡主要實現瞭環形雙向鏈表的：雙向新增，雙向遍歷，雙向插入，雙向刪除。
如圖為雙向環形鏈表示意圖，每一個節點都被兩個指針所指向，同時每個節點也指向瞭兩個節點。
實現代碼如下：
class Player:
"""節點類"""
def __init__(self):
"""初始化姓名，分數，指針"""
self.name = ''
self.score = 0
self.rlink = None
self.llink = None
def ergodic(head, num=None, is_print=False, left=False):
"""遍歷函數，num是遍歷到哪一個位置序號，is_print是否觸發打印方法，left表示是否由head開始往左遍歷"""
ptr = head
count = 0
while True:
if num == count:
break
if not left:
if ptr.rlink != head:
ptr = ptr.rlink
else:
break
else:
if ptr.llink != head:
ptr = ptr.llink
else:
break
count += 1
if is_print:
print('No.'+str(count), ptr.llink.name if ptr.llink != head else 'head', '<---',
ptr.name, ptr.score, '--->', ptr.rlink.name if ptr.rlink != head else 'head')
return ptr # 返回遍歷完成後的最後一個節點
head = Player() # 初始化一個鏈表頭指針，不用來存放任何數據
head.rlink = head # 初始化右指針
head.llink = head # 初始化左指針
while True:
select = input("(1).新增 (2).查看 (3).插入 (4).刪除 (5).離開\n輸入：")
if select == "1": # 新增節點，分為右新增和左新增
direction = input("(1).右新增 (2).左新增\n輸入：")
if direction not in ("1", "2"):
print("輸入錯誤")
continue
new_data = Player()
new_data.name = input("姓名：")
new_data.score = input("分數：")
if direction == "1": # 右新增
ptr = ergodic(head) # 從head開始向右遍歷獲取最後一個節點
ptr.rlink = new_data
new_data.llink = ptr
new_data.rlink = head
head.llink = new_data
else: # 左新增
ptr = ergodic(head, left=True) # 從head開始向左遍歷獲取最後一個節點
ptr.llink = new_data
new_data.rlink = ptr
new_data.llink = head
head.rlink = new_data
elif select == "2": # 遍歷查看所有節點，分為右遍歷和左遍歷
direction = input("(1).右遍歷 (2).左遍歷\n輸入：")
if direction == "1": # 右遍歷
ergodic(head, is_print=True)
elif direction == "2": # 左遍歷
ergodic(head, is_print=True, left=True)
else:
print("輸入錯誤")
elif select == '3': # 插入節點，分為右插入和左插入
direction = input("(1).右插入 (2).左插入\n輸入：")
if direction not in ("1", "2"):
print("輸入錯誤")
continue
try:
num = int(input("請輸入需要插入的節點位置序號：")) # 輸入序號必須是大於0的正整數，如果輸入大於最後一個節點的序號則插入到最後一個節點之後
if num < 1:
print("輸入必須為大於0的正整數")
continue
except ValueError:
print("輸入有誤")
continue
insert_data = Player()
insert_data.name = input("姓名：")
insert_data.score = input("分數：")
if direction == "1": # 右插入
ptr = ergodic(head, num - 1) # 獲取需要插入位置的前一個節點，新插入的節點就在這個節點的後面
insert_data.llink = ptr
insert_data.rlink = ptr.rlink
ptr.rlink = insert_data
insert_data.rlink.llink = insert_data
else: # 左插入
ptr = ergodic(head, num - 1, left=True)
insert_data.rlink = ptr
insert_data.llink = ptr.llink
ptr.llink = insert_data
insert_data.llink.rlink = insert_data
elif select == '4': # 刪除節點，分為右刪除和左刪除
direction = input("(1).右刪除 (2).左刪除\n輸入：")
if direction not in ("1", "2"):
print("輸入錯誤")
continue
try:
num = int(input("請輸入需要刪除的節點位置序號：")) # 輸入序號必須是大於0的正整數，如果輸入大於最後一個節點的序號則刪除最後一個節點
if num < 1:
print("輸入必須為大於0的正整數")
continue
except ValueError:
print("輸入有誤")
continue
if direction == "1": # 右刪除
ptr = ergodic(head, num) # 獲取需要刪除的節點
else: # 左刪除
ptr = ergodic(head, num, left=True)
ptr.llink.rlink = ptr.rlink
ptr.rlink.llink = ptr.llink
elif select == '5':
print("成功離開")
break
else:
print("輸入錯誤，請重試")
部分運行效果如下：
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。