python单链表:头插法、尾插法创建, 判空, 长度, 遍历, 增加3种, 查找2种, 修改2种, 删除2种_边充电边写代码的博客-程序员秘密_python描述链表的头插法

技术标签: python  链表  数据结构  

文章目录

前言

单链表是数据结构中为非常基础的内容,所以我们也来简单学一下喽^-^

一、单链表是什么?

单链表是存储、操作数据的一种基本结构,类似于只能单向遍历的列表,只是连接时靠结构体依次连接。

二、写代码时注意点:

1.关联性:将self.head赋值给临时变量时,改变变量由self.head带来的相关属性时,会改变self.head的相关属性。

2.防止遗失:加入元素时与删除元素时,先把后面的元素连接防止丢失后面数据。

3.小思路:查找与修改和删除代码类似均要找,我们写起来就可以类似的写,修改的核心思想是将指针指向到修改的那一个位置,删除的核心思想是到删除的前一个位置。(删除也可以将指针指向要删除的位置,将他下一位的值赋值给他,然后将他与他下一位的下一位连接即可)

4.小问题: 当按下标操作链表时,IndexError,要用户重新输入还是直接去搞首位末尾??? 前者判断让用户重新输入即可,个人兴趣就选择后者硬搞!

三、代码

1.每一个结点的创建

class Linknode:
    def __init__(self, data=None):
        self.data = data
        self.next = None

2.Linklist完整代码

class Linklist:
    def __init__(self):
        self.head = Linknode()  # 创建空链表

    # 头插法创建
    def head_create(self, li):
        self.head = Linknode(li[0])  # 赋值头结点
        for i in li[1:]:
            node = Linknode(i)
            node.next = self.head
            self.head = node  # 头指针指回链表开头
        print("头插法创建完毕!")

    # 尾插法创建·
    def tail_create(self, li):
        self.head = Linknode(li[0])  # 赋值头结点
        tail = self.head  # 头尾指针均指向头结点
        for i in li[1:]:
            node = Linknode(i)
            tail.next = node
            tail = node  # 尾指针指链表末尾
        print("尾插法创建完毕!")

    # 判空
    def is_empty(self):
        return self.head.data is None

    # 长度
    def length(self):
        p = self.head
        count = 0
        while p is not None:  # 判断结点是否为空
            count += 1
            p = p.next
        return count

    # 遍历
    def travel(self):
        p = self.head
        while p:
            print(p.data, end=' ')
            p = p.next
        print()

    # 头增加
    def increase_head(self, data):
        node = Linknode(data)
        if self.is_empty():
            self.head = node
        else:
            node.next = self.head
            self.head = node  # 头指针指回开头
        print("头增加完毕!")

    # 尾增加
    def increase_tail(self, data):
        node = Linknode(data)
        # 由于可能开始为空链表,就不能直接额在后加结点
        if self.is_empty():
            self.head = node
        else:
            p = self.head  # p为移动浮标
            while p.next is not None:
                p = p.next
            p.next = node
        print("尾增加完毕!")

    # 指定位置增加
    def increase_pos(self, pos, data):  # pos为下标位置
        if pos <= 0:
            self.increase_head(data)
        elif pos >= self.length():  # 包含了len == 0的情况
            self.increase_tail(data)
        else:
            p = self.head
            for _ in range(pos - 1):  # 走到要增加位置的前一个
                p = p.next
            node = Linknode(data)
            node.next = p.next  # 先连接后面的那个结点,防止后面结点丢失
            p.next = node
            print("指定增加完毕!")

    # 查找:返回第一个找到的位置
    def data_find_pos(self, data):
        p = self.head
        count = 0
        if self.is_empty():
            print("链表为空,未找到数据!")
        while p is not None:  # 遍历链表
            if p.data == data:
                return count  # 返回下标
            p = p.next
            count += 1
        print("未找到数据!")

    # 查找:返回指定位置的元素
    def pos_find_data(self, pos):  # pos为下标位置
        p = self.head
        length = self.length()
        if self.is_empty():
            print("链表为空,未找到数据!")
        if pos <= 0:  # 返回第一个元素
            return self.head.data
        elif pos >= length:  # 返回最后一个元素
            while p.next is not None:
                p = p.next
            return p.data
        else:  # 至少有一个元素且索引[1~len-1]
            for _ in range(pos):
                p = p.next
            return p.data

    # 删除:删除第一个找到的数据
    def delete_data(self, data):
        p = self.head
        if self.is_empty():
            print("链表为空,无法删除!")
        # 元素>=1
        elif self.length() == 1:  # 无法把指针指到要删去的上一个元素,所以讨论一下(除循环链表)
            if self.head.data == data:
                self.head = Linknode()  # 直接把它变为空链表
                # 如果self.head = self.head.next 会导致self.head == None影响后面的继续操作
                print("删除成功!")
            else:
                print("链表中没有要删除的数据!")
        else:
            # 链长>=2且找的不在首位置
            while p.next is not None:  # 遍历到要删除的前面一个位置
                if p.next.data == data:
                    p.next = p.next.next
                    print("删除成功!")
                    return
                p = p.next
            print("链表中没有要删除的数据!")

    # 删除:删除指定位置的数据
    def delete_pos(self, pos):  # pos为下标位置
        p = self.head
        length = self.length()
        if self.is_empty():
            print("链表为空,无法删除!")
            return
        # 1个元素及以上
        if pos <= 0 or length == 1:
            self.head = self.head.next
        # 2个元素及以上
        elif pos >= length:  # 删最后一个元素
            while p.next.next is not None:
                p = p.next
            p.next = None
        else:
            for _ in range(pos - 1):  # 走到要删的前一个位置
                p = p.next
            p.next = p.next.next
        print("删除成功!")

    # 修改:修改第一个找到的数据
    def revise_data(self, old_data, new_data):
        p = self.head
        length = self.length()
        if length == 0:
            print("链表为空,无法修改!")
            return
        while p is not None:  # 遍历链表
            if p.data == old_data:
                p.data = new_data
                print("修改成功!")
                return
            p = p.next
        print("未找到数据,无法修改!")

    # 修改:修改指定位置的元素
    def revise_pos_data(self, pos, data):  # pos为下标位置
        p = self.head
        length = self.length()
        count = 0
        if self.is_empty():
            print("链表为空,无法修改!")
        # 1个元素及以上
        if pos <= 0:  # 修改第一个
            self.head.data = data
            print("修改成功!")
        elif pos >= length:  # 修改最后一个元素
            while p.next is not None:
                p = p.next
            p.data = data
        else:  # 至少有一个元素且索引合法
            for _ in range(pos):  # 走到指定位置
                p = p.next
            p.data = data
        print("修改成功!")

