Python双向循环链表的操作

目录

一、双向循环链表

双向循环链表图

 二、双向循环链表的操作

1、判断链表是否为空

2,链表长度

3,遍历整个链表

4,在链表头部添加元素

5、链表尾部添加元素

6,在指定位置插入元素

7,修改指定位置的元素

8,删除元素

9、查找元素是否存在

三、完整代码


 相关文章

Python单向链表操作

Python单向循环链表的操作

Python双向链表的操作

Python双向循环链表的操作

一、双向循环链表

双向循环链表图

结点node里有三个部分:pre(指向上一结点next的指针)、elem(元素)和next(指向下一结点的指针),head指针指向头结点,尾结点的next指向头结点,头结点的pre指向尾结点的next

 二、双向循环链表的操作

1、判断链表是否为空
 

    def is_empty(self):
        # 链表是否为空
        if self.__head is None:
            return True
        else:
            return False

2,链表长度
 

    def length(self):
        # 链表长度
        if self.is_empty():
            return 0
        count = 0
        cur = self.__head
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

3,遍历整个链表
 

  def travel(self):
     # 遍历整个链表
        if self.is_empty():
            return
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem, end=' ')
            cur = cur.next
        print(cur.elem)

4,在链表头部添加元素

      def add(self, item):
        # 链表头部添加元素
        node = Node(item)
        if self.is_empty():
            # 是空链表头指针直接指向新结点
            self.__head = node
            # 修改新结点的next指向结点自己
            node.next = node
            # 新结点的pre指向结点自己的next构成一个结点的双向循环
            node.pre = node.next
        else:
            tail = self.__head
            # 循环找到尾结点
            while tail.next != self.__head:
                tail = tail.next
            # 1.新来的节点的next指向第一个头节点
            node.next = self.__head
            # 2.再改变第一个头节点的指针指向新节点的next
            self.__head.pre = node.next
            # 3.将尾指向指向添加node节点
            tail.next = node
            # 4.新结点pre指向尾结点的next
            node.pre = tail.next
            # 5.最后修改头指针指向新结点
            self.__head = node


5、链表尾部添加元素

修改尾结点与新结点的双向指针指向

再修改新结点(这时也是尾结点了)与头结点的双向指针指向

    def append(self, item):
        # 链表尾部添加元素
        # 创建新结点
        node = Node(item)
        # 是空链表就把头节点指向这个节点
        if self.is_empty():
            self.__head = node
            node.next = node
            node.pre = node.next
        else:
            tail = self.__head
            # 找到尾节点
            while tail.next != self.__head:
                tail = tail.next
            # 修改尾结点与新结点的指针
            tail.next = node
            node.pre = tail.next
            # 修改尾结点和头结点的循环指针
            node.next = self.__head
            self.__head.pre = node.next


6,在指定位置插入元素

找到要插入的位置的前一个结点的指针

修改前一个结点与新插入结点的双向指针

再修改新插入的结点与后一个结点的双向指针

    def insert(self, pos, item):
        # 位置pos在第一个元素之前,则在头部插入
        if pos <= 0:
            self.add(item)
            # 位置pos大于总长度,则在尾部插入
        elif pos > self.length():
            self.append(item)
        else:
            # 指定位置添加元素
            node = Node(item)
            count = 0
            cur = self.__head  # 当前指针
            # 循环找到要插入的位置的前一个结点指针位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next.pre = node.next
            node.pre = cur.next
            cur.next = node

7,修改指定位置的元素

    def modify(self, pos, item):
        """修改指定位置的元素"""
        # 当指定的位置pos小于等于0时,则修改头部元素
        if pos <= 0:
            self.__head.elem = item
        # 当pos大于等于链表总长度时,则修改尾部元素
        elif pos >= self.length():
            tail = self.__head
            # 循环让指针指向尾部元素
            while tail.next != self.__head:
                tail = tail.next
            tail.elem = item  # 修改尾部元素
        else:
            count = 0
            tail = self.__head
            # 循环指针找到指定的位置
            while count < pos:  # 1.当不满足条件退出循环时,说明指针已经指向了给定的pos位置
                tail = tail.next
                count += 1
            tail.elem = item  # 2.将pos位置的元素修改

8,删除元素

    def remove(self, item):
        # 删除节点
        cur = self.__head  # cur当前指针
        forword = None  # 前一个指针
        while cur.next != self.__head:
            # 找到了要删除的元素
            if cur.elem == item:
                # 要删除的元素就是第一个元素
                if cur == self.__head:
                    tail = self.__head
                    # 让tail指向最后一个元素
                    while tail.next != self.__head:
                        tail = tail.next
                    # 1.尾结点的next指向头结点的next(这个next指向第二个结点)
                    tail.next = cur.next
                    # 2.第二个结点的pre指向尾结点的next
                    cur.next.pre = tail.next
                    # 3.修改头指针指向第二个结点
                    self.__head = cur.next

                else:
                    forword.next = cur.next
                return
            # 未找到要删除的元素,指针向后走,继续遍历
            else:
                forword = cur
                cur = cur.next
        # 当上面的while循环不满足条件时(cur.next == self.__head),说明只有一个结点元素
        if cur.elem == item:
            if cur.next == self.__head:
                forword.next = self.__head

