荒废了一段时间，这段时间实验室事情多，就没怎么看数据结构（悲痛）。
什么是单向循环链表？
顾名思义，单向循环链表，就是在单向链表的基础上做一些改动，实现链表循环，即将原本尾节点的next指向None，现指向链表的头节点，这样一来就实现了所谓的单项循环链表。
单向循环链表
了解了大致的概念之后，我们需要用代码实现这个单向循环链表，单向循环链表的代码也是在单向链表的代码基础上进行更改。
节点的构造是没有区别的，可以直接用单向链表的代码。
那关于首节点，我们是不是需要一些改动啊，比如让它指向自己。
class Node():
'''节点'''
def __init__(self,elem):
self.elem = elem
self.next = None
class SingleLinkList(object):
'''单向循环链表'''
def __init__(self,node=None):
#内部私有函数，链表头的初始化，可以直接建立空链表
self.__head = node
if node:
node.next = node#self.__head指向node，如果node存在那还需要建立一个回环，让 note.next指向自己本身
- 那么关于探空的功能呢?是不是也无需更改？
答案是无需更改
def is_empty(self):
"""判断链表是否为空"""
return self.__head == None
-
实现求长度的功能：
单向链表结束的条件：cur == None或者cur == self.__head
能否用在我们的单项循环链表呢，答案是不可以，因为单向链表的判断语句不仅在尾结点上复合，且在头节点也符合，故不可用。
单向循环链表的结束条件：cur.next == seif.__head
但是我们的count初始值为1，如果按照这个初值走，最后会少算一个节点，故初始值改为1。
def length(self):
"""返回链表的长度"""
#cur游标，用来移动遍历节点
#count，用来记录节点数量
count = 1
cur = self.__head
while cur.next != self.__head:
count += 1
cur = cur.next
return count
考虑一下，若链表为空链表怎么处理呢，若链表只有一个节点呢？
def length(self):
"""返回链表的长度"""
#cur游标，用来移动遍历节点
#count，用来记录节点数量
count = 1
if self.is_empty():
return 0
cur = self.__head
while cur.next != self.__head:#满足仅有一个节点的选项
count += 1
cur = cur.next
return count
- 如何实现遍历功能：
如果我们使用单向链表的原代码，会发现忽略了打印尾结点，所以最后要加一个打印。
考虑特殊情况，若这个单向循环链表为空链表呢？我们可以预先做个判断，若为空则直接返回，不进行任何操作。
若只含有一个节点呢？直接看代码吧。
def travel(self):
"""遍历链表"""
cur = self.__head
if self.is_empty():
return
while cur != self.__head:
print(cur.elem,end=' ')
cur = cur.next
print(cur.next,end=' ')
通过代码分析，若只含有一个节点，程序不会执行while循环，而是直接打印这个节点。
- 实现头插法（add）:
-
方法一 这个主要是自己要理解
-
方法二
这个方法比较容易理解，首先就是移动游标找到尾结点，当终止while循环的时候，游标cur所指向的位置恰好是尾结点，然后将添加的新节点node的node.next指向原首节点也就是self.__head，然后让self.__head指向node，最后将尾结点的next，指向我们新添加的这个头节点，即cur.next指向node或者也可以指向self.__head，因为此时self.head就指向node。
考虑一下特殊情况，当链表为空链表时，那么self.__head指向的便是None，cur就在None的位置了，但是None怎么可能会有next呢？显然程序无法满足空链表的头插需求；现在考虑一下只有一个节点的链表是否符合要求呢？显然符合要求；下面是代码实现。
def add(self, item):
"""头部添加节点"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
node.next = self.__head
self.__head = node
cur.next = node
- 实现尾插法：
-
方法一这个应该不难理解
-
方法二这个也不难理解
那我们直接上代码吧：
def append(self, item):
"""尾部添加节点"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
node.next = self.__head
验证一下，若单向循环链表只有一个节点怎么办?是不是程序依旧可以实现啊。
-
实现随机插入的（insert）方法：
我们直接先码一下，单向链表的代码，看看怎么更改
因为随机插入涉及的头插和尾插都是调用，所以我们这里就不在更改，因为已经可以实现；唯一需要更改的就是else语句，也就是涉及到中间插入的问题，但是单向循环链表的中间插入和单向链表的中间插入并没有什么区别啊，所以更无需更改。所以整体同单向链表一致，无需再做任何更改。 -
实现查找某个元素的功能：单向链表
我们直接从这个单向链表中更改：
while语句的条件存在问题，要改成while cur.next ！= self.head
这样一来if条件判断到最后一个元素的时候，就会终止循环了，而不再进行判断，其次还需要考虑的问题是特殊情况，比如空链表或者仅有一个节点的情况(直接上代码，按照代码进行分析)。
def search(self, item):
"""查找节点是否存在"""
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.elem == item:
return True
else:
cur = cur.next
if cur.elem == item:
return True
return False
我们考虑一下，单个节点，代码也完全可以实现预期目标。
-
实现删除节点的功能：观察代码，不能拿发现这个删除首节点的情况是最复杂的，因为涉及要遍历到尾节点，然后改变尾节点的指向。如果是删除中间节点的话，首尾节点无需更改，直接更改中间节点的指向即可。但同时当cur指向尾节点的时候，会忽略尾节点的判断，所以最后要重新判断一下尾节点的问题。接下来就是考虑首届点删除的问题了。还要考虑特殊情况：
- 判断是否为空链表，若为空直接返回。
- 如果仅有一个节点，那么程序直接跳出while循环，执行pre.next但pre指向的是None没有next ,需要让head直接指向None。
总程序如下：
def remove(self, item):
"""删除一个节点"""
if self.is_empty():
return
cur = self.__head
pre = None
while cur.next != self.__head:
if cur.elem == item:
#先判断是否为头节点，然后再去处理头节点
if cur == self.__head:#头节点的情况下
rear = self.__head
self.__head = cur.next
while rear.next != self.__head:
rear = rear.next
self.__head = cur.next
rear.next = self.__head
else:#在中间删除
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
if cur.elem == item:#退出循环cur指向尾节点，在尾部删除
if cur == self.__head:#链表只有一个节点
self.__head = None
else:
pre.next = cur.next
总体代码：
class Node():
'''节点'''
def __init__(self,elem):
self.elem = elem
self.next = None
class SingleCycleLinkList(object):
'''单向循环链表'''
def __init__(self,node=None):
#内部私有函数，链表头的初始化，可以直接建立空链表
self.__head = node
if node:
node.next = node#self.__head指向node，如果node存在那还需要建立一个回环，让 note.next指向自己本身
def is_empty(self):
"""判断链表是否为空"""
return self.__head == None
def length(self):
"""返回链表的长度"""
#cur游标，用来移动遍历节点
#count，用来记录节点数量
count = 1
if self.is_empty():
return 0
cur = self.__head
while cur.next != self.__head:#满足仅有一个节点的选项
count += 1
cur = cur.next
return count
def travel(self):
"""遍历链表"""
cur = self.__head
if self.is_empty():
return
while cur != self.__head:
print(cur.elem,end=' ')
cur = cur.next
print(cur.next,end=' ')
def add(self, item):
"""头部添加节点"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
node.next = self.__head
self.__head = node
cur.next = node
def append(self, item):
"""尾部添加节点"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = self.__head
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
cur.next = node
node.next = self.__head
def insert(self, pos, item):
"""在指定位置添加节点"""
pre = self.__head
count = 0
if pos <= 0:
self.add(item)
elif pos >= (self.length()-1):
self.append(item)
else:
while count < (pos-1):
count += 1
pre = pre.next
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
"""删除一个节点"""
if self.is_empty():
return
cur = self.__head
pre = None
while cur.next != self.__head:
if cur.elem == item:
#先判断是否为头节点，然后再去处理头节点
if cur == self.__head:#头节点的情况下
rear = self.__head
self.__head = cur.next
while rear.next != self.__head:
rear = rear.next
self.__head = cur.next
rear.next = self.__head
else:#在中间删除
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
if cur.elem == item:#退出循环cur指向尾节点，在尾部删除
if cur == self.__head:#链表只有一个节点
self.__head = None
else:
pre.next = cur.next
def search(self, item):
"""查找节点是否存在"""
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.elem == item:
return True
else:
cur = cur.next
if cur.elem == item:
return True
return False
if __name__ == '__main__':
li = SingleCycleLinkList()
print(li.is_empty())
print(li.length())
li.append(1)
li.append(2)
print(li.is_empty())
print(li.length())
li.append(3)
li.append(4)
li.add(10)
li.add(20)
li.insert(2,30)
li.insert(10,1000)
li.insert(0,999)
li.travel()
print()
print(li.search(20))
print(li.search(123))
li.travel()
li.remove(999)
li.travel()
li.remove(1000)
li.travel()
li.remove(30)
li.travel()
测试结果：
D:\anaconda\python.exe D:/bilibili大学/简书代码/singe_cycle_link_list.py
True
0
False
2
<__main__.Node object at 0x000001C2CEDBB390>
True
False
<__main__.Node object at 0x000001C2CEDBB390> <__main__.Node object at 0x000001C2CEDBB438> <__main__.Node object at 0x000001C2CEDBB438> <__main__.Node object at 0x000001C2CEDBB438>
Process finished with exit code 0
