Python數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表詳解

更新時間：2022年01月24日 15:18:07 作者：盼小輝丶

循環(huán)鏈表 (Circular Linked List) 是鏈?zhǔn)酱鎯Y(jié)構(gòu)的另一種形式，它將鏈表中最后一個結(jié)點的指針指向鏈表的頭結(jié)點，使整個鏈表頭尾相接形成一個環(huán)形，使鏈表的操作更加方便靈活。本文將詳細(xì)介紹一下循環(huán)鏈表的相關(guān)知識，需要的可以參考一下

0. 學(xué)習(xí)目標(biāo)

循環(huán)鏈表 (Circular Linked List) 是鏈?zhǔn)酱鎯Y(jié)構(gòu)的另一種形式，它將鏈表中最后一個結(jié)點的指針指向鏈表的頭結(jié)點，使整個鏈表頭尾相接形成一個環(huán)形，使鏈表的操作更加方便靈活。我們已經(jīng)介紹了單鏈表和雙向鏈表，本節(jié)中我們將基于單鏈表和雙向鏈表實現(xiàn)循環(huán)鏈表與循環(huán)雙鏈表以及它們的相關(guān)操作。
通過本節(jié)學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

循環(huán)鏈表的基本概念及其優(yōu)缺點

循環(huán)鏈表及其操作的實現(xiàn)

循環(huán)雙鏈表及其操作的實現(xiàn)

1. 循環(huán)鏈表簡介

在單鏈表/雙向鏈表中，最后一個結(jié)點的指針域為 None，訪問鏈表中任何數(shù)據(jù)只能從鏈表頭開始順序訪問，而不能進行任何位置的隨機查詢訪問，如果查詢的結(jié)點在鏈表的尾部也需遍歷整個鏈表。

循環(huán)鏈表是一種特殊的鏈表，在循環(huán)鏈表中，首尾端點相互連接，使整個鏈表頭尾相接形成一個環(huán)形，也就是說鏈表中的最后一個結(jié)點指向第一個結(jié)點；換句話說，在循環(huán)鏈表中所有結(jié)點都指向下一個結(jié)點，每一個結(jié)點都有一個后繼結(jié)點。

循環(huán)鏈表的優(yōu)點是，從鏈表中任一結(jié)點出發(fā)，順著指針鏈都可找到表中其它結(jié)點，因此沒有結(jié)點指向 None；同時并不會占用額外的存儲空間，僅僅是改變了最后一個結(jié)點的指針指向，就可以使操作更加方便靈活。

循環(huán)鏈表可以基于單鏈表和雙向鏈表，通?；趩捂湵淼难h(huán)鏈表稱為循環(huán)單鏈表，而基于雙向鏈表的循環(huán)鏈表稱為循環(huán)雙鏈表，兩種類型的循環(huán)鏈表示意圖如下所示：

NOTE：由于我們對于鏈表已經(jīng)非常熟悉了，因此對于鏈表中相似的操作只會進行簡要的介紹，我們的主要精力將放在具有差異的操作上。

2. 循環(huán)單鏈表實現(xiàn)

類似于單鏈表，接下來讓我們實現(xiàn)一個帶有頭結(jié)點的循環(huán)單鏈表類，并用頭指針標(biāo)識鏈表的開頭，如果你還不了解單鏈表，可以參考《單鏈表及其操作實現(xiàn)》相關(guān)介紹。

2.1 循環(huán)單鏈表的基本操作

循環(huán)單鏈表的基本操作大部分與單鏈表相同，只是循環(huán)遍歷是否完成的條件需要由 current == None 改為 current != head

2.1.1 循環(huán)單鏈表的初始化

初始化循環(huán)單鏈表函數(shù)中，創(chuàng)建的頭結(jié)點指針域 next 不為空，而是指向自身：

class CircularLinkedList:
    def __init__(self):
        head_node = Node()
        self.head = head_node
        head_node.next = head_node
        self.length = 0