9、查找元素是否存在

    def search(self, item):
        # 查找节点是否存在
        cur = self.__head
        while cur.next != self.__head:
            # 找到了返回True,未回到指向下一个继续遍历
            if cur.elem == item:
                return True
            cur = cur.next
        # 查找的元素在最后一个,遍历后指向最后一个,但是没有进入循环,所以需要在循环体外判断一次
        if cur.elem == item:
            return True
        return False

三、完整代码

class Node():
    def __init__(self, elem):
        # 双向循环链表结点
        self.pre = None
        self.elem = elem
        self.next = None


class DoubleCircleLinkList():
    def __init__(self, node=None):
        self.__head = node
        if node:
            node.next = node  # 只有一个结点时,next指针指向自己,构成循环
            node.pre = node.next

    def is_empty(self):
        # 链表是否为空
        if self.__head is None:
            return True
        else:
            return False

    def length(self):
        # 链表长度
        if self.is_empty():
            return 0
        count = 0
        cur = self.__head
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
     # 遍历整个链表
        if self.is_empty():
            return
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem, end=' ')
            cur = cur.next
        print(cur.elem)

    def add(self, item):
        # 链表头部添加元素
        node = Node(item)
        if self.is_empty():
            # 是空链表头指针直接指向新结点
            self.__head = node
            # 修改新结点的next指向结点自己
            node.next = node
            # 新结点的pre指向结点自己的next构成一个结点的双向循环
            node.pre = node.next
        else:
            tail = self.__head
            # 循环找到尾结点
            while tail.next != self.__head:
                tail = tail.next
            # 1.新来的节点的next指向第一个头节点
            node.next = self.__head
            # 2.再改变第一个头节点的指针指向新节点的next
            self.__head.pre = node.next
            # 3.将尾指向指向添加node节点
            tail.next = node
            # 4.新结点pre指向尾结点的next
            node.pre = tail.next
            # 5.最后修改头指针指向新结点
            self.__head = node

    def append(self, item):
        # 链表尾部添加元素
        # 创建新结点
        node = Node(item)
        # 是空链表就把头节点指向这个节点
        if self.is_empty():
            self.__head = node
            node.next = node
            node.pre = node.next
        else:
            tail = self.__head
            # 找到尾节点
            while tail.next != self.__head:
                tail = tail.next
            # 修改尾结点与新结点的指针
            tail.next = node
            node.pre = tail.next
            # 修改尾结点和头结点的循环指针
            node.next = self.__head
            self.__head.pre = node.next

    def modify(self, pos, item):
        """修改指定位置的元素"""
        # 当指定的位置pos小于等于0时,则修改头部元素
        if pos <= 0:
            self.__head.elem = item
        # 当pos大于等于链表总长度时,则修改尾部元素
        elif pos >= self.length():
            tail = self.__head
            # 循环让指针指向尾部元素
            while tail.next != self.__head:
                tail = tail.next
            tail.elem = item  # 修改尾部元素
        else:
            count = 0
            tail = self.__head
            # 循环指针找到指定的位置
            while count < pos:  # 1.当不满足条件退出循环时,说明指针已经指向了给定的pos位置
                tail = tail.next
                count += 1
            tail.elem = item  # 2.将pos位置的元素修改

    def insert(self, pos, item):
        # 位置pos在第一个元素之前,则在头部插入
        if pos <= 0:
            self.add(item)
            # 位置pos大于总长度,则在尾部插入
        elif pos > self.length():
            self.append(item)
        else:
            # 指定位置添加元素
            node = Node(item)
            count = 0
            cur = self.__head  # 当前指针
            # 循环找到要插入的位置的前一个结点指针位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next.pre = node.next
            node.pre = cur.next
            cur.next = node

    def remove(self, item):
        # 删除节点
        cur = self.__head  # cur当前指针
        forword = None  # 前一个指针
        while cur.next != self.__head:
            # 找到了要删除的元素
            if cur.elem == item:
                # 要删除的元素就是第一个元素
                if cur == self.__head:
                    tail = self.__head
                    # 让tail指向最后一个元素
                    while tail.next != self.__head:
                        tail = tail.next
                    # 1.尾结点的next指向头结点的next(这个next指向第二个结点)
                    tail.next = cur.next
                    # 2.第二个结点的pre指向尾结点的next
                    cur.next.pre = tail.next
                    # 3.修改头指针指向第二个结点
                    self.__head = cur.next

                else:
                    forword.next = cur.next
                return
            # 未找到要删除的元素,指针向后走,继续遍历
            else:
                forword = cur
                cur = cur.next
        # 当上面的while循环不满足条件时(cur.next == self.__head),说明只有一个结点元素
        if cur.elem == item:
            if cur.next == self.__head:
                forword.next = self.__head

    def search(self, item):
        # 查找节点是否存在
        cur = self.__head
        while cur.next != self.__head:
            # 找到了返回True,未回到指向下一个继续遍历
            if cur.elem == item:
                return True
            cur = cur.next
        # 查找的元素在最后一个,遍历后指向最后一个,但是没有进入循环,所以需要在循环体外判断一次
        if cur.elem == item:
            return True
        return False


