網(wǎng)站首頁 編程語言 正文
0. 學(xué)習(xí)目標
循環(huán)鏈表 (Circular Linked List) 是鏈式存儲結(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)鏈表可以基于單鏈表和雙向鏈表，通常基于單鏈表的循環(huán)鏈表稱為循環(huán)單鏈表，而基于雙向鏈表的循環(huán)鏈表稱為循環(huán)雙鏈表，兩種類型的循環(huán)鏈表示意圖如下所示：
NOTE：由于我們對于鏈表已經(jīng)非常熟悉了，因此對于鏈表中相似的操作只會進行簡要的介紹，我們的主要精力將放在具有差異的操作上。
2. 循環(huán)單鏈表實現(xiàn)
類似于單鏈表，接下來讓我們實現(xiàn)一個帶有頭結(jié)點的循環(huán)單鏈表類，并用頭指針標識鏈表的開頭，如果你還不了解單鏈表，可以參考《單鏈表及其操作實現(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)雙鏈表類，并用頭指針標識鏈表的開頭，如果你還不了解雙向鏈表，可以參考《雙向鏈表及其操作實現(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]
原文鏈接：https://blog.csdn.net/LOVEmy134611/article/details/121162008
相關(guān)推薦
- 2022-09-18 Python?Pandas實現(xiàn)DataFrame合并的圖文教程_python
- 2022-06-13 詳解Python如何利用Pandas與NumPy進行數(shù)據(jù)清洗_python
- 2022-04-01 Fatal Python error: Py_Initialize: unable to load
- 2022-08-12 Python打包成exe文件的詳細操作指南_python
- 2023-12-21 npm install 報錯（npm ERR! errno: -4048, npm ERR! c
- 2022-09-22 String和StringBuilder的用法
- 2022-09-17 詳解python中靜態(tài)方法staticmethod用法_python
- 2023-07-25 rollup的五大核心配置
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速