Python数据结构之循环链表详解
本文详细解析Python中循环链表与循环双链表的实现原理及代码。涵盖循环单链表的初始化、遍历、插入删除操作，以及利用继承简化实现的技巧。同时深入讲解循环双链表的节点指针处理及复杂操作，通过完整代码示例验证各项功能，帮助开发者掌握环形数据结构的核心逻辑。
0. 学习目标
循环链表 (Circular Linked List) 属于链式存储结构的一种变体，其核心特征是将链表中最后一个结点的指针域指向头结点，从而构成一个首尾相连的环形结构。这种设计使得链表的操作更加灵活便捷。在已介绍单链表和双向链表的基础上，本节将重点阐述如何基于这两种基础结构构建循环链表与循环双链表，并实现相关操作。学习本节需掌握以下核心内容：
理解循环链表的基本概念及其优缺点
掌握循环链表及其核心操作的代码实现
掌握循环双链表及其核心操作的代码实现
1. 循环链表简介
在传统的单链表或双向链表中，最后一个结点的指针域通常指向 None（空值）。这意味着访问链表数据必须从头结点开始顺序遍历，无法进行随机访问；若目标结点位于链表尾部，则需遍历整个链表。
循环链表是一种特殊的线性表，其首尾端点相互连接，形成闭环。具体而言，链表中最后一个结点的指针指向第一个结点（头结点）。这意味着在循环链表中，每个结点都有后继结点，不存在指向空值的指针。
循环链表的主要优势在于：从链表中任意结点出发，顺着指针链均可遍历到表中其他所有结点，无需担心遇到空指针。此外，它并未占用额外的存储空间，仅通过修改最后一个结点的指针指向，即可提升操作的灵活性与便利性。
循环链表可基于单链表或双向链表构建。基于单链表构建的称为循环单链表，基于双向链表构建的称为循环双链表。两种类型的循环链表示意图如下所示：
NOTE：鉴于读者对链表结构已较为熟悉，文中对相似操作仅做简要说明，重点聚焦于具有差异性的关键操作实现。
2. 循环单链表实现
与单链表类似，我们将实现一个带有头结点的循环单链表类，并使用头指针标识链表起始位置。若对单链表尚不熟悉，可参考《单链表及其操作实现》一文。
2.1 循环单链表的基本操作
循环单链表的基本操作与单链表高度相似，主要区别在于循环遍历的终止条件：由判断 current == None 改为判断 current != head。
2.1.1 循环单链表的初始化
在初始化函数中，创建的头结点指针域 next 不指向空，而是指向其自身，形成初始的闭环：
class CircularLinkedList:
def __init__(self):
head_node = Node()
self.head = head_node
head_node.next = head_node
self.length = 0
2.1.2 获取循环单链表长度
通过重载 __len__ 方法，直接返回对象内部的 length 属性值，以获取循环单链表的长度：
def __len__(self):
return self.length
2.1.3 读取指定位置元素
重载 __getitem__ 方法以实现读取指定位置元素的功能。同理，若需修改指定位置元素，可重载 __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可以看出，上述读取与修改操作与单链表的实现逻辑完全一致。
2.1.4 查找指定元素
在循环单链表中查找指定元素的操作与单链表基本相同。使用 current 指针沿后继链依次遍历每个结点，判断其值是否等于指定值 value。若相等则返回该结点索引，否则继续向后搜索。关键区别在于循环遍历的终止条件由 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 属性，可通过该属性判断插入位置的合法性。因此，在循环单链表中指定位置插入新元素的操作与单链表完全相同：
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 的后继结点地址，随后动态释放被删除的结点：
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 函数触发对象上的 __str__ 方法，可生成适合打印的字符串表示：
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] 为方便在链表尾部追加新元素，可额外实现 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 简单的实现方法
观察上述实现可知，CircularLinkedList 类的代码大部分与 SinglyLinkedList 类完全相同。若熟悉继承机制，可令 CircularLinkedList 继承自《单链表及其操作实现》中定义的 SinglyLinkedList 类，从而简化循环单链表的实现过程。
from SinglyLinkedList import SinglyLinkedList
class CircularLinkedList(SinglyLinkedList):
"""
利用继承机制仅需要实现循环单链表与单链表中不同的操作,仅需要重载父类中：
__init__(), locate(), del_value(), __str__(), append() 函数即可
相关代码在上一小节已经给出，这里不再赘述
"""
pass
2.3 循环单链表应用示例
接下来，我们将测试上述实现的循环单链表，以验证各项操作的有效性。首先初始化一个链表 cllist，并向其中追加若干元素：
cllist = CircularLinkedList()
# 在循环单链表末尾追加元素
cllist.append('apple')
cllist.append('lemon')
# 在指定位置插入元素
cllist.insert(0, 'banana')
cllist.insert(2, 'orange')
我们可以直接打印链表中的数据元素、链表长度等关键信息：
print('循环单链表 cllist 数据为：', cllist)
print('循环单链表 cllist 长度为：', len(cllist))
print('循环单链表 cllist 第 0 个元素为：', cllist[0])
cllist[0] = 'pear'
print('修改循环单链表 cllist 后数据元素为：', cllist)
以上代码输出如下：
循环单链表 cllist 数据为： [banana-->apple-->orange-->lemon] 循环单链表 cllist 长度为： 4 循环单链表 cllist 第 0 个元素为： banana 修改循环单链表 cllist 后数据元素为： [pear-->apple-->orange-->lemon]
接下来，演示在指定位置添加/删除元素，以及如何查找指定元素等操作：
# 在指定位置添加/删除结点
cllist.insert(1, 'grape')
print('在位置 1 添加 grape 后循环单链表 cllist 数据：', cllist)
del(cllist[2])
print('修改循环单链表 cllist 后数据：', cllist)
# 删除指定元素
cllist.del_value('pear')
print('删除 pear 后循环单链表 cllist 数据：', cllist)
cllist.append('watermelon')
print('添加 watermelon 后循环单链表 cllist 数据：', cllist)
以上代码输出如下：
在位置 1 添加 grape 后循环单链表 cllist 数据： [pear-->grape-->apple-->orange-->lemon] 修改循环单链表 cllist 后数据： [pear-->grape-->orange-->lemon] 删除 pear 后循环单链表 cllist 数据： [grape-->orange-->lemon] 添加 watermelon 后循环单链表 cllist 数据： [grape-->orange-->lemon-->watermelon]
2.4 利用循环单链表基本操作实现复杂操作
[1] 将两个循环单链表首尾相接进行合并，连接示例如下图所示：
与单链表不同，循环单链表的连接操作不仅需要遍历第一个链表找到最后一个结点并连接到第二个链表，还需遍历第二个链表，使第二个链表的尾结点 next 指针指向第一个链表的头结点。具体实现如下：
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('循环单链表 cllist1：', cllist1)
print('循环单链表 cllist2：', cllist2)
result = merge(cllist1, cllist2)
print('循环链表连接结果：', result)
算法执行结果如下：
循环单链表 cllist1： [0-->1-->2-->3-->4] 循环单链表 cllist2： [5-->10-->15-->20-->25] 循环单链表连接结果： [0-->1-->2-->3-->4-->5-->10-->15-->20-->25]
3. 循环双链表实现
类似于双向链表，我们将实现一个带有头结点的循环双链表类，并使用头指针标识链表起始位置。若对双向链表不熟悉，可参考《双向链表及其操作实现》一文。
3.1 循环双链表的基本操作
由于循环双链表类 DoubleLinkedCircularList 的代码大部分与双向链表类 DoublyLinkedList 完全相同，我们借助继承机制来简化循环双链表的实现，其中 DoublyLinkedList 类的实现可参考《双向链表及其操作实现》。
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)循环双链表的初始化，不仅需要将头结点的 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))
相比于普通双链表，循环双链表的删除和插入操作更为便捷。得益于其循环特性，无需特别考虑所删除或插入的结点是否为链表最后一个结点：
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 s3.2 循环双链表应用示例
接下来，测试上述实现的循环双链表，以验证操作的有效性：
dlclist = DoubleLinkedCircularList()
# 在链表末尾追加元素
dlclist.append('apple')
dlclist.append('lemon')
# 在指定位置插入元素
dlclist.insert(0, 'banana')
dlclist.insert(2, 'orange')
print('循环双链表 dlclist 数据为：', dlclist)
print('循环双链表 dlclist 长度为：', len(dlclist))
# 查找指定元素，这里就是调用父类的locate方法
print('apple 在 dlclist 中序号为：', dlclist.locate('apple'))
# 获取指定位置元素
print('循环双链表 dlclist 第 0 个元素为：', dlclist[0])
# 修改数据元素
dlclist[0] = 'pear'
print('修改循环双链表 dlclist 后数据元素为：', dlclist)
del(dlclist[2])
print('修改循环双链表 dlclist 后数据：', dlclist)
# 删除指定元素
dlclist.del_value('pear')
print('删除 pear 后循环双链表 dlclist 数据：', dlclist)
上述程序输出如下所示：
循环双链表 dlclist 数据为： [banana<-->apple<-->orange<-->lemon] 循环双链表 dlclist 长度为： 4 apple 在 dlclist 中序号为： 1 循环双链表 dlclist 第 0 个元素为： banana 修改循环双链表 dlclist 后数据元素为： [pear<-->apple<-->orange<-->lemon] 修改循环双链表 dlclist 后数据： [pear<-->apple<-->lemon] 删除 pear 后循环双链表 dlclist 数据： [apple<-->lemon]
以上就是Python数据结构之循环链表详解的详细内容，更多关于Python循环链表的资料请关注本站其它相关文章！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
