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

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

循環(huán)鏈表 (Circular Linked List) 是鏈式存儲結構的另一種形式，它將鏈表中最后一個結點的指針指向鏈表的頭結點，使整個鏈表頭尾相接形成一個環(huán)形，使鏈表的操作更加方便靈活。本文將詳細介紹一下循環(huán)鏈表的相關知識，需要的可以參考一下

0. 學習目標

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

初始化循環(huán)單鏈表函數(shù)中，創(chuàng)建的頭結點指針域 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__ 操作，它們的時間復雜度均為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 指針沿后繼鏈依次遍歷每個結點，并判斷其值是否等于指定值 value，若是則返回該結點索引，否則繼續(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
            # 插入新結點
            node.next = previous.next
            previous.next = node
            self.length += 1

2.1.6 刪除指定位置元素

要刪除鏈表中第i個結點，同樣首先找到刪除位置的前一個結點 previous，指針 current 指向要刪除的結點，將 previous 的指針域修改為待刪除結點 current 的后繼結點的地址，刪除后的結點需動態(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ù)調用對象上的 __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] 刪除指定元素，其時間復雜度與刪除指定位置元素相同，都為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ù)即可
    相關代碼在上一小節(jié)已經(jīng)給出，這里不再贅述
    """
    pass

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

接下來，我們將測試上述實現(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]

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

# 在指定位置添加/刪除結點
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)復雜操作

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

與單鏈表不同，循環(huán)單鏈表的連接不僅需要遍歷第一個鏈表找到最后一個結點連接到第二個鏈表上，還需要遍歷第二個鏈表，使第二個鏈表的尾結點的 next 指針指向第一個鏈表的頭結點，具體實現(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)鏈表連接結果：', result)

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

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

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

類似于雙向鏈表，接下來我們實現(xiàn)一個帶有頭結點的循環(huán)雙鏈表類，并用頭指針標識鏈表的開頭，如果你還不了解雙向鏈表，可以參考《雙向鏈表及其操作實現(xià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)雙鏈表的初始化，不僅需要將頭結點的 next 指針指向自身外，previous 指針同樣需要指向自身：

class DoubleLinkedCircularList(DoublyLinkedList):
    def __init__(self, data=None):
        self.length = 0
        # 初始化頭結點
        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)特性的原因，并不需要考慮所刪除或插入的結點是否是鏈表中的最后一個結點：

    def __delitem__(self, index):
        # 刪除指定位置結點
        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)雙鏈表應用示例

接下來，我們測試上述實現(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))
# 查找指定元素，這里就是調用父類的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ù)結構之循環(huán)鏈表詳解的詳細內容，更多關于Python循環(huán)鏈表的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

Django實現(xiàn)微信小程序支付的示例代碼
這篇文章主要介紹了Django實現(xiàn)微信小程序支付的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2020-09-09
Python學習之直方圖均衡化原理詳解
直方圖均衡化是以累計分布函數(shù)為核心，將原始圖像灰度直方圖從比較集中的某個灰度區(qū)間，非線性地映射為在全部灰度范圍內的較均勻分布，從而增強對比度。本文將為大家詳細講解直方圖均衡化的原理，需要的可以參考一下
2022-03-03
Python中的常用函數(shù)使用及說明
這篇文章主要介紹了Python中的常用函數(shù)使用及說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2024-02-02
Python循環(huán)語句之while循環(huán)和for循環(huán)詳解
在Python中,循環(huán)語句用于重復執(zhí)行一段代碼,直到滿足某個條件為止,在Python中,有兩種主要的循環(huán)語句：for循環(huán)和while循環(huán),本文就來給大家介紹一下這兩個循環(huán)的用法,需要的朋友可以參考下
2023-08-08
python tkinter實現(xiàn)鼠標懸停提示
這篇文章主要為大家詳細介紹了python如何使用tkinter控件實現(xiàn)鼠標懸停提示以及提示文本動態(tài)展示,文中的示例代碼講解詳細,有需要的可以參考下
2024-11-11
Python初學者必須掌握的25個內置函數(shù)詳解
這篇文章主要介紹了Python25個常用內置函數(shù)總結,本文羅列了數(shù)學相關、功能相關、類型轉換、字符串處理、序列處理函數(shù)等常用內置函數(shù),需要的朋友可以參考下
2021-09-09
Python初學者需要注意的事項小結(python2與python3)
這篇文章主要介紹了Python初學者需要注意的事項小結，包括了python2與python3的一些區(qū)別,需要的朋友可以參考下
2018-09-09
python?NetworkX庫生成并繪制帶權無向圖
這篇文章主要為大家介紹了python?NetworkX庫生成并繪制帶權無向圖的實現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-05-05
淺析Python中的多條件排序實現(xiàn)
Python中使用sort方法和sorted函數(shù)排序時關鍵就在于key參數(shù)值的編寫技巧,這里我們來舉兩個實例淺析Python中的多條件排序實現(xiàn):
2016-06-06
在numpy矩陣中令小于0的元素改為0的實例
今天小編就為大家分享一篇在numpy矩陣中令小于0的元素改為0的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-01-01