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单向循环链表实例详解的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did17019

更新时间：2022-09-13 阅读：52次