Python數(shù)據(jù)結構之雙向鏈表詳解
0. 學習目標
單鏈表只有一個指向直接后繼的指針來表示結點間的邏輯關系，因此可以方便的從任一結點開始查找其后繼結點，但要找前驅結點則比較困難，雙向鏈表是為了解決這一問題，其使用兩個指針表示結點間的邏輯關系。在上一節(jié)中我們已經(jīng)討論了單鏈表及其相關操作的實現(xiàn)，本節(jié)中我們將重點討論雙向鏈表及其相關操作的實現(xiàn)。
通過本節(jié)學習，應掌握以下內(nèi)容：
雙向鏈表的基本概念及其優(yōu)缺點
雙向鏈表基本操作的實現(xiàn)
利用雙向鏈表的基本操作實現(xiàn)復雜算法
1. 雙向鏈表簡介
1.1 雙向鏈表介紹
雙向鏈表 (doubly linked list) 與單鏈表相似，同樣使用結點和指針的相關概念，屬于順序表的鏈式存儲結構，單鏈表和雙向鏈表的唯一區(qū)別在于雙向鏈表是用兩個指針表示結點間的邏輯關系，增加了一個指向其直接前驅的指針域，這樣形成的鏈表有兩條不同方向的鏈——前驅鏈和后繼鏈，因此稱為雙向鏈表，或稱為雙鏈表。
1.2 雙向鏈表結點類
在雙向鏈表中，根據(jù)已知結點查找其直接前驅結點可以與查找其直接后繼結點一樣方便。與單鏈表相同，雙向鏈表同樣可以分為帶有頭結點和不帶頭結點兩類，本節(jié)僅討論帶頭結點的雙向鏈表。雙向鏈表的結點示意圖如下所示，每個結點都有兩個指針——指向直接后繼的指針 next 和指向直接前驅的指針 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 變量指向直接前驅結點，而 next 變量保留對直接后繼結點的引用，而 data 變量用于存儲數(shù)據(jù)，重載 __str__ 方法用于便于打印結點對象。
1.3 雙向鏈表優(yōu)缺點
雙向鏈表的優(yōu)點在于給定雙向鏈表中的一個節(jié)點，我們可以雙向遍歷，直接訪問它的前驅結點，這樣在需要查找前驅的操作中，就不必再從頭開始遍歷整個鏈表，極大的方便了諸如刪除結點等操作。
而雙向鏈表的主要缺點如下：
- 每個結點需要一個額外的前驅指針，需要更多的空間；
- 結點的插入或刪除需要更多的指針修改操作。
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 之前；另一種方法是找到待插入位置結點的前驅結點 prev，然后待插結點插入 prev 之后，兩種方法的操作略有不同，這里以第二種方法的操作為例，第一種方法的具體操作留給大家進行推導。
由于 prev 指向待插入位置的后繼結點，因此如果插入位置為列表末尾，由于 prev.next = None，無法使用 prev.next.previous，而在鏈表中間部位 prev.next.previous = prev，所以顯然插入鏈表中間位置和鏈表末尾的操作有所不同。
(1) 在雙向鏈表的末尾插入一個結點步驟如下：
- 遍歷列表直到最后一個結點，創(chuàng)建新結點；
- 將新節(jié)點的 previous 指針指向鏈表的最后一個結點；
- 更新原鏈表最后一個結點的 next 指針指向新結點。
(2) 在雙鏈表中間插入結點與單鏈表類似，但是需要更多的步驟用于修改指針：
- 首先遍歷鏈表到插入位置的前驅結點 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 的前驅結點的 next 指針指向 current 的后繼節(jié)點外，如果刪除的并非鏈尾元素，還需要將 current 的后繼節(jié)點的 previous 指針指向 current 的前驅結點：
算法實現(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ù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Iconfont(矢量圖標)+iconmoon(圖標svg互轉)配合javascript實現(xiàn)社交分享系統(tǒng)
這篇文章主要介紹了Iconfont(矢量圖標)+iconmoon(圖標svg互轉)配合javascript實現(xiàn)社交分享系統(tǒng),本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-04-04
詳解pycharm2020.1.1專業(yè)版安裝指南(推薦)
這篇文章主要介紹了pycharm2020.1.1專業(yè)版安裝指南,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-08-08
今天小編就為大家分享一篇利用Python正則表達式過濾敏感詞的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01
Python辦公自動化之教你用Python批量識別發(fā)票并錄入到Excel表格中
今天來分享一篇辦公干貨文章,對于財務專業(yè)等學生或者公司財務人員來說,將報賬發(fā)票等匯總到excel簡直就是一個折磨.尤其是到年底的時候,公司的財務人員面對一大堆的發(fā)票簡直就是苦不堪言.正好我們學會了Python,我們應該將Python的優(yōu)勢發(fā)揮起來,需要的朋友可以參考下2021-06-06
Python實現(xiàn)將doc轉化pdf格式文檔的方法
這篇文章主要介紹了Python實現(xiàn)將doc轉化pdf格式文檔的方法,結合實例形式分析了Python實現(xiàn)doc格式文件讀取及轉換pdf格式文件的操作技巧,以及php調(diào)用py文件的具體實現(xiàn)方法,需要的朋友可以參考下2018-01-01
通常使用TOF等3d攝像頭采集的格式一般只是深度圖,下面這篇文章主要給大家介紹了關于如何基于Python深度圖生成3D點云的相關資料,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2022-12-12
這篇文章主要介紹了python求素數(shù)示例,打印出素數(shù)列表,需要的朋友可以參考下2014-02-02
今天來做一個最簡單的例子，利用寫一個最簡單的緩存系統(tǒng)，以key``value的方式保持數(shù)據(jù)，并且需要將內(nèi)容中的數(shù)據(jù)落地到文件，以便下次啟動的時候，將文件的內(nèi)容加載進內(nèi)存中來，感興趣的可以了解一下2023-04-04
Jupyter Notebook中%time和%timeit的使用詳解
本文主要介紹了Jupyter Notebook中%time和%timeit的使用詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-02-02
@用做函數(shù)的修飾符,可以在模塊或者類的定義層內(nèi)對函數(shù)進行修飾,下面這篇文章主要給大家介紹了關于python中?@?的含義以及基本使用的相關資料,需要的朋友可以參考下2021-12-12