日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后,達者為師

網站首頁 編程語言 正文

Python數據結構之雙向鏈表詳解_python

作者:盼小輝丶 ? 更新時間: 2022-04-02 編程語言

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

欄目分類
最近更新