3.代码测试

if __name__ == '__main__':
    link = Linklist()
    link.travel()  # None
    print(link.is_empty())  # True
    link.tail_create([2, 4, 3, 7, 1])  #尾插法创建完毕!
    print(link.is_empty())  # False
    print(link.length())  # 5
    link.travel()  # 2 4 3 7 1
    link.increase_tail(1)  # 尾增加完毕!
    link.travel()  # 2 4 3 7 1 1
    link.increase_head(1)  # 头增加完毕!
    link.travel()  # 1 2 4 3 7 1 1 
    link.increase_pos(2, 10)  # 指定增加完毕!
    link.travel()  # 1 2 10 4 3 7 1 1
    print(link.pos_find_data(2))  # 10
    print(link.data_find_pos(4))  # 3
    link.delete_data(2)  # 删除成功!
    link.travel()  # 1 10 4 3 7 1 1
    link.delete_pos(-100)  # 删除成功
    link.travel()  # 10 4 3 7 1 1 
    link.revise_data(1, 9)  # 修改成功!
    link.travel()  # 10 4 3 7 9 1 
    link.revise_pos_data(1, 6)  # 修改成功!
    link.travel()  # 10 6 3 7 9 1 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_57613791/article/details/123161225

智能推荐

搜狗拼音带来的俩个烦人的弹窗解决方法_zhaojiafu666的博客-程序员秘密_装了搜狗拼音后文件资源管理器老是跳出弹窗

文章目录1、搜狐的新闻2、提示安装搜狗浏览器清理垃圾解决办法,按ctrl + alt 就会关闭了。1、搜狐的新闻进入你安装的搜狗拼音的目录下,进入数字的文件夹,把SohuNews 这个选中它,shift+delete,将它彻底删除。直接delete还会出来,这样就解决了。2、提示安装搜狗浏览器清理垃圾我没安装搜狗浏览器,却是弹窗显示搜狗浏览器说要清理垃,这个就很烦人了,而且我点击关闭...

启动计算机按住del不放,win10系统重置后无法开机提示PReSS CRTL+ALT+DeL TO ReSTART的解决方法..._weixin_39844515的博客-程序员秘密

