单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。
单向循环链表.png
具体操作
- is_empty() 判断链表是否为空
- length() 返回链表的长度
- travel() 遍历
- add(item) 在头部添加一个节点
- append(item) 在尾部添加一个节点
- insert(pos, item) 在指定位置pos添加节点
- remove(item) 删除一个节点
- search(item) 查找节点是否存在
完整代码实现：
class Node(object):
"""节点"""
def __init__(self,item):
self.item=item
self.next=None
class SingleLinkList(object):
"""单向循环列表"""
def __init__(self):
self.__head=None
def is_empty(self):
"""判断列表是否为空"""
return self.__head==None
def length(self):
"""返回列表的长度"""
if self.is_empty():
return 0
count=1
cur=self.__head
while cur.next !=self.__head:
count+=1
cur=cur.next
return count
def travel(self):
"""遍历链表"""
if self.is_empty():
return
cur=self.__head
print(cur.item)
while cur.next!=self.__head:
cur=cur.next
print(cur.item)
print("")
def add(self,item):
"""头部添加节点"""
node=Node(item)
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,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
#将为节点指向node
cur=cur.next
#将node节点指向__head
node.next=self.__head
def insert(self,pos,item):
"""在指定位置添加节点"""
if pos<=0:
self.add(item)
elif pos>(self.length()-1):
self.append(item)
else:
node=Node(item)
cur=self.__head
count=0
#移动到指定位置的前一个位置
while count<(pos-1):
count+=1
cur=cur.next
node.next=cur.next
cur.next=node
def remove(self,item):
"""删除一个节点"""
if self.is_empty():
return
#将cur指向头结点
cur=self.__head
pre=Node
#若头结点的元素就是要查找的元素item
if cur.item==item:
#如果链表不止一个节点
if cur.next!=self.__head:
#先找到为节点，将为节点的next指向第二个节点
while cur.next !=self.__head:
#找到了要删除的元素
if cur.item==item:
#删除
pre.next=cur.next
return
else:
pre=cur
cur=cur.next
if cur.item==item:
#尾部删除
pre.next=cur.next
def search(self,item):
if self.is_empty():
return False
cur=self.__head
if cur.item==item:
return True
while cur.next!=self.__head:
cur=cur.next
if cur.item==item:
return True
return False
if __name__=='__main__':
ll=SingleLinkList()
ll.add(1)
ll.add(2)
ll.append(3)
ll.insert(2,4)
ll.insert(4,5)
ll.insert(0,6)
print("length:",ll.length())
ll.travel()
print(ll.search(3))
print(ll.search(7))
ll.remove(1)
print("length:",ll.length())
ll.travel()
参考：数据结构与算法Python语言描述