2.1.2 獲取循環(huán)單鏈表長度

重載 __len__ 從對象返回 length 的值用于求取循環(huán)單鏈表長度：

    def __len__(self):
        return self.length

2.1.3 讀取指定位置元素

重載 __getitem__ 操作用于實現(xiàn)讀取鏈表指定位置元素的操作，類似的，我們也可以實現(xiàn)修改指定位置元素的操作，只需要重載 __setitem__ 操作，它們的時間復(fù)雜度均為O(n)：

def __getitem__(self, index):
? ? ? ? if index > self.length - 1 or index < 0:
? ? ? ? ? ? raise IndexError("CircularLinkedList assignment index out of range")
? ? ? ? else:
? ? ? ? ? ? count = -1
? ? ? ? ? ? current = self.head
? ? ? ? ? ? while count < index:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? return current.data
? ? def __setitem__(self, index, value):
? ? ? ? if index > self.length - 1 or index < 0:
? ? ? ? ? ? raise IndexError("CircularLinkedList assignment index out of range")
? ? ? ? else:
? ? ? ? ? ? count = -1
? ? ? ? ? ? current = self.head
? ? ? ? ? ? while count < index:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? ? ? count += 1

? ? ? ? ? ? current.data = value

我們可以發(fā)現(xiàn)，這兩個操作與單鏈表的操作完全相同。

2.1.4 查找指定元素

在循環(huán)單鏈表中查找指定元素的操作與單鏈表基本相同，使用 current 指針沿后繼鏈依次遍歷每個結(jié)點，并判斷其值是否等于指定值 value，若是則返回該結(jié)點索引，否則繼續(xù)往后搜索；只是循環(huán)遍歷是否完成的條件需要由 current == None 改為 current != head：

    def locate(self, value):
        count = 0
        current = self.head.next
        while current != self.head 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.1.5 在指定位置插入新元素

由于有 length 屬性的原因，我們可通過 length 判斷插入位置是否合法，因此在循環(huán)單鏈表中的指定位置插入新元素與在單鏈表指定位置插入新元素完全相同：

    def insert(self, index, data):
        count = -1
        current = self.head
        # 判斷插入位置的合法性
        if index > self.length or index < 0:
            raise IndexError("CircularLinkedList assignment index out of range")
        else:
            node = Node(data)
            while count < index:
                # 查找插入位置
                previous = current
                current = current.next
                count += 1
            # 插入新結(jié)點
            node.next = previous.next
            previous.next = node
            self.length += 1

2.1.6 刪除指定位置元素

要刪除鏈表中第i個結(jié)點，同樣首先找到刪除位置的前一個結(jié)點 previous，指針 current 指向要刪除的結(jié)點，將 previous 的指針域修改為待刪除結(jié)點 current 的后繼結(jié)點的地址，刪除后的結(jié)點需動態(tài)的釋放：

    def __delitem__(self, index):
        if index > self.length - 1 or index < 0:
            raise IndexError("CircularLinkedList assignment index out of range")
        else:
            count = -1
            previous = self.head
            while count < index - 1:
                previous = previous.next
                count += 1
            current = previous.next
            previous.next = current.next
            self.length -= 1
            del current

2.1.7 其它一些有用的操作

[1] 使用 str 函數(shù)調(diào)用對象上的 __str__ 方法可以創(chuàng)建適合打印的字符串表示：

     def __str__(self):
        head = self.head
        s = "["
        current = self.head.next
        count = 0
        while current != head:
            count += 1
            s += str(current)
            current = current.next
            if count < self.length:
                s += '-->'
        s += "]"
        return s

[2] 刪除指定元素，其時間復(fù)雜度與刪除指定位置元素相同，都為O(n)：

    def del_value(self, value):
        previous = self.head
        current = self.head.next
        while current != self.head:
            if current.data == value:
                previous.next = current.next
                self.length -= 1
                del current
                return
            else:
                previous = current
                current = current.next
        raise ValueError("The value provided is not present!")

