Python实现单向循环链表
Python实现单向循环链表
关于链表的介绍，请参考：链表介绍
本篇文章使用 Python 来实现一个单向循环链表。
一、定义一个创建节点的类
链表是由一个个的节点组成的，在创建链表之前，要先创建节点，然后把节点“串”到链表上。在同一个链表中，每个节点的结构都相同，只是节点中保存的数据不同和引用不同，所以提前声明一个创建节点的类，需要创建节点时实例化即可。
# coding=utf-8
class Node(object):
def __init__(self, data):
self.data = data
self.next = None单向循环链表的节点包含两个域，一个信息域(元素域)和一个链接域(引用域)。在实例化一个节点时，传入数据保存到信息域中，链接域默认为空，当对节点进行“链接”操作时，再设置具体的链接域。
单向循环链表中，尾节点的链接域指向头节点。
二、定义一个单向循环链表类
实例化一个单向循环链表时，这个链表是一个空链表，把节点依次“链接”上去后，链表中才有节点和数据。
在链表中，要找到链表的某个节点，需要从链表的头节点开始，依次寻找，所以在实例化单向循环链表时，必须定义好链表的“头”，当加入头节点时，将链表的“头”指向头节点。
定义一个单向循环链表类 SingleCycleLinkList，初始化一个单向循环链表时，链表的“头”指向空值，默认为空链表。
class SingleCycleLinkList(object):
def __init__(self):
self.__head = None三、实现单向循环链表的展示功能
def is_empty(self):
return not self.__head
def show(self):
if self.is_empty():
print('空链表')
return
cur = self.__head
while cur.next != self.__head:
print(cur.data, end=' → ')
cur = cur.next
print(cur.data, '→ ')先实现判断链表是否为空的方法 is_empty() ，实例化单向循环链表时，默认是空的，链表的头指向为空。所以，如果链表的头指向为空(对应布尔值False)， is_empty() 的值就为 True ，反之。
展示链表中的数据，就是将链表中所有的数据依次打印输出。链表不像顺序表有“索引”，链表只能从头节点开始依次往下找，直到尾节点。所以链表不能使用 for 循环进行遍历，只能使用 while 循环进行遍历，并使用一个游标 cur 来记录当前所处的节点，通过游标 cur 向下一个节点移动来遍历，当链接域指向头节点时(尾节点)停止。
这里要注意单向循环链表与单向链表的区别，遍历时单向链表的尾节点是指向空，单向循环链表的尾节点是指向头节点，不仅要修改判断的条件，还要注意尾节点是否已经进行了逻辑处理，不能漏了。
实现 show() 方法时，为了更形象地展示链表中每个节点的关系，我在每个节点之后使用右箭头连接(空链表无效果)。
if __name__ == '__main__':
s = SingleCycleLinkList()
print("is_empty: ", s.is_empty())
s.show()运行结果：
is_empty: True
空链表四、实现单向循环链表中添加数据的功能
def add(self, data):
node = Node(data)
if self.is_empty():
self.__head = node
node.next = self.__head
return
cur = self.__head
while cur.next != self.__head:
cur = cur.next
cur.next = node
node.next = self.__head
self.__head = node
def append(self, data):
if self.is_empty():
self.add(data)
return
cur = self.__head
while cur.next != self.__head:
cur = cur.next
node = Node(data)
cur.next = node
node.next = self.__head
def length(self):
if self.is_empty():
return 0
length = 1
cur = self.__head
while cur.next != self.__head:
length += 1
cur = cur.next
return length
def insert(self, index, data):
if index <= 0:
self.add(data)
return
if index > self.length() - 1:
self.append(data)
return
cur = self.__head
for i in range(index-1):
cur = cur.next
node = Node(data)
node.next = cur.next
cur.next = node添加数据到单向循环链表中，无论将数据添加到链表的哪个位置，都要先创建一个新节点，新节点里存放对应的数据，然后将新节点添加到指定的位置。
add(data)：从头部添加时，链表原来的头节点会成为第二个节点，新节点成为头节点。添加分为三步，第一步将新节点的链接域指向原来的头节点，第二步将尾节点指向新节点，第三步将链表的头指向新节点。在第二步中，要先找到尾节点，使用一个游标从头节点开始，依次找到尾节点。如果原来的链表为空，将链表的头指向新节点，再将新节点的链接域指向头，即使只有一个节点也要保证循环的结构。
append(data)：从尾部添加时，找到链表的尾节点，先将尾节点的链接域指向新节点，再将新节点的链接域指向头节点。如果原来的链表为空，则与从头部添加一样，直接调用即可。
insert(index, data)：在指定位置添加数据时，要使用一个游标 cur 来找到此位置的前一个节点，将新节点的链接域指向指定位置原来的节点，然后将游标记录的节点(指定位置的前一个节点)的链接域指向新节点，这样就成功将新节点插入到了指定位置。
如果指定的位置是负数或超过了链表最大长度，则需要特殊处理，上面的处理是负数在头部添加，超过最大长度在尾部添加。也可以直接抛出 IndexError ，这个自己按需选择。
同时，上面实现了获取链表长度的方法 length()，返回链表当前的节点个数。
s.add(1)
s.add(10)
s.append(2)
s.append(3)
s.append(4)
s.show()
s.insert(1, 20)
s.show()
print("链表长度：", s.length())运行结果：
10 → 1 → 2 → 3 → 4 →
10 → 20 → 1 → 2 → 3 → 4 →
链表长度： 6五、实现单向循环链表的查询和修改功能
def is_exist(self, value):
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.data == value:
return True
cur = cur.next
if cur.data == value:
return True
return False
def index(self, value):
if self.is_empty():
return -1
index = 0
cur = self.__head
while cur.next != self.__head:
if cur.data == value:
return index
cur = cur.next
index += 1
if cur.data == value:
return index
return -1
def setitem(self, index, value):
if index < 0:
raise IndexError
if index > self.length() - 1:
raise IndexError
cur = self.__head
for i in range(index):
cur = cur.next
cur.data = valueis_exist(value)：判断一个数据是否存在链表中，遍历链表的每个节点，如果节点的数据值与目标值相等，则说明链表中存在目标值。
index(value)：返回一个数据在链表中的第几个节点，与判断是否存在的实现方式一样，这里返回的是数据处于第几个节点中，如果链表中不存在这个数据，则返回-1。
setitem(index, value)：修改指定位置的节点的数据，先根据给定的值，找到链表中该位置的节点，然后修改节点中的数据。如果指定位置小于零或大于链表长度，抛出 IndexError 。
print(s.is_exist(100))
print(s.index(20))
s.setitem(2, 30)
s.show()运行结果：
False
1
10 → 20 → 30 → 2 → 3 → 4 →六、实现单向循环链表的删除功能
def remove(self, index):
if index < 0:
raise IndexError
if index > self.length() - 1:
raise IndexError
cur = self.__head
prev = None
for i in range(index):
prev = cur
cur = cur.next
if cur == self.__head:
prev = self.__head
while prev.next != self.__head:
prev = prev.next
if prev == self.__head:
self.__head = None
return
prev.next = self.__head.next
self.__head = self.__head.next
return
prev.next = cur.next
def delete(self, value):
cur = self.__head
prev = None
while cur.next != self.__head:
if cur.data == value:
if cur == self.__head:
prev = self.__head
while prev.next != self.__head:
prev = prev.next
prev.next = cur.next
self.__head = cur.next
return
prev.next = cur.next
return
prev = cur
cur = cur.next
if cur.data == value:
if cur == self.__head:
self.__head = None
return
prev.next = cur.next
return
def delete_all(self, value):
cur = self.__head
prev = None
while cur.next != self.__head:
if cur.data == value:
if cur == self.__head:
prev = self.__head
while prev.next != self.__head:
prev = prev.next
prev.next = cur.next
self.__head = cur.next
self.delete_all(value)
return
prev.next = cur.next
self.delete_all(value)
return
prev = cur
cur = cur.next
if cur.data == value:
if cur == self.__head:
self.__head = None
return
prev.next = cur.next
self.delete_all(value)
returnremove(index)：删除指定位置的节点，使用游标 cur 找到节点，使用另一个游标 prev 来记录当前节点的前一个节点，将该位置的前一个节点的链接域指向该位置的后一个节点。如果删除的是头节点，先找到链表的尾节点，然后将尾节点指向第二个节点，再将头指向第二个节点。如果链表只有一个节点，删除时将链表的头指向空即可。如果指定的位置小于零或超过链表长度，则抛出 IndexError 。
delete(value)：删除指定值的节点，先遍历链表，找到对应值的节点，删除的方式与 remove(index) 相同。使用这个方法，如果链表中有多个满足条件的节点，只会删除最前面的一个节点。
delete_all(value)：删除数据等于指定值的所有节点，如果链表中有多个节点的数据与目标值相等，删除第一个节点后，链表的长度发生了改变，继续遍历和删除节点，会出现删除不完全甚至程序出错的情况。所以在删除第一个节点之后，递归调用自身，这样重新遍历时使用的是新的链表长度，不会出现漏删或错误。
s.remove(3)
s.show()
s.delete(4)
s.show()
s.add(4)
s.insert(3, 4)
s.insert(3, 4)
s.append(4)
s.append(4)
s.show()
s.delete_all(4)
s.show()运行结果：
10 → 20 → 30 → 3 → 4 →
10 → 20 → 30 → 3 →
4 → 10 → 20 → 4 → 4 → 30 → 3 → 4 → 4 →
10 → 20 → 30 → 3 →以上就是用 Python 实现的单向循环链表及单向循环链表的一些简单操作方法。
腾讯云开发者