if __name__ == '__main__':
    ll = DoubleCircleLinkList()
    print(ll.is_empty())
    print(ll.length())
    ll.travel()

    print('add')
    ll.add(9)
    ll.travel()

    print('append')
    ll.append(13)
    ll.travel()
    ll.append(14)
    ll.travel()

    print('insert')
    ll.insert(2, 100)
    ll.travel()

    print('remove')
    ll.remove(9)
    ll.travel()

    print('modify')
    ll.modify(1, 200)
    ll.travel()

    print(ll.search(200))

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/13337.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

VS Code 插件开发概览

VS Code 插件开发概览 前言 VS Code作为开发者的代码开发利器&#xff0c;越来越受开发者的喜爱。像我身边的前端&#xff0c;每天80%的开发工作都是在VS Code上完成的。随着人们对它的使用&#xff0c;不再满足简单的优雅&#xff0c;舒服写代码这一基本需求。有些人利用它进…

阿里ARouter 路由框架解析

一、简介 众所周知&#xff0c;在日常开发中&#xff0c;随着项目业务越来越复杂&#xff0c;项目中的代码量也越来越多&#xff0c;如果维护、扩展、解耦等成了一个非常头疼问题&#xff0c;随之孕育而生的诸如插件化、组件化、模块化等热门技术。 而其中组件化中一项的难点&…

深入理解Linux多线程

致前行的人&#xff1a; 昨日渐多&#xff0c;明日愈少&#xff0c;今日还在&#xff0c;不要为成功而努力&#xff0c;要为做一个有价值的人而努力。人生道路上充满了坎坷&#xff0c;谁也不可能一帆风顺。只有在最困难的时刻&#xff0c;才能体会到无助的含义。 目录 1.理解…

SpringBoot集成MyBatis-yml自动化配置原理详解

SpringBoot集成MyBatis-yml自动化配置原理详解 简介&#xff1a;spring boot整合mybatis开发web系统目前来说是市面上主流的框架&#xff0c;每个Java程序和springboot mybatis相处的时间可谓是比和自己女朋友相处的时间都多&#xff0c;但是springboot mybatis并没有得到你的真…

适用于 Windows 的 5 个最好的 PDF 转换器应用程序

由于稳定性、高分辨率、高安全性、易于传输等特点&#xff0c;PDF已经成为我们日常工作中最常用的格式。我们在享受PDF带来便利的同时&#xff0c;也发现PDF带来了一些不便&#xff0c;其中最大的问题就是PDF内容的编辑难度。同时&#xff0c;并不是所有的文件都是PDF格式的&am…

代码优化- 前端优化

常量折叠 基本思想&#xff1a;在编译期间计算表达式的值&#xff08;编译时静态计算&#xff09; 例如&#xff1a;a 3 5 > a 8&#xff0c;if (true && false) ... > if (false) 好处是&#xff1a;语法树的节点数量减少了&#xff0c;意味着编译器要维护…

Ubuntu上跑通PaddleOCR

书接上文。刚才说到我已经在NUC8里灌上了Windows Server 2019。接下来也顺利的启用了Hyper-V角色并装好了一台Ubuntu 22.04 LTS 的虚机。由于自从上回在树莓派上跑通了Paddle-Lite-Demo之后想再研究一下PaddleOCR但进展不顺&#xff0c;因此决定先不折腾了&#xff0c;还是从x6…

【论文写作】如何写科技论文?万能模板!!!(以IEEE会议论文为例)

0. 写在前面 常言道&#xff0c;科技论文犹如“八股文”&#xff0c;有固定的写作模式。本篇博客主要是针对工程方面的论文的结构以及写作链条的一些整理&#xff0c;并不是为了提高或者润色一篇论文的表达。基本上所有的论文&#xff0c;都需要先构思好一些点子&#xff0c;有…

一文搞懂Session和JWT登录认证