[3] 為了方便的在鏈表尾部追加新元素，可以實現(xiàn)函數(shù) append：

    def append(self, value):
        node = Node(value)
        current = self.head.next
        while current.next != self.head:
            current = current.next
        node.next = current.next
        current.next = node
        self.length += 1

2.2 簡單的實現(xiàn)方法

從上述實現(xiàn)，我們可以看到，CircularLinkedList 類的代碼中大部分與 SinglyLinkedList 類完全相同，如果你對繼承機制還有印象的話，我們也可以令 CircularLinkedList 繼承自在《單鏈表及其操作實現(xiàn)》中實現(xiàn)的 SinglyLinkedList，簡化循環(huán)單鏈表的實現(xiàn)。

from SinglyLinkedList import SinglyLinkedList
class CircularLinkedList(SinglyLinkedList):
    """
    利用繼承機制僅需要實現(xiàn)循環(huán)單鏈表與單鏈表中不同的操作,僅需要重載父類中：
    __init__(), locate(), del_value(), __str__(), append() 函數(shù)即可
    相關(guān)代碼在上一小節(jié)已經(jīng)給出，這里不再贅述
    """
    pass

2.3 循環(huán)單鏈表應(yīng)用示例

接下來，我們將測試上述實現(xiàn)的循環(huán)單鏈表，以驗證操作的有效性。首先初始化一個鏈表 cllist，并在其中追加若干元素：

cllist = CircularLinkedList()
# 在循環(huán)單鏈表末尾追加元素
cllist.append('apple')
cllist.append('lemon')
# 在指定位置插入元素
cllist.insert(0, 'banana')
cllist.insert(2, 'orange')

我們可以直接打印鏈表中的數(shù)據(jù)元素、鏈表長度等信息：

print('循環(huán)單鏈表 cllist 數(shù)據(jù)為：', cllist)
print('循環(huán)單鏈表 cllist 長度為：', len(cllist))
print('循環(huán)單鏈表 cllist 第 0 個元素為：', cllist[0])
cllist[0] = 'pear'
print('修改循環(huán)單鏈表 cllist 后數(shù)據(jù)元素為：', cllist)

以上代碼輸出如下：

循環(huán)單鏈表 cllist 數(shù)據(jù)為： [banana-->apple-->orange-->lemon]
循環(huán)單鏈表 cllist 長度為： 4
循環(huán)單鏈表 cllist 第 0 個元素為： banana
修改循環(huán)單鏈表 cllist 后數(shù)據(jù)元素為： [pear-->apple-->orange-->lemon]

接下來，我們將演示在指定位置添加/刪除元素、以及如何查找指定元素等：

# 在指定位置添加/刪除結(jié)點
cllist.insert(1, 'grape')
print('在位置 1 添加 grape 后循環(huán)單鏈表 cllist 數(shù)據(jù)：', cllist)
del(cllist[2])
print('修改循環(huán)單鏈表 cllist 后數(shù)據(jù)：', cllist)
# 刪除指定元素
cllist.del_value('pear')
print('刪除 pear 后循環(huán)單鏈表 cllist 數(shù)據(jù)：', cllist)
cllist.append('watermelon')
print('添加 watermelon 后循環(huán)單鏈表 cllist 數(shù)據(jù)：', cllist)

以上代碼輸出如下：

在位置 1 添加 grape 后循環(huán)單鏈表 cllist 數(shù)據(jù)： [pear-->grape-->apple-->orange-->lemon]
修改循環(huán)單鏈表 cllist 后數(shù)據(jù)： [pear-->grape-->orange-->lemon]
刪除 pear 后循環(huán)單鏈表 cllist 數(shù)據(jù)： [grape-->orange-->lemon]
添加 watermelon 后循環(huán)單鏈表 cllist 數(shù)據(jù)： [grape-->orange-->lemon-->watermelon]

2.4 利用循環(huán)單鏈表基本操作實現(xiàn)復(fù)雜操作

