python单向循环链表原理与实现方法示例
本文实例讲述了python单向循环链表原理与实现方法。分享给大家供大家参考，具体如下：
单向循环链表
单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。
操作
- is_empty()判断链表是否为空
- length()返回链表的长度
- travel()遍历
- add(item)在头部添加一个节点
- append(item)在尾部添加一个节点
- insert(pos,item)在指定位置pos添加节点
- remove(item)删除一个节点
- search(item)查找节点是否存在
实现
#-*-coding:utf-8-*-
#!python3
classNode(object):
"""节点"""
def__init__(self,item):
self.item=item
self.next=None
classSinCycLinkedlist(object):
"""单向循环链表"""
def__init__(self):
self.__head=None
defis_empty(self):
"""判断链表是否为空"""
returnself.__head==None
deflength(self):
"""返回链表的长度"""
#如果链表为空，返回长度0
ifself.is_empty():
return0
count=1
cur=self.__head
whilecur.next!=self.__head:
count+=1
cur=cur.next
returncount
deftravel(self):
"""遍历链表"""
ifself.is_empty():
return
cur=self.__head
print(cur.item,)
whilecur.next!=self.__head:
cur=cur.next
print(cur.item,)
print("")
defadd(self,item):
"""头部添加节点"""
node=Node(item)
ifself.is_empty():
self.__head=node
node.next=self.__head
else:
#添加的节点指向_head
node.next=self.__head
#移到链表尾部，将尾部节点的next指向node
cur=self.__head
whilecur.next!=self.__head:
cur=cur.next
cur.next=node
#_head指向添加node的
self.__head=node
defappend(self,item):
"""尾部添加节点"""
node=Node(item)
ifself.is_empty():
self.__head=node
node.next=self.__head
else:
#移到链表尾部
cur=self.__head
whilecur.next!=self.__head:
cur=cur.next
#将尾节点指向node
cur.next=node
#将node指向头节点_head
node.next=self.__head
definsert(self,pos,item):
"""在指定位置添加节点"""
ifpos<=0:
self.add(item)
elifpos>(self.length()-1):
self.append(item)
else:
node=Node(item)
cur=self.__head
count=0
#移动到指定位置的前一个位置
whilecount<(pos-1):
count+=1
cur=cur.next
node.next=cur.next
cur.next=node
defremove(self,item):
"""删除一个节点"""
#若链表为空，则直接返回
ifself.is_empty():
return
#将cur指向头节点
cur=self.__head
pre=None
whilecur.next!=self.__head:
ifcur.item==item:
#先判断此结点是否是头节点
ifcur==self.__head:
#头节点的情况
#找尾节点
rear=self.__head
whilerear.next!=self.__head:
rear=rear.next
self.__head=cur.next
rear.next=self.__head
else:
#中间节点
pre.next=cur.next
return
else:
pre=cur
cur=cur.next
#退出循环，cur指向尾节点
ifcur.item==item:
ifcur==self.__head:
#链表只有一个节点
self.__head=None
else:
#pre.next=cur.next
pre.next=self.__head
defsearch(self,item):
"""查找节点是否存在"""
ifself.is_empty():
returnFalse
cur=self.__head
ifcur.item==item:
returnTrue
whilecur.next!=self.__head:
cur=cur.next
ifcur.item==item:
returnTrue
returnFalse
if__name__=="__main__":
ll=SinCycLinkedlist()
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()
运行结果：
length:6
6
2
1
4
3
5True
False
length:5
6
2
4
3
5
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。