python单向循环链表实例详解

作者:python-行者 时间:2023-05-25 01:29:40 

使用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

来源:https://blog.csdn.net/Dhaihaihai/article/details/111304465

标签:python,链表
0
投稿

猜你喜欢

  • Python爬虫爬取美剧网站的实现代码

    2021-07-11 01:05:04
  • php实现的三个常用加密解密功能函数示例

    2023-07-20 06:25:52
  • 关于vue-i18n在单文件js中的使用

    2024-05-09 09:38:48
  • Python pandas 列转行操作详解(类似hive中explode方法)

    2021-02-18 15:12:31
  • python 爬取英雄联盟皮肤图片

    2021-08-10 10:16:06
  • 科讯商业版中用到的ajax空间与分页函数

    2024-04-17 10:05:45
  • 基于python解线性矩阵方程(numpy中的matrix类)

    2023-11-03 06:54:12
  • mysql密码中有特殊字符&在命令行下登录的操作

    2024-01-17 22:29:18
  • Keras神经网络efficientnet模型搭建yolov3目标检测平台

    2021-10-08 11:45:33
  • golang json性能分析详解

    2024-05-09 14:57:46
  • 在asp中使用存储过程

    2008-02-26 12:17:00
  • PDO::rollBack讲解

    2023-07-23 06:52:34
  • PyTorch上实现卷积神经网络CNN的方法

    2023-10-30 11:37:05
  • 利用ImageAI库只需几行python代码实现目标检测

    2023-06-25 15:03:28
  • Python win32com 操作Exce的l简单方法(必看)

    2022-12-04 10:20:36
  • 运用ASP调用数据库中视图及存储过程

    2008-02-03 15:33:00
  • 在Django框架中设置语言偏好的教程

    2022-01-18 22:47:35
  • python executemany的使用及注意事项

    2024-01-02 22:55:16
  • Python中OpenCV Tutorials 20  高动态范围成像的实现步骤

    2022-04-02 07:24:20
  • Python3最长回文子串算法示例

    2023-05-27 14:17:10
  • asp之家 网络编程 m.aspxhome.com