網站首頁 編程語言 正文
0. 學習目標
單鏈表只有一個指向直接后繼的指針來表示結點間的邏輯關系,因此可以方便的從任一結點開始查找其后繼結點,但要找前驅結點則比較困難,雙向鏈表是為了解決這一問題,其使用兩個指針表示結點間的邏輯關系。在上一節中我們已經討論了單鏈表及其相關操作的實現,本節中我們將重點討論雙向鏈表及其相關操作的實現。
通過本節學習,應掌握以下內容:
雙向鏈表的基本概念及其優缺點
雙向鏈表基本操作的實現
利用雙向鏈表的基本操作實現復雜算法
1. 雙向鏈表簡介
1.1 雙向鏈表介紹
雙向鏈表 (doubly linked list) 與單鏈表相似,同樣使用結點和指針的相關概念,屬于順序表的鏈式存儲結構,單鏈表和雙向鏈表的唯一區別在于雙向鏈表是用兩個指針表示結點間的邏輯關系,增加了一個指向其直接前驅的指針域,這樣形成的鏈表有兩條不同方向的鏈——前驅鏈和后繼鏈,因此稱為雙向鏈表,或稱為雙鏈表。
1.2 雙向鏈表結點類
在雙向鏈表中,根據已知結點查找其直接前驅結點可以與查找其直接后繼結點一樣方便。與單鏈表相同,雙向鏈表同樣可以分為帶有頭結點和不帶頭結點兩類,本節僅討論帶頭結點的雙向鏈表。雙向鏈表的結點示意圖如下所示,每個結點都有兩個指針——指向直接后繼的指針 next 和指向直接前驅的指針 previous:
用 Python 實現雙向鏈表結點類如下:
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 變量用于存儲數據,重載 __str__ 方法用于便于打印結點對象。
1.3 雙向鏈表優缺點
雙向鏈表的優點在于給定雙向鏈表中的一個節點,我們可以雙向遍歷,直接訪問它的前驅結點,這樣在需要查找前驅的操作中,就不必再從頭開始遍歷整個鏈表,極大的方便了諸如刪除結點等操作。
而雙向鏈表的主要缺點如下:
- 每個結點需要一個額外的前驅指針,需要更多的空間;
- 結點的插入或刪除需要更多的指針修改操作。
2. 雙向鏈表實現
類似于單鏈表,接下來讓我們實現一個帶有頭結點的雙鏈表類,并用頭指針標識鏈表的開頭,如果你還不了解單鏈表,可以參考《單鏈表及其操作實現》相關介紹。
2.1 雙向鏈表的初始化
雙向鏈表的初始化建立一個空的帶頭結點的單鏈表,其表長 length 初始化為 0,此時鏈表中沒有元素結點,只有一個頭結點:
class DoublyLinkedList: def __init__(self, data=None): self.length = 0 # 初始化頭結點 head_node = Node() self.head = head_node
創建雙向鏈表 DoublyLinkedList 對象的時間復雜度為O(1)。
NOTE:如果你還記得繼承機制的話,我們也可以令 DoublyLinkedList 繼承自在《單鏈表及其操作實現》中實現的 SinglyLinkedList,可以極大的化簡雙向鏈表的實現。
2.2 獲取雙向鏈表長度
求取雙向鏈表長度只需要重載 __len__ 從對象返回 length 的值,因此時間復雜度為O(1):
def __len__(self): return self.length
2.3 讀取指定位置元素
雙向鏈表中讀取指定位置元素的算法與單鏈表完全相同,只需要使用后繼鏈訪問每一個結點即可,因此操作的復雜度同樣為O(n),接下來我們將重載 __getitem__ 操作實現讀取鏈表指定位置元素的操作;同時,我們希望確保索引在可接受的索引范圍內,否則將引發 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
類似的,我們也可以實現修改指定位置元素的操作,只需要重載 __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 = value
2.4 查找指定元素
與單鏈表相同,當查找指定元素時,需要設置一個跟蹤鏈表結點的指針 current,令其順著 next 域依次指向每個結點,每指向一個結點就判斷其值是否等于指定值 value,若是則返回該結點索引;否則繼續往后搜索,如果鏈表中無此元素,則引發 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) 在雙向鏈表的末尾插入一個結點步驟如下:
- 遍歷列表直到最后一個結點,創建新結點;
- 將新節點的 previous 指針指向鏈表的最后一個結點;
- 更新原鏈表最后一個結點的 next 指針指向新結點。
(2) 在雙鏈表中間插入結點與單鏈表類似,但是需要更多的步驟用于修改指針:
- 首先遍歷鏈表到插入位置的前驅結點 prev,創建新結點;
- 新結點的 next 指針指向要插入新結點位置的下一個節點,新結點的 previous 指針指向 prev;
- 插入位置后繼節點的 previous 指向新節點,prev 結點的 next 指針指向新節點。
算法實現如下所示:
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 的后繼節點外,如果刪除的并非鏈尾元素,還需要將 current 的后繼節點的 previous 指針指向 current 的前驅結點:
算法實現如下所示:
def get_node(self, index): """輔助函數,用于根據位置返回結點""" 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 函數調用對象上的 __str__ 方法可以創建適合打印的字符串表示:
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 刪除指定元素
與刪除指定位置元素略有不同,刪除指定元素需要在鏈表中刪除第一個具有與給定值相同數據元素的結點,但修改指針的操作是類似的,其時間復雜度同樣為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 在鏈表尾部追加新元素
為了方便的在鏈表尾部追加新元素,可以實現函數 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),如果需要經常在鏈表尾部追加新元素,可以使用增加尾指針 tail 用于追蹤鏈表的最后一個元素,利用尾指針在鏈表尾部追加新元素時間復雜度可以降至O(1)。
3. 雙向鏈表應用
接下來,我們首先測試上述實現的雙向鏈表,以驗證操作的有效性,然后利用實現的基本操作來實現更復雜的算法。
3.1 雙向鏈表應用示例
首先初始化一個鏈表 dllist,并在其中追加若干元素:
dllist = DoublyLinkedList() # 在鏈表末尾追加元素 dllist.append('apple') dllist.append('banana') dllist.append('orange') # 在指定位置插入元素 dllist.insert(0, 'grape') dllist.insert(4, 'lemon')
我們可以直接打印鏈表中的數據元素、鏈表長度等信息:
print('雙向鏈表 sllist 為:', dllist) print('雙向鏈表 sllist 長度為:', len(dllist)) print('雙向鏈表 sllist 第0個元素為:', dllist[0]) # 修改數據元素 dllist[0] = 'pear' del(dllist[3]) print('雙向修改鏈表 sllist 數據后:', dllist)
以上代碼輸出如下:
雙向鏈表 dllist 為: [grape<-->apple<-->banana<-->orange<-->lemon]
雙向鏈表 dllist 長度為: 5
雙向鏈表 dllist 第0個元素為: grape
修改雙向鏈表 dllist 數據后: [pear<-->apple<-->banana<-->lemon]
接下來,我們將演示在指定位置添加/刪除元素、以及如何查找指定元素等:
# 修改數據元素 dllist[0] = 'pear' print('修改雙向鏈表 dllist 數據后:', dllist) dllist.insert(0, 'watermelon') print('在位置 0 添加 watermelon 后雙向鏈表鏈表 ddlist 數據:', dllist) del(dllist[3]) print('刪除位置 3 處元素后雙向鏈表 ddlist 數據:', dllist) dllist.append('lemon') print('在尾部追加元素 lemon 后雙向鏈表 ddlist 數據:', dllist) dllist.del_value('lemon') print('刪除 lemon 后雙向鏈表 dllist 數據:', dllist) print('watermelon 在雙向鏈表 dllist 中的索引為:', dllist.locate('orange'))
以上代碼輸出如下:
修改雙向鏈表 dllist 數據后: [pear<-->apple<-->banana<-->orange<-->lemon]
在位置 0 添加 watermelon 后雙向鏈表鏈表 ddlist 數據: [watermelon<-->pear<-->apple<-->banana<-->orange<-->lemon]
刪除位置 3 后雙向鏈表 ddlist 數據: [watermelon<-->pear<-->apple<-->orange<-->lemon]
在尾部追加元素 lemon 后雙向鏈表 ddlist 數據: [watermelon<-->pear<-->apple<-->orange<-->lemon<-->lemon]
刪除 lemon 后雙向鏈表 dllist 數據: [watermelon<-->pear<-->apple<-->orange<-->lemon]
watermelon 在雙向鏈表 dllist 中的索引為: 3
3.2 利用雙向鏈表基本操作實現復雜操作
[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]
原文鏈接:https://blog.csdn.net/LOVEmy134611/article/details/120200096
相關推薦
- 2022-05-12 正則判斷只能輸入大于0的正整數
- 2022-07-20 C語言詳細講解while語句的用法_C 語言
- 2022-05-21 Python實現歸一化算法詳情_python
- 2022-04-18 antd4.*表格 Each child in a list should have a uniqu
- 2022-06-09 FreeRTOS實時操作系統的任務通知方法_操作系統
- 2022-04-23 一起來了解python的基本輸入和輸出_python
- 2022-08-30 詳解Python單元測試的兩種寫法_python
- 2022-04-28 C++中的友元函數與友元類詳情_C 語言
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支