很多小伙伴都遇到过win10系统重置后无法开机提示PRESS CRTL+ALT+DEL TO RESTART的困惑吧,一些朋友看过网上零散的win10系统重置后无法开机提示PRESS CRTL+ALT+DEL TO RESTART的处理方法,并没有完完全全明白win10系统重置后无法开机提示PRESS CRTL+ALT+DEL TO RESTART是如何解决的,今天小编准备了简单的解决办法,只需要...

linux中设置fcitx使用shift切换中英文输入法_Alex Creation的博客-程序员秘密_trigger input method

选择屏幕右上角输入法标志选择"configure" -&gt; 选择"Global Config" -&gt; 勾选最下边的"Show Advance Option" -&gt; 按照下图将"Extra key for trigger input method"选项选择为"SHIFT Both"

编译tomcat native_wangpingfang的博客-程序员秘密

1    准备tomcat-native依赖apr, openssl和jdk。 下载oracle jdk,在linux下使用如下命令,下载:wget --no-check-certificate --no-cookies--header "Cookie: oraclelicense=accept-securebackup-cookie"http://download.ora

python单纯形法求解线性规划问题_Time ??的博客-程序员秘密_单纯形法时间复杂度

单纯形法求解线性规划问题概念线性规划(Linear programming),是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。数学模型(1)列出约束条件及目标函数(2)画出约束条件所表示的可行域(3)在可行域内求目标函数的最优解及最优值线性规划的标准型一...

sql从查询结果创建一个临时表_wangqi0079的博客-程序员秘密_查询表结构并创建临l时表

从查询结果创建一个临时表临时表随数据库的关闭而自动消失,不占内存空间。创建临时表的方法与创建永久表的方法相似,只不过在新表的名称前加一个“#”号或两个“##”号。一个“#”号表示创建的是局部的临时表;两个“##”号表示创建的是全局临时表。示例:在“course”表中,把查询“课程类别”是“艺术类”的结果保存到临时表“##newltable”中,并查看“##newtable”表的信息。在

随便推点

Firefox 打开谷歌页面提示“检测到该服务器正在将此地址的请求循环重定向”的完美解决方法 (转)_xuan2717的博客-程序员秘密_请求无限循环重定向

Firefox 打开谷歌页面提示“检测到该服务器正在将此地址的请求循环重定向”的完美解决方法 (转)

计算机网络——应用层_「已注销」的博客-程序员秘密

1 网络应用体系结构(1)客户机/服务器结构(2)纯P2P结构没有永远在线的服务器 节点间歇性接入网路 节点可能改变网络优点:高度可伸缩缺点:难于管理(3)混合结构以上两种结构混合在一起使用例:Napster,一种提供线上音乐服务的软体文件传输使用P2P结构 文件搜索采用C/S结构2 网络应用进程通信不同主机上运行的进程如何通信呢?消息交...

win10+3070+cuda11.2搭建飞桨paddleServing及测试_北风萧瑟为谁寒的博客-程序员秘密_win10 飞浆

实际安装方案软硬件环境七彩虹3070 ultra wwin10Anaconda3-2020.11-Windows-x86_64.exe461.72-desktop-win10-64bit-international-dch-whql.execuda_11.2.1_461.09_win10.execudnn-11.2-windows-x64-v8.1.1.33.zip链接:https://pan.baidu.com/s/1KaO_tbsEXkv2G-OIFAlxQA提取码:9vae–来自百

1024程序猿节,记录下_创创大帝(水印很浅-下载的文档)的博客-程序员秘密

1024程序节,记录下一晃又过去了大半年了作为一个程序员,继续加油~

QT实现OPENGL三维画图(视角可调整)_三十而学的博客-程序员秘密

QT实现OPENGL画图继承QOpenGLWidget和QOpenGLFunctions实现自定义窗口类。重写QOpenGLWidget的虚函数void paintGL() override;void initializeGL() override;void mouseMoveEvent(QMouseEvent*)override;void mousePressEvent(QMouseE...

分享10个Github上排名前10的技术教程+开源项目,值得你收藏深入研究,用来丰富简历绰绰有余!_前程有光的博客-程序员秘密

前言每年都有很多程序员想跳槽,心有余而力不足,只因项目经验不足,大厂梦便止步于此,想增加项目经验却又受限于公司我经常逛github,发现了一些优秀的技术教程和开源项目,其中的框架及代码非常不错,我便做了一个资源整合,完结后做成了一个文档,对于想要提升自身项目经验的小伙伴一定会有很大的帮助。让我们来看部分内容展示:开始之前,记得点赞收藏加关注哦 ,需要下载PDF版本和获取更多知识点、面试题的朋友可以点一点下方链接免费领取了,点击这里备注csdn即可自行下载,希望对你们有帮助商城系统下面的商城