python单向循环链表如何实现

发布时间:2023-05-17 11:19:56 作者:zzz
来源:亿速云 阅读:103

本篇内容主要讲解“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单向循环链表如何实现”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

推荐阅读:
  1. 单向双向链表的实现
  2. 单向循环链表

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python

上一篇:python深度学习tensorflow参数初始化initializer源码分析

下一篇:Python基础之模块怎么使用

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》