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

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

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

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

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

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

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

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

在單鏈表/雙向鏈表中，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)?None，訪問(wèn)鏈表中任何數(shù)據(jù)只能從鏈表頭開(kāi)始順序訪問(wèn)，而不能進(jìn)行任何位置的隨機(jī)查詢?cè)L問(wèn)，如果查詢的結(jié)點(diǎn)在鏈表的尾部也需遍歷整個(gè)鏈表。

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

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

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

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

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

類似于單鏈表，接下來(lái)讓我們實(shí)現(xiàn)一個(gè)帶有頭結(jié)點(diǎn)的循環(huán)單鏈表類，并用頭指針標(biāo)識(shí)鏈表的開(kāi)頭，如果你還不了解單鏈表，可以參考《單鏈表及其操作實(shí)現(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é)點(diǎn)指針域 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)單鏈表長(zhǎng)度

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

    def __len__(self):
        return self.length

2.1.3 讀取指定位置元素

重載 __getitem__ 操作用于實(shí)現(xiàn)讀取鏈表指定位置元素的操作，類似的，我們也可以實(shí)現(xiàn)修改指定位置元素的操作，只需要重載 __setitem__ 操作，它們的時(shí)間復(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)，這兩個(gè)操作與單鏈表的操作完全相同。

2.1.4 查找指定元素

在循環(huán)單鏈表中查找指定元素的操作與單鏈表基本相同，使用 current 指針沿后繼鏈依次遍歷每個(gè)結(jié)點(diǎn)，并判斷其值是否等于指定值 value，若是則返回該結(jié)點(diǎn)索引，否則繼續(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 屬性的原因，我們可通過(guò) 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é)點(diǎn)
            node.next = previous.next
            previous.next = node
            self.length += 1

2.1.6 刪除指定位置元素

要?jiǎng)h除鏈表中第i個(gè)結(jié)點(diǎn)，同樣首先找到刪除位置的前一個(gè)結(jié)點(diǎn) previous，指針 current 指向要?jiǎng)h除的結(jié)點(diǎn)，將 previous 的指針域修改為待刪除結(jié)點(diǎn) current 的后繼結(jié)點(diǎn)的地址，刪除后的結(jié)點(diǎn)需動(dòng)態(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)用對(duì)象上的 __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] 刪除指定元素，其時(shí)間復(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] 為了方便的在鏈表尾部追加新元素，可以實(shí)現(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 簡(jiǎn)單的實(shí)現(xiàn)方法

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

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

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

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

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

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

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

以上代碼輸出如下：

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

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

# 在指定位置添加/刪除結(jié)點(diǎn)
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)單鏈表基本操作實(shí)現(xiàn)復(fù)雜操作

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

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

def merge(cllist1, cllist2):
    current = cllist1.head
    while current.next != cllist1.head:
        current = current.next
    # 若cllist2不為空，進(jìn)行連接操作
    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
# 算法測(cè)試
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)雙鏈表實(shí)現(xiàn)

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

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

由于循環(huán)雙鏈表類 DoubleLinkedCircularList 的代碼中大部分與雙向鏈表類 DoublyLinkedList 完全相同，因此我們借助繼承機(jī)制來(lái)簡(jiǎn)化循環(huán)雙鏈表的實(shí)現(xiàn)，DoublyLinkedList 類的實(shí)現(xiàn)參考《雙向鏈表及其操作實(shí)現(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é)點(diǎn)的 next 指針指向自身外，previous 指針同樣需要指向自身：

class DoubleLinkedCircularList(DoublyLinkedList):
    def __init__(self, data=None):
        self.length = 0
        # 初始化頭結(jié)點(diǎn)
        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é)點(diǎn)是否是鏈表中的最后一個(gè)結(jié)點(diǎn)：

    def __delitem__(self, index):
        # 刪除指定位置結(jié)點(diǎn)
        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

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

? 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)用示例

接下來(lái)，我們測(cè)試上述實(shí)現(xiàn)的循環(huán)雙鏈表，以驗(yà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 長(zhǎng)度為：', len(dlclist))
# 查找指定元素，這里就是調(diào)用父類的locate方法
print('apple 在 dlclist 中序號(hào)為：', dlclist.locate('apple'))
# 獲取指定位置元素
print('循環(huán)雙鏈表 dlclist 第 0 個(gè)元素為：', 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 長(zhǎng)度為： 4
apple 在 dlclist 中序號(hào)為： 1
循環(huán)雙鏈表 dlclist 第 0 個(gè)元素為： 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)鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: