Python數(shù)據(jù)結構之雙向鏈表詳解
0. 學習目標
單鏈表只有一個指向直接后繼的指針來表示結點間的邏輯關系，因此可以方便的從任一結點開始查找其后繼結點，但要找前驅(qū)結點則比較困難，雙向鏈表是為了解決這一問題，其使用兩個指針表示結點間的邏輯關系。在上一節(jié)中我們已經(jīng)討論了單鏈表及其相關操作的實現(xiàn)，本節(jié)中我們將重點討論雙向鏈表及其相關操作的實現(xiàn)。
通過本節(jié)學習，應掌握以下內(nèi)容：
雙向鏈表的基本概念及其優(yōu)缺點
雙向鏈表基本操作的實現(xiàn)
利用雙向鏈表的基本操作實現(xiàn)復雜算法
1. 雙向鏈表簡介
1.1 雙向鏈表介紹
雙向鏈表 (doubly linked list) 與單鏈表相似，同樣使用結點和指針的相關概念，屬于順序表的鏈式存儲結構，單鏈表和雙向鏈表的唯一區(qū)別在于雙向鏈表是用兩個指針表示結點間的邏輯關系，增加了一個指向其直接前驅(qū)的指針域，這樣形成的鏈表有兩條不同方向的鏈——前驅(qū)鏈和后繼鏈，因此稱為雙向鏈表，或稱為雙鏈表。
1.2 雙向鏈表結點類
在雙向鏈表中，根據(jù)已知結點查找其直接前驅(qū)結點可以與查找其直接后繼結點一樣方便。與單鏈表相同，雙向鏈表同樣可以分為帶有頭結點和不帶頭結點兩類，本節(jié)僅討論帶頭結點的雙向鏈表。雙向鏈表的結點示意圖如下所示，每個結點都有兩個指針——指向直接后繼的指針 next 和指向直接前驅(qū)的指針 previous：
用 Python 實現(xiàn)雙向鏈表結點類如下：
class Node: ? ? def __init__(self, data=None): ? ? ? ? self.data = data ? ? ? ? self.next = None ? ? ? ? self.previous = None ? ? def __str__(self): ? ? ? ? return str(self.data)
previous 變量指向直接前驅(qū)結點，而 next 變量保留對直接后繼結點的引用，而 data 變量用于存儲數(shù)據(jù)，重載 __str__ 方法用于便于打印結點對象。
1.3 雙向鏈表優(yōu)缺點
雙向鏈表的優(yōu)點在于給定雙向鏈表中的一個節(jié)點，我們可以雙向遍歷，直接訪問它的前驅(qū)結點，這樣在需要查找前驅(qū)的操作中，就不必再從頭開始遍歷整個鏈表，極大的方便了諸如刪除結點等操作。
而雙向鏈表的主要缺點如下：
- 每個結點需要一個額外的前驅(qū)指針，需要更多的空間；
- 結點的插入或刪除需要更多的指針修改操作。
2. 雙向鏈表實現(xiàn)
類似于單鏈表，接下來讓我們實現(xiàn)一個帶有頭結點的雙鏈表類，并用頭指針標識鏈表的開頭，如果你還不了解單鏈表，可以參考《單鏈表及其操作實現(xiàn)》相關介紹。
2.1 雙向鏈表的初始化
雙向鏈表的初始化建立一個空的帶頭結點的單鏈表，其表長 length 初始化為 0，此時鏈表中沒有元素結點，只有一個頭結點：
class DoublyLinkedList:
def __init__(self, data=None):
self.length = 0
# 初始化頭結點
head_node = Node()
self.head = head_node
創(chuàng)建雙向鏈表 DoublyLinkedList 對象的時間復雜度為O(1)。
NOTE：如果你還記得繼承機制的話，我們也可以令 DoublyLinkedList 繼承自在《單鏈表及其操作實現(xiàn)》中實現(xiàn)的 SinglyLinkedList，可以極大的化簡雙向鏈表的實現(xiàn)。
2.2 獲取雙向鏈表長度
求取雙向鏈表長度只需要重載 __len__ 從對象返回 length 的值，因此時間復雜度為O(1)：
def __len__(self):
return self.length
2.3 讀取指定位置元素
雙向鏈表中讀取指定位置元素的算法與單鏈表完全相同，只需要使用后繼鏈訪問每一個結點即可，因此操作的復雜度同樣為O(n)，接下來我們將重載 __getitem__ 操作實現(xiàn)讀取鏈表指定位置元素的操作；同時，我們希望確保索引在可接受的索引范圍內(nèi)，否則將引發(fā) IndexError 異常：
def __getitem__(self, index):
if index > self.length - 1 or index < 0:
raise IndexError("DoublyLinkedList assignment index out of range")
else:
count = -1
current = self.head
while count < index:
current = current.next
count += 1
return current.data
類似的，我們也可以實現(xiàn)修改指定位置元素的操作，只需要重載 __setitem__ 操作，其復雜度同樣為O(n)：
? def __setitem__(self, index, value):
? ? ? ? if index > self.length - 1 or index < 0:
? ? ? ? ? ? raise IndexError("DoublyLinkedList assignment index out of range")
? ? ? ? else:
? ? ? ? ? ? count = -1
? ? ? ? ? ? current = self.head
? ? ? ? ? ? while count < index:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? current.data = value2.4 查找指定元素
與單鏈表相同，當查找指定元素時，需要設置一個跟蹤鏈表結點的指針 current，令其順著 next 域依次指向每個結點，每指向一個結點就判斷其值是否等于指定值 value，若是則返回該結點索引；否則繼續(xù)往后搜索，如果鏈表中無此元素，則引發(fā) ValueError 異常，其時間復雜度為O(n)：
def locate(self, value):
count = -1
current = self.head
while current != None and current.data != value:
count += 1
current = current.next
if current and current.data == value:
return count
else:
raise ValueError("{} is not in sequential list".format(value))
2.5 在指定位置插入新元素
在指定位置插入新元素有兩種不同的方法，一種是找到待插入位置的結點 current，然后將待插結點插入 current 之前；另一種方法是找到待插入位置結點的前驅(qū)結點 prev，然后待插結點插入 prev 之后，兩種方法的操作略有不同，這里以第二種方法的操作為例，第一種方法的具體操作留給大家進行推導。
由于 prev 指向待插入位置的后繼結點，因此如果插入位置為列表末尾，由于 prev.next = None，無法使用 prev.next.previous，而在鏈表中間部位 prev.next.previous = prev，所以顯然插入鏈表中間位置和鏈表末尾的操作有所不同。
(1) 在雙向鏈表的末尾插入一個結點步驟如下：
- 遍歷列表直到最后一個結點，創(chuàng)建新結點；
- 將新節(jié)點的 previous 指針指向鏈表的最后一個結點；
- 更新原鏈表最后一個結點的 next 指針指向新結點。
(2) 在雙鏈表中間插入結點與單鏈表類似，但是需要更多的步驟用于修改指針：
- 首先遍歷鏈表到插入位置的前驅(qū)結點 prev，創(chuàng)建新結點；
- 新結點的 next 指針指向要插入新結點位置的下一個節(jié)點，新結點的 previous 指針指向 prev；
- 插入位置后繼節(jié)點的 previous 指向新節(jié)點，prev 結點的 next 指針指向新節(jié)點。
算法實現(xiàn)如下所示：
def insert(self, index, data):
count = 0
prev = self.head
# 判斷插入位置的合法性
if index > self.length or index < 0:
raise IndexError("DoublyLinkedList assignment index out of range")
else:
new_node = Node(data)
while count < index:
prev = prev.next
count += 1
new_node.previous = prev
self.length += 1
if prev.next:
# 鏈表中間插入結點
new_node.next = prev.next
prev.next.previous = new_node
prev.next = new_node
else:
# 鏈尾插入結點
prev.next = new_node
2.6 刪除指定位置元素
刪除指定位置元素，只需要找到相應位置結點 current，修改指針后，刪除結點即可。需要注意的是，除了需要將 current 的前驅(qū)結點的 next 指針指向 current 的后繼節(jié)點外，如果刪除的并非鏈尾元素，還需要將 current 的后繼節(jié)點的 previous 指針指向 current 的前驅(qū)結點：
算法實現(xiàn)如下所示：
def get_node(self, index):
"""輔助函數(shù)，用于根據(jù)位置返回結點"""
if index > self.length - 1 or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
count = -1
current = self.head
while count < index:
current = current.next
count += 1
return current
def __delitem__(self, index):
"""刪除指定位置元素"""
if index > self.length - 1 or index < 0:
raise IndexError("SinglyLinkedList assignment index out of range")
else:
current = self.get_node(index)
if current:
current.previous.next = current.next
# 如果刪除的并非最后一個結點
if current.next:
current.next.previous = current.previous
self.length -= 1
del current
在插入和刪除操作中，都是先確定操作位置，然后再進行插入和刪除操作，所以其時間復雜度均為O(n)。
2.7 其它一些有用的操作
2.7.1 鏈表元素輸出操作
將雙向鏈表轉換為字符串以便進行打印，使用 str 函數(shù)調(diào)用對象上的 __str__ 方法可以創(chuàng)建適合打印的字符串表示：
def __str__(self):
s = "["
current = self.head.next
count = 0
while current != None:
count += 1
s += str(current)
current = current.next
if count < self.length:
s += '<-->'
s += "]"
return s
2.7.2 刪除指定元素
與刪除指定位置元素略有不同，刪除指定元素需要在鏈表中刪除第一個具有與給定值相同數(shù)據(jù)元素的結點，但修改指針的操作是類似的，其時間復雜度同樣為O(n)：
def del_value(self, value):
current = self.head
while current:
if current.data == value:
current.previous.next = current.next
if current.next:
current.next.previous = current.previous
self.length -= 1
del current
return
else:
current = current.next
raise ValueError("The value provided is not present!")
2.7.3 在鏈表尾部追加新元素
為了方便的在鏈表尾部追加新元素，可以實現(xiàn)函數(shù) append：
def append(self, data):
new_node = Node(data)
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.previous = current
self.length += 1
此算法的時間復雜度為O(n)，如果需要經(jīng)常在鏈表尾部追加新元素，可以使用增加尾指針 tail 用于追蹤鏈表的最后一個元素，利用尾指針在鏈表尾部追加新元素時間復雜度可以降至O(1)。
3. 雙向鏈表應用
接下來，我們首先測試上述實現(xiàn)的雙向鏈表，以驗證操作的有效性，然后利用實現(xiàn)的基本操作來實現(xiàn)更復雜的算法。
3.1 雙向鏈表應用示例
首先初始化一個鏈表 dllist，并在其中追加若干元素：
dllist = DoublyLinkedList()
# 在鏈表末尾追加元素
dllist.append('apple')
dllist.append('banana')
dllist.append('orange')
# 在指定位置插入元素
dllist.insert(0, 'grape')
dllist.insert(4, 'lemon')
我們可以直接打印鏈表中的數(shù)據(jù)元素、鏈表長度等信息：
print('雙向鏈表 sllist 為：', dllist)
print('雙向鏈表 sllist 長度為：', len(dllist))
print('雙向鏈表 sllist 第0個元素為：', dllist[0])
# 修改數(shù)據(jù)元素
dllist[0] = 'pear'
del(dllist[3])
print('雙向修改鏈表 sllist 數(shù)據(jù)后：', dllist)
以上代碼輸出如下：
雙向鏈表 dllist 為： [grape<-->apple<-->banana<-->orange<-->lemon]
雙向鏈表 dllist 長度為： 5
雙向鏈表 dllist 第0個元素為： grape
修改雙向鏈表 dllist 數(shù)據(jù)后： [pear<-->apple<-->banana<-->lemon]
接下來，我們將演示在指定位置添加/刪除元素、以及如何查找指定元素等：
# 修改數(shù)據(jù)元素
dllist[0] = 'pear'
print('修改雙向鏈表 dllist 數(shù)據(jù)后：', dllist)
dllist.insert(0, 'watermelon')
print('在位置 0 添加 watermelon 后雙向鏈表鏈表 ddlist 數(shù)據(jù)：', dllist)
del(dllist[3])
print('刪除位置 3 處元素后雙向鏈表 ddlist 數(shù)據(jù)：', dllist)
dllist.append('lemon')
print('在尾部追加元素 lemon 后雙向鏈表 ddlist 數(shù)據(jù)：', dllist)
dllist.del_value('lemon')
print('刪除 lemon 后雙向鏈表 dllist 數(shù)據(jù)：', dllist)
print('watermelon 在雙向鏈表 dllist 中的索引為：', dllist.locate('orange'))
以上代碼輸出如下：
修改雙向鏈表 dllist 數(shù)據(jù)后： [pear<-->apple<-->banana<-->orange<-->lemon]
在位置 0 添加 watermelon 后雙向鏈表鏈表 ddlist 數(shù)據(jù)： [watermelon<-->pear<-->apple<-->banana<-->orange<-->lemon]
刪除位置 3 后雙向鏈表 ddlist 數(shù)據(jù)： [watermelon<-->pear<-->apple<-->orange<-->lemon]
在尾部追加元素 lemon 后雙向鏈表 ddlist 數(shù)據(jù)： [watermelon<-->pear<-->apple<-->orange<-->lemon<-->lemon]
刪除 lemon 后雙向鏈表 dllist 數(shù)據(jù)： [watermelon<-->pear<-->apple<-->orange<-->lemon]
watermelon 在雙向鏈表 dllist 中的索引為： 3
3.2 利用雙向鏈表基本操作實現(xiàn)復雜操作
[1] 利用雙向鏈表的基本操作，合并兩個雙向鏈表：
def merge(dllist1, dllist2):
current = dllist1.head
while current.next:
current = current.next
if dllist2.head.next:
tmp = dllist2.head.next
current.next = tmp
tmp.previous = current
dllist1.length += len(dllist2)
return dllist1
# 算法測試
dllist1 = DoublyLinkedList()
dllist2 = DoublyLinkedList()
for i in range(5):
dllist1.append(i)
dllist2.append((i+1)*5)
print('雙向鏈表 dllist1：', dllist1)
print('雙向鏈表 dllist2：', dllist2)
dllist = merge(dllist1, dllist2)
print('鏈表合并結果：', dllist)
程序輸出結果如下：
雙向鏈表 dllist1： [0<-->1<-->2<-->3<-->4]
雙向鏈表 dllist2： [5<-->10<-->15<-->20<-->25]
鏈表合并結果： [0<-->1<-->2<-->3<-->4<-->5<-->10<-->15<-->20<-->25]
到此這篇關于Python數(shù)據(jù)結構之雙向鏈表詳解的文章就介紹到這了,更多相關Python雙向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了利用python做數(shù)據(jù)擬合，下面文章圍繞如何讓利用python做數(shù)據(jù)擬合的相關資料展開詳細內(nèi)容,需要的朋友可以參考一下，希望對大家有所幫助2021-11-11
這篇文章主要為大家介紹了python全局變量,局部變量和命名空間，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
Python面試之os.system()和os.popen()的區(qū)別詳析
Python調(diào)用Shell,有兩種方法:os.system(cmd)或os.popen(cmd)腳本執(zhí)行過程中的輸出內(nèi)容,下面這篇文章主要給大家介紹了關于Python面試之os.system()和os.popen()區(qū)別的相關資料,需要的朋友可以參考下2022-06-06
EasyOCR?是?PyTorch?實現(xiàn)的一個光學字符識別?(OCR)?工具，這篇文章主要介紹了Python如何使用EasyOCR工具識別圖像文本,需要的朋友可以參考下2023-04-04
這篇文章主要介紹了基于Python 函數(shù)和方法的區(qū)別說明，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
Win10搭建Pyspark2.4.4+Pycharm開發(fā)環(huán)境的圖文教程(親測)
本文主要介紹了Win10搭建Pyspark2.4.4+Pycharm開發(fā)環(huán)境的圖文教程(親測)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-02-02
這篇文章主要介紹了Python可視化神器pyecharts繪制雷達圖，雷達圖是以從同一點開始的軸上表示的三個或更多個定量變量的二維圖表的形式顯示多變量數(shù)據(jù)的圖形方法2022-07-07
在本篇文章里小編給大家整理的是一篇關于python如何建立web服務的相關知識點內(nèi)容，有需要的朋友們可以參考下。2021-04-04
這篇文章主要為大家介紹了Python dict的使用誤區(qū)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
python使用pywinauto驅(qū)動微信客戶端實現(xiàn)公眾號爬蟲
這個項目是通過pywinauto控制windows(win10)上的微信PC客戶端來實現(xiàn)公眾號文章的抓取。代碼分成server和client兩部分。server接收client抓取的微信公眾號文章，并且保存到數(shù)據(jù)庫。另外server支持簡單的搜索和導出功能。client通過pywinauto實現(xiàn)微信公眾號文章的抓取。2021-05-05