快捷導(dǎo)航

Python實(shí)現(xiàn)雙向鏈表

更新時(shí)間：2022年05月25日 13:28:03 作者：HBLQ_GK

這篇文章主要為大家詳細(xì)介紹了Python實(shí)現(xiàn)雙向鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

之前寫的單向鏈表和環(huán)形鏈表都只是單向的，只能單向遍歷，不能根據(jù)后面的節(jié)點(diǎn)獲取前面的節(jié)點(diǎn)，除非進(jìn)行反轉(zhuǎn)操作。

雙向鏈表每個(gè)節(jié)點(diǎn)都有兩個(gè)指針，這兩個(gè)指針分別指向前后兩個(gè)節(jié)點(diǎn)，這樣就可以從任意一個(gè)節(jié)點(diǎn)從兩個(gè)方向獲取其他的所有節(jié)點(diǎn)，非常方便。但是由于每個(gè)節(jié)點(diǎn)有兩個(gè)指針，所以雙向鏈表比較消耗空間。

在設(shè)計(jì)雙向鏈表時(shí)，通常會(huì)加上一個(gè)鏈表頭指針，該鏈表頭指針的數(shù)據(jù)字段不存放任何數(shù)據(jù)。

雙向鏈表的可以是環(huán)形的，也可以不是環(huán)形的，如果是環(huán)形的話，那么最后一個(gè)節(jié)點(diǎn)的一個(gè)指針將指向鏈表頭，鏈表頭的一個(gè)指針將指向最后一個(gè)節(jié)點(diǎn)；如果不是環(huán)形的話，那么最后一個(gè)節(jié)點(diǎn)的一個(gè)指針和鏈表頭的一個(gè)指針都將指向None。

我在這里實(shí)現(xiàn)的是一個(gè)環(huán)形的雙向鏈表，這樣我就可以從鏈表頭開始，從兩個(gè)方向中任意選擇一個(gè)方向來(lái)進(jìn)行操作。

我在這里主要實(shí)現(xiàn)了環(huán)形雙向鏈表的：雙向新增，雙向遍歷，雙向插入，雙向刪除。

如圖為雙向環(huán)形鏈表示意圖，每一個(gè)節(jié)點(diǎn)都被兩個(gè)指針?biāo)赶颍瑫r(shí)每個(gè)節(jié)點(diǎn)也指向了兩個(gè)節(jié)點(diǎn)。

實(shí)現(xiàn)代碼如下：

class Player:
? ? """節(jié)點(diǎn)類"""
? ? def __init__(self):
? ? ? ? """初始化姓名，分?jǐn)?shù)，指針"""
? ? ? ? self.name = ''
? ? ? ? self.score = 0
? ? ? ? self.rlink = None
? ? ? ? self.llink = None
?
?
def ergodic(head, num=None, is_print=False, left=False):
? ? """遍歷函數(shù)，num是遍歷到哪一個(gè)位置序號(hào)，is_print是否觸發(fā)打印方法，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 ?# 返回遍歷完成后的最后一個(gè)節(jié)點(diǎn)
?
?
head = Player() ?# 初始化一個(gè)鏈表頭指針，不用來(lái)存放任何數(shù)據(jù)
head.rlink = head ?# 初始化右指針
head.llink = head ?# 初始化左指針
?
?
while True:
? ? select = input("(1).新增 ? (2).查看 ? (3).插入 ? (4).刪除 ? (5).離開\n輸入：")
? ? if select == "1": ?# 新增節(jié)點(diǎn)，分為右新增和左新增
? ? ? ? direction = input("(1).右新增 ? (2).左新增\n輸入：")
? ? ? ? if direction not in ("1", "2"):
? ? ? ? ? ? print("輸入錯(cuò)誤")
? ? ? ? ? ? continue
? ? ? ? new_data = Player()
? ? ? ? new_data.name = input("姓名：")
? ? ? ? new_data.score = input("分?jǐn)?shù)：")
? ? ? ? if direction == "1": ?# 右新增
? ? ? ? ? ? ptr = ergodic(head) ?# 從head開始向右遍歷獲取最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ptr.rlink = new_data
? ? ? ? ? ? new_data.llink = ptr
? ? ? ? ? ? new_data.rlink = head
? ? ? ? ? ? head.llink = new_data
? ? ? ? else: ?# 左新增
? ? ? ? ? ? ptr = ergodic(head, left=True) ?# 從head開始向左遍歷獲取最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ptr.llink = new_data
? ? ? ? ? ? new_data.rlink = ptr
? ? ? ? ? ? new_data.llink = head
? ? ? ? ? ? head.rlink = new_data
?
? ? elif select == "2": ?# 遍歷查看所有節(jié)點(diǎn)，分為右遍歷和左遍歷
? ? ? ? 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("輸入錯(cuò)誤")
?
? ? elif select == '3': ?# 插入節(jié)點(diǎn)，分為右插入和左插入
? ? ? ? direction = input("(1).右插入 ? (2).左插入\n輸入：")
? ? ? ? if direction not in ("1", "2"):
? ? ? ? ? ? print("輸入錯(cuò)誤")
? ? ? ? ? ? continue
? ? ? ? try:
? ? ? ? ? ? num = int(input("請(qǐng)輸入需要插入的節(jié)點(diǎn)位置序號(hào)：")) ?# 輸入序號(hào)必須是大于0的正整數(shù)，如果輸入大于最后一個(gè)節(jié)點(diǎn)的序號(hào)則插入到最后一個(gè)節(jié)點(diǎn)之后
? ? ? ? ? ? if num < 1:
? ? ? ? ? ? ? ? print("輸入必須為大于0的正整數(shù)")
? ? ? ? ? ? ? ? continue
? ? ? ? except ValueError:
? ? ? ? ? ? print("輸入有誤")
? ? ? ? ? ? continue
? ? ? ? insert_data = Player()
? ? ? ? insert_data.name = input("姓名：")
? ? ? ? insert_data.score = input("分?jǐn)?shù)：")
? ? ? ? if direction == "1": ?# 右插入
? ? ? ? ? ? ptr = ergodic(head, num - 1) ?# 獲取需要插入位置的前一個(gè)節(jié)點(diǎn)，新插入的節(jié)點(diǎn)就在這個(gè)節(jié)點(diǎn)的后面
? ? ? ? ? ? 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': ?# 刪除節(jié)點(diǎn)，分為右刪除和左刪除
? ? ? ? direction = input("(1).右刪除 ? (2).左刪除\n輸入：")
? ? ? ? if direction not in ("1", "2"):
? ? ? ? ? ? print("輸入錯(cuò)誤")
? ? ? ? ? ? continue
? ? ? ? try:
? ? ? ? ? ? num = int(input("請(qǐng)輸入需要?jiǎng)h除的節(jié)點(diǎn)位置序號(hào)：")) ?# 輸入序號(hào)必須是大于0的正整數(shù)，如果輸入大于最后一個(gè)節(jié)點(diǎn)的序號(hào)則刪除最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? if num < 1:
? ? ? ? ? ? ? ? print("輸入必須為大于0的正整數(shù)")
? ? ? ? ? ? ? ? continue
? ? ? ? except ValueError:
? ? ? ? ? ? print("輸入有誤")
? ? ? ? ? ? continue
? ? ? ? if direction == "1": ?# 右刪除
? ? ? ? ? ? ptr = ergodic(head, num) ?# 獲取需要?jiǎng)h除的節(jié)點(diǎn)
? ? ? ? else: ?# 左刪除
? ? ? ? ? ? ptr = ergodic(head, num, left=True)
? ? ? ? ptr.llink.rlink = ptr.rlink
? ? ? ? ptr.rlink.llink = ptr.llink
?
? ? elif select == '5':
? ? ? ? print("成功離開")
? ? ? ? break
? ? else:
? ? ? ? print("輸入錯(cuò)誤，請(qǐng)重試")

部分運(yùn)行效果如下：