使用python实现单向循环链表，供大家参考，具体内容如下
单向循环链表
将所有的链接在一起，每一个节点分为数据存储区和链接区，数据区存储数据，链接区链接下一个节点
item： 存储数据的地方
next： 链接下一个节点
注意： 单向循环链表是首位链接，即尾部的节点要和头部的节点链接
单向链表操作
1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在
代码实现
# Functions 函数声明
class Node():
"""实例化节点类"""
def __init__(self, item):
self.item = item
self.next = None
class Linklist():
"""
存放节点类
"""
def __init__(self):
self.head = None
# 1. 链表是否为空
def is_empty(self):
return self.head == None
# 2. 链表的长度
def length(self):
"""
返回链表的长度
遍历所有的节点，使用计数器计数
1、链表为空情况
"""
# 实例化节点
cur = self.head
if self.is_empty():
return 0
else:
# 计数
count = 1
# 遍历链表
while cur.next != self.head:
count+=1
cur = cur.next
return count
# 3. 遍历链表
def travel(self):
"""
遍历链表，获取所有的数据
实例游标，遍历数据，输出数据
1、 空链表情况
2、 只有头部节点情况
3、 只有尾部节点情况
"""
# 实例化游标
cur = self.head
if self.is_empty():
return None
else:
# 遍历数据
while cur.next != self.head:
print(cur.item, end=' ')
cur = cur.next
# 最后一个节点要单独输出
print(cur.item)
# 4. 链表头部添加元素
def add(self, item):
"""
往链表头部添加数据
分析
链表为空
self.head 直接指向node， 再讲node指向自己
链表不为空
node.next = self.head
"""
# 实例化游标
cur = self.head
# 实例化节点
node = Node(item)
# 判断是否为空
if self.is_empty():
self.head = node
node.next = node
else:
# 不为空的情况
# 要将最后一个节点指向node
while cur.next != self.head:
cur = cur.next
node.next = self.head
self.head = node
cur.next = node
# 5. 链表尾部添加元素
def append(self, item):
"""
往尾部添加数据
分析
实例化节点，再实例化游标先指向最后一个节点
调换指向
1、空链表情况
2、只有一个链表情况
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
# 判断是否为空
if self.is_empty():
self.add(item)
else:
# 不为空的情况,移动游标指向最后一个节点
while cur.next != self.head:
cur = cur.next
node.next = self.head
cur.next = node
pass
# 6. 链表指定位置添加元素
def insert(self, index, item):
"""
指定位置添加数据
实例化节点， 实例化游标指向索引的数据，更改指向
位置大小
链表是否为空
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
if index <=0:
self.add(item)
elif index > (self.length()-1):
self.append(item)
else:
# 判断链表是否为空
if self.is_empty():
self.add(item)
else:
# 移动游标，指向指定的索引位置
count = 0
while count < index-1:
count+=1
cur = cur.next
node.next = cur.next
cur.next = node
pass
# 7. 链表删除节点
def remove(self, item):
"""
删除指定的节点
实例化游标，遍历链表插件这个节点是否存在，存在则更改指向
不存在，则不修改
空链表情况
头节点情况
尾结点情况
"""
# 实例化游标
cur = self.head
if self.is_empty():
return None
else:
# 不为空，遍历链表，对比数据是否相等
# 如果头节点是要删除的数据
if cur.item == item:
self.head=cur.next
# 找出最后的节点，将最后的节点指向，删除后面的那个节点
while cur.next != self.head:
cur = cur.next
cur.next = cur.next
else:
pro = None
while cur.next != self.head:
if cur.item == item:
if cur.item == item:
pro.next = cur.next
return True
else:
pro = cur
cur = cur.next
if cur.item == item:
pro.next = self.head
pass
# 8. 查找节点是否存在
def search(self, item):
"""
查找该节点是否存在
实例化游标，遍历所有的节点
查看当前节点的数据是否和item 相等
空链表
头节点
尾结点
"""
# 实例化游标
cur = self.head
# 判断空链表
if self.is_empty():
return None
else:
# 不为空遍历整个链表
if cur.item == item:
return True
else:
while cur.next != self.head:
if cur.item == item:
return True
else:
cur = cur.next
if cur.item == item:
return True
pass测试运行
# 程序的入口
if __name__ == "__main__":
a = Linklist()
a.add(400)
a.add(300)
a.add(200)
a.add(100)
# a.append(10)
a.insert(4,6)
# a.remove(6)
print(a.length()) # 5
a.travel() # 100 200 300 400 6
print(a.search(100)) # True
pass以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程网。