[1] 將兩個循環(huán)單鏈表首尾相接進行合并，連接示例如下圖所示：

與單鏈表不同，循環(huán)單鏈表的連接不僅需要遍歷第一個鏈表找到最后一個結(jié)點連接到第二個鏈表上，還需要遍歷第二個鏈表，使第二個鏈表的尾結(jié)點的 next 指針指向第一個鏈表的頭結(jié)點，具體實現(xiàn)如下：

def merge(cllist1, cllist2):
    current = cllist1.head
    while current.next != cllist1.head:
        current = current.next
    # 若cllist2不為空，進行連接操作
    if cllist2.head.next != cllist2.head:
        current.next = cllist2.head.next
        current2 = cllist2.head.next
        while current2.next != cllist2.head:
            current2 = current2.next
        current2.next = cllist1.head
        cllist1.length += len(cllist2)
        return cllist1
# 算法測試
cllist1 = CircularLinkedList()
cllist2 = CircularLinkedList()
for i in range(5):
    cllist1.append(i)
    cllist2.append((i+1)*5)
print('循環(huán)單鏈表 cllist1：', cllist1)
print('循環(huán)單鏈表 cllist2：', cllist2)
result = merge(cllist1, cllist2)
print('循環(huán)鏈表連接結(jié)果：', result)

算法執(zhí)行結(jié)果如下：

循環(huán)單鏈表 cllist1： [0-->1-->2-->3-->4]
循環(huán)單鏈表 cllist2： [5-->10-->15-->20-->25]
循環(huán)單鏈表連接結(jié)果： [0-->1-->2-->3-->4-->5-->10-->15-->20-->25]

3. 循環(huán)雙鏈表實現(xiàn)

類似于雙向鏈表，接下來我們實現(xiàn)一個帶有頭結(jié)點的循環(huán)雙鏈表類，并用頭指針標(biāo)識鏈表的開頭，如果你還不了解雙向鏈表，可以參考《雙向鏈表及其操作實現(xiàn)》相關(guān)介紹。

3.1 循環(huán)雙鏈表的基本操作

由于循環(huán)雙鏈表類 DoubleLinkedCircularList 的代碼中大部分與雙向鏈表類 DoublyLinkedList 完全相同，因此我們借助繼承機制來簡化循環(huán)雙鏈表的實現(xiàn)，DoublyLinkedList 類的實現(xiàn)參考《雙向鏈表及其操作實現(xiàn)》。

from DoublyLinkedList import DoublyLinkedList

class Node:
? ? def __init__(self, data=None):
? ? ? ? self.data = data
? ? ? ? self.next = None
? ? ? ? self.previous = None

? ? def __str__(self):
? ? ? ? return str(self.data)

循環(huán)雙鏈表的初始化，不僅需要將頭結(jié)點的 next 指針指向自身外，previous 指針同樣需要指向自身：

class DoubleLinkedCircularList(DoublyLinkedList):
    def __init__(self, data=None):
        self.length = 0
        # 初始化頭結(jié)點
        head_node = Node() 
        self.head = head_node
        self.head.next = self.head
        self.head.previous = self.head

定位元素位置，同樣只需要修改遍歷完成條件即可：

    def locate(self, value):
        count = 0
        current = self.head.next
        while current != self.head 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))

