定义
单链表的一个变形是单向循环链表，只不过单向循环链表最后一个节点不再指向空，而是指向头节点，从而形成了一个环。
优势
对单向链表中任一个节点的访问都需要从头结点开始；而对单向循环链表从任意节点出发都能遍历整个列表，极大的增强了其灵活性。
python 实现
class Node(object):
"""
节点
"""
def __init__(self, item):
self.item = item
self.next = None
class SinCycLinkedlist(object):
"""
单向循环链表
"""
def __init__(self):
self._head = None
def is_empty(self):
"""
判断链表是否为空
"""
return self._head == None
def length(self):
"""
返回链表的长度
"""
# 如果链表为空，返回0
if self.is_empty():
return 0
count = 1
cur = self._head
while cur.next != self._head:
count += 1
cur = cur.next
return count
def traverse(self):
"""
遍历链表
"""
if self.is_empty():
return
cur = self._head
while cur.next != self._head:
cur = cur.next
print(cur.item, end=" ")
print("")
def add(self, value):
"""
头部插入节点
"""
node = Node(value)
if self.is_empty():
self._head = node
node.next = self._head
else:
# 添加的节点指向head
node.next =self._head
# 移到链表尾部，尾部节点next指向node
cur = self._head
while cur.next != self._head:
cur = cur.next
cur.next = node
# _head指向node
self._head = node
def append(self, value):
"""
尾部插入
"""
node = Node(value)
if self.is_empty():
self._head = node
node.next = self._head
else:
# 添加的节点指向head
node.next=self._head
# 移动到链表尾部，尾部next指向node
cur = self._head
while cur.next != self._head:
cur = cur.next
cur.next = node
# node指向头节点
node.next = self._head
def insert(self, value, index):
"""
指定位置插入
"""
if index <= 0:
self.add(value)
elif index > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self._head
count = 0
while count < (index - 1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, value):
"""
删除节点
"""
node = Node(value)
if self.is_empty():
return
cur = self._head
pre = None
# 若删除的节点为头结点
if cur.item == value:
# 如果链表有多个节点
if cur.next != self._head:
# 找到尾节点 尾节点的next指向第二个节点
while cur.next != self._head:
cur = cur.next
# cur指向尾节点
cur.next = self._head.next
self._head = self._head.next
else:
# 只有一个节点
self._head = None
else:
pre = self._head
while cur.next != self._head:
# 找到要删除的
if cur.item == value:
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
# cur指向尾节点
if cur.item == value:
# 尾部删除
pre.next = cur.next
def search(self, value):
"""
查找节点
"""
if self.is_empty():
return False
cur = self._head
if cur.item == value:
return True
while cur.next != self._head:
cur = cur.next
if cur.item == value:
return True
return False
if __name__ == '__main__':
link_node = Node(100)
single_cycle_link_list = SinCycLinkedlist()
print("当前链表是否为空：", single_cycle_link_list.is_empty())
print("当前链表长度为：", single_cycle_link_list.length())
single_cycle_link_list.append(99)
print("当前链表是否为空：", single_cycle_link_list.is_empty())
print("当前链表长度为：", single_cycle_link_list.length())
single_cycle_link_list.append(23)
single_cycle_link_list.append(89)
single_cycle_link_list.append("python")
single_cycle_link_list.append(12.66)
single_cycle_link_list.add(27)
single_cycle_link_list.insert(4, 0)
single_cycle_link_list.remove(27)
single_cycle_link_list.traverse()
print(single_cycle_link_list.search(23))
结果
当前链表是否为空： True
当前链表长度为： 0
当前链表是否为空： False
当前链表长度为： 1
99 23 89 python 12.66
True