前言 目前在开发的小组结课项目中用到了JWT认证&#xff0c;简单分享一下&#xff0c;并看看与Session认证的异同。 登录认证&#xff08;Authentication&#xff09;的概念非常简单&#xff0c;就是通过一定手段对用户的身份进行确认。 我们都知道 HTTP 是无状态的&#xf…

强化学习技巧

此软件包处于维护模式&#xff0c;请使用Stable-Baselines3 (SB3)获取最新版本。您可以在 SB3 文档中找到迁移指南。 本节的目的是帮助您进行强化学习实验。它涵盖了有关 RL 的一般建议&#xff08;从哪里开始、选择哪种算法、如何评估算法等&#xff09;&#xff0c;以及使用自…

【Linux】System V 共享内存、消息队列、信号量

&#x1f34e;作者&#xff1a;阿润菜菜 &#x1f4d6;专栏&#xff1a;Linux系统编程 system V共享内存介绍 System V 共享内存是一种进程间通信的机制&#xff0c;它允许多个进程共享一块物理内存区域&#xff08;称为“段”&#xff09;。System V 共享内存的优点是效率高&…

OTG是什么意思?

OTG是什么意思&#xff1f; OTG是怎么样实现的&#xff1f; TYPE-C接口的手机如何实现同时充电OTG功能&#xff1f; OTG是什么意思&#xff1f; OTG是On-The-Go的缩写&#xff0c;是一项新兴技术&#xff0c;主要应用于不同的设备或移动设备间的联接&#xff0c;进行数据交…

基于遥感的自然生态环境检测——实验三:生态因子提取

实验三&#xff1a;生态因子提取 一、实验目标 生态因子生成&#xff1b;生态因子归一化&#xff1b;生态环境评价 二、实验内容 根据经过大气校正后的影像生产土地覆盖指数、土壤指数以及坡度等&#xff0c;对土地覆盖指数、土壤指数以及坡度进行密度分割归一化&#xff1…

“SCSA-T学习导图+”系列:下一代防火墙

本期引言&#xff1a; 近年来&#xff0c;随着数字化业务带给我们高效和便捷的同时&#xff0c;信息暴露面的增加、网络边界的模糊化以及黑客攻击的产业化&#xff0c;使得网络安全事件相较以往成指数级增加。传统防火墙基于五元组的方式对进出网络的数据流量进行访问控制&…

JavaScript(JS)-1.JS基础知识

1.JavaScript概念 (1)JavaScript是一门跨平台&#xff0c;面向对象的脚本语言&#xff0c;来控制网页行为的&#xff0c;它能使网页可交互 (2)W3C标准&#xff1a;网页主要由三部分组成 ①结构&#xff1a;HTML负责网页的基本结构&#xff08;页面元素和内容&#xff09;。 …

【Linux网络服务】Linux网络设置

一、查看网络配置 1.1ifconfig 1.2ip a 1.3什么是mtu 最大传输单元MTU&#xff0c;是指网络能够传输的最大数据包大小&#xff0c;以字节为单位。MTU的大小决定了发送端一次能够发送报文的最大字节数。如果MTU超过了接收端所能够承受的最大值&#xff0c;或者是超过了发送路径…

EIGRP 配置,详解拓扑表,路由汇聚

1.3 EIGRP 拓扑&#xff0c;路由以及汇聚 1.3.1 实验目的 通过对 EIGRP 拓扑&#xff0c;路由以及汇聚相关实验的练习&#xff0c;掌握 EIGRP 建立拓扑信息的方式&#xff0c; 度量计算方法&#xff0c;如何调整度量&#xff0c;非等价负载均衡&#xff0c;以及 EIGRP 末节路…

做完自动化测试,但别让不会汇报毁了你...

pytest 是一个成熟的全功能Python测试工具&#xff0c;可以帮助您编写更好的程序。它与 python 自带的 unittest 测试框架类似&#xff0c;但 pytest 使用起来更简洁和高效&#xff0c;并且兼容 unittest 框架。pytest 能够支持简单的单元测试和复杂的功能测试&#xff0c;pyte…

Verilog带参数的`define用法

宏除了可以进行简单的文本替换,还可以像函数和任务一样传递指定多个参数分别对文本进行对应的替换. 示例1&#xff1a; define Disp(pa,pb,pc) \initial \begin \#1200; \$display("%d \n",(papbpc)); \$display(" data_ pa data_ pb data_ pc %d",(…

C#中用程序代码修改了datagridview中的数据,保存时只对光标当前行有保存解决办法

C#中DataGridView绑定了DataTable后&#xff0c;通过代码修改DataGridView中的数据&#xff0c;总有一行&#xff08;被修改过并被用户选中的行集合中索引为0的行&#xff09;不能被UpDate回数据库的问题和解决办法 长江黄鹤 2017-06-26 | 300阅读 | 1转藏 转藏全屏朗读分…
最新文章