本篇内容主要讲解“python单向循环链表如何实现”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“python单向循环...
本篇内容主要讲解“python单向循环链表如何实现”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“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
到此,相信大家对“python单向循环链表如何实现”有了更深的了解,不妨来实际操作一番吧!这里是捷杰建站网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!