相比于雙鏈表，循環(huán)雙鏈表的刪除和插入操作更加方便，由于其循環(huán)特性的原因，并不需要考慮所刪除或插入的結(jié)點是否是鏈表中的最后一個結(jié)點：

    def __delitem__(self, index):
        # 刪除指定位置結(jié)點
        if index > self.length - 1 or index < 0:
            raise IndexError("DoubleLinkedCircularList assignment index out of range")
        else:
            count = -1
            current = self.head
            while count < index:
                current = current.next
                count += 1
            current.previous.next = current.next
            current.next.previous = current.previous
            self.length -= 1
            del current
    
    def del_value(self, value):
        # 刪除鏈表中的指定元素
        current = self.head
        while current.next != self.head:
            if current.data == value:
                current.previous.next = current.next
                current.next.preious = current.previous
                self.length -= 1
                del current
                return
            else:
                current = current.next
        raise ValueError("The value provided is not present!")
    
    def insert(self, index, data):
        count = 0
        current = self.head
        # 判斷插入位置的合法性
        if index > self.length or index < 0:
            raise IndexError("DoubleLinkedCircularList assignment index out of range")
        else:
            new_node = Node(data)
            while count < index:
                current = current.next
                count += 1
            new_node.next = current.next
            current.next.previous = new_node
            new_node.previous = current
            current.next = new_node
            self.length += 1

由于繼承的緣故，并不需要在子類中重寫相同的操作(類如查找指定元素等)，最后我們重載一些其它有用的操作：

? def append(self, data):
? ? ? ? new_node = Node(data)
? ? ? ? current = self.head
? ? ? ? while current.next != self.head:
? ? ? ? ? ? current = current.next
? ? ? ? new_node.next = current.next
? ? ? ? current.next.previous = new_node
? ? ? ? new_node.previous = current
? ? ? ? current.next = new_node
? ? ? ? self.length += 1

? ? def __str__(self):
? ? ? ? head = self.head
? ? ? ? s = "["
? ? ? ? current = self.head.next
? ? ? ? count = 0
? ? ? ? while current != head:
? ? ? ? ? ? count += 1
? ? ? ? ? ? s += str(current)
? ? ? ? ? ? current = current.next
? ? ? ? ? ? if count < self.length:
? ? ? ? ? ? ? ? s += '<-->'
? ? ? ? s += "]"
? ? ? ? return s

3.2 循環(huán)雙鏈表應(yīng)用示例

接下來，我們測試上述實現(xiàn)的循環(huán)雙鏈表，以驗證操作的有效性：

dlclist = DoubleLinkedCircularList()
# 在鏈表末尾追加元素
dlclist.append('apple')
dlclist.append('lemon')
# 在指定位置插入元素
dlclist.insert(0, 'banana')
dlclist.insert(2, 'orange')
print('循環(huán)雙鏈表 dlclist 數(shù)據(jù)為：', dlclist)
print('循環(huán)雙鏈表 dlclist 長度為：', len(dlclist))
# 查找指定元素，這里就是調(diào)用父類的locate方法
print('apple 在 dlclist 中序號為：', dlclist.locate('apple'))
# 獲取指定位置元素
print('循環(huán)雙鏈表 dlclist 第 0 個元素為：', dlclist[0])
# 修改數(shù)據(jù)元素
dlclist[0] = 'pear'
print('修改循環(huán)雙鏈表 dlclist 后數(shù)據(jù)元素為：', dlclist)
del(dlclist[2])
print('修改循環(huán)雙鏈表 dlclist 后數(shù)據(jù)：', dlclist)
# 刪除指定元素
dlclist.del_value('pear')
print('刪除 pear 后循環(huán)雙鏈表 dlclist 數(shù)據(jù)：', dlclist)

上述程序輸出如下所示：

循環(huán)雙鏈表 dlclist 數(shù)據(jù)為： [banana<-->apple<-->orange<-->lemon]
循環(huán)雙鏈表 dlclist 長度為： 4
apple 在 dlclist 中序號為： 1
循環(huán)雙鏈表 dlclist 第 0 個元素為： banana
修改循環(huán)雙鏈表 dlclist 后數(shù)據(jù)元素為： [pear<-->apple<-->orange<-->lemon]
修改循環(huán)雙鏈表 dlclist 后數(shù)據(jù)： [pear<-->apple<-->lemon]
刪除 pear 后循環(huán)雙鏈表 dlclist 數(shù)據(jù)： [apple<-->lemon]

以上就是Python數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表詳解的詳細(xì)內(nèi)容，更多關(guān)于Python循環(huán)鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: