python实现单向链表数据结构及其基本方法

简介: 顺序表和链表作为线性表的典型结构,上一篇已经说了顺序表在python中的典型应用:list和tuple,《顺序表数据结构在python中的应用》,今天来实现链表的基本结构之一:单向链表。单向链表模型:链表是一个个节点连接而成,节点由两部分构成:元素域、链接域;链接域链接下一个节点,从而构成一条链条,而python主要实现单个节点对象,从而构成链条。

顺序表和链表作为线性表的典型结构,上一篇已经说了顺序表在python中的典型应用:list和tuple,《顺序表数据结构在python中的应用》,今天来实现链表的基本结构之一:单向链表。

单向链表模型:

链表是一个个节点连接而成,节点由两部分构成:元素域、链接域;链接域链接下一个节点,从而构成一条链条,而python主要实现单个节点对象,从而构成链条。

python实现一个节点对象:

class node:
    def __init__(self, item):
        self.item = item  # 该节点值
        self.next = None   #  连接一下一个节点
AI 代码解读


定义一个链条对象:

class SinglyLinkedList:
    """链表对象"""
    def __init__(self):
        self._head = None
AI 代码解读


链表对象从头部开始,链接一个个节点,下面我们添加一个在头部和尾部增加节点的方法。

class Node:
    def __init__(self, item):
        self.item = item  # 该节点值
        self.next = None   #  连接一下一个节点


class SinglyLinkedList:
    """链表对象"""
    def __init__(self):
        self._head = None

    def add(self, item):
        """
        头部添加节点
        :param item: 节点值
        :return:
        """
        node = Node(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        """
        尾部添加节点
        :param items:
        :return:
        """
        cur = self._head
        if not cur:  # 判断是否为空链表
            self.add(item)
        else:
            node = Node(item)
            while cur.next:
                cur = cur.next
            cur.next = node
AI 代码解读


其中注意在尾部添加节点的时候要判断是否为空链表,如果是空链表就直接用头部添加方法,如果不是空链表,那么需要遍历到最后一个节点上添加节点。

那我们给链表添加一些实现属性的方法,是否为空、链表长度、遍历链表等。

class Node:
    def __init__(self, item):
        self.item = item  # 该节点值
        self.next = None   #  连接一下一个节点


class SinglyLinkedList:
    """链表对象"""
    def __init__(self):
        self._head = None

    @property
    def is_empty(self):
        """
        判断链表是否为空,只需要看头部是否有节点
        :return:
        """
        if self._head:
            return False
        else:
            return True

    @property
    def length(self):
        """
        获取链表长度
        :return:
        """
        cur = self._head
        n = 0
        if not cur:
            return n
        else:
            while cur.next:
                cur = cur.next
                n += 1
            return n+1

    def ergodic(self):
        """
        遍历链表
        :return:
        """
        cur = self._head
        if not cur:
            print('None')
        else:
            while cur.next:
                print(cur.item)
                cur = cur.next
            print(cur.item)
AI 代码解读


接下来继续增加我们链表的插入节点和删除节点以及判断节点是否存在的方法。

class Node:
    def __init__(self, item):
        self.item = item  # 该节点值
        self.next = None   #  连接一下一个节点


class SinglyLinkedList:
    """链表对象"""
    def __init__(self):
        self._head = None

    def insert(self, index, item):
        """
        在指定位置插入节点(设置索引从0开始)
        :param item:
        :return:
        """
        if index == 0:  # 当索为0则头部插入
            self.add(item)
        elif index >= self.length:  # 当索引超范围则尾部插入
            self.append(item)
        else:  # 找到插入位置的上一个节点,修改上一个节点的next属性
            cur = self._head
            n = 1
            while cur.next:
                if n == index:
                    break
                cur = cur.next
                n += 1
            node = Node(item)
            node.next = cur.next
            cur.next = node

    def deltel(self, item):
        """
        删除节点
        :param item:
        :return:
        """
        if self.is_empty:  # 节点为空的情况
            raise ValueError("null")
        cur = self._head
        pre = None  # 记录删除节点的上一个节点
        if cur.item == item:  # 当删除节点为第一个的情况
            self._head = cur.next
        while cur.next:
            pre = cur
            cur = cur.next
            if cur.item == item:
                pre.next = cur.next

    def search(self, item):
        """
        查找节点是否存在
        :param item:
        :return:
        """
        cur = self._head
        while None != cur:
            if cur.item == item:
                return True
            cur = cur.next
        return False
AI 代码解读


依此类推,我们可以像列表的方法一下来实现节点的方法,比如还可以设置查找索引,修改节点值等方法,这种数据数据结构和列表使用方法一样,只不过列表是python内部已经实现了相关的方法,如果要在python中使用链表,那么我们应该编写自己的链表数据结构,导入即可使用。

完整源码见下:

class Node:
    def __init__(self, item):
        self.item = item  # 该节点值
        self.next = None   #  连接一下一个节点


class SinglyLinkedList:
    """链表对象"""
    def __init__(self):
        self._head = None

    def add(self, item):
        """
        头部添加节点
        :param item: 节点值
        :return:
        """
        node = Node(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        """
        尾部添加节点
        :param items:
        :return:
        """
        cur = self._head
        if not cur:  # 判断是否为空链表
            self.add(item)
        else:
            node = Node(item)
            while cur.next:
                cur = cur.next
            cur.next = node

    @property
    def is_empty(self):
        """
        判断链表是否为空,只需要看头部是否有节点
        :return:
        """
        if self._head:
            return False
        else:
            return True

    @property
    def length(self):
        """
        获取链表长度
        :return:
        """
        cur = self._head
        n = 0
        if not cur:
            return n
        else:
            while cur.next:
                cur = cur.next
                n += 1
            return n+1

    def ergodic(self):
        """
        遍历链表
        :return:
        """
        cur = self._head
        if not cur:
            print('None')
        else:
            while cur.next:
                print(cur.item)
                cur = cur.next
            print(cur.item)

    def insert(self, index, item):
        """
        在指定位置插入节点(设置索引从0开始)
        :param item:
        :return:
        """
        if index == 0:  # 当索为0则头部插入
            self.add(item)
        elif index >= self.length:  # 当索引超范围则尾部插入
            self.append(item)
        else:  # 找到插入位置的上一个节点,修改上一个节点的next属性
            cur = self._head
            n = 1
            while cur.next:
                if n == index:
                    break
                cur = cur.next
                n += 1
            node = Node(item)
            node.next = cur.next
            cur.next = node

    def deltel(self, item):
        """
        删除节点
        :param item:
        :return:
        """
        if self.is_empty:  # 节点为空的情况
            raise ValueError("null")
        cur = self._head
        pre = None  # 记录删除节点的上一个节点
        if cur.item == item:  # 当删除节点为第一个的情况
            self._head = cur.next
        while cur.next:
            pre = cur
            cur = cur.next
            if cur.item == item:
                pre.next = cur.next

    def search(self, item):
        """
        查找节点是否存在
        :param item:
        :return:
        """
        cur = self._head
        while None != cur:
            if cur.item == item:
                return True
            cur = cur.next
        return False
AI 代码解读



目录
打赏
0
1
0
0
760
分享
相关文章
|
2月前
|
Python技术解析:了解数字类型及数据类型转换的方法。
在Python的世界里,数字并不只是简单的数学符号,他们更多的是一种生动有趣的语言,用来表达我们的思维和创意。希望你从这个小小的讲解中学到了有趣的内容,用Python的魔法揭示数字的奥秘。
77 26
|
2月前
|
在VScode环境下配置Python环境的方法
经过上述步骤,你的VSCode环境就已经配置好了。请尽情享受这扇你为自己开启的知识之窗。如同你在冒险世界中前行,你的探索之路只有越走越广,你获得的知识只会越来越丰富,你的能力只会越来越强。
181 37
解决Python requests库POST请求参数顺序问题的方法。
总之,想要在Python的requests库里保持POST参数顺序,你要像捋顺头发一样捋顺它们,在向服务器炫耀你那有条不紊的数据前。抓紧手中的 `OrderedDict`与 `json`这两把钥匙,就能向服务端展示你的请求参数就像经过高端配置的快递包裹,里面的商品摆放井井有条,任何时候开箱都是一种享受。
50 10
|
2月前
|
Python 中__new__方法详解及使用
__new__ 是 Python 中用于创建类实例的静态方法,在实例化对象时优先于 __init__ 执行。它定义在基础类 object 中,需传递 cls 参数(表示当前类)。__new__ 可决定是否使用 __init__ 方法或返回其他对象作为实例。特性包括:1) 在实例化前调用;2) 始终为静态方法。示例中展示了其用法及 Python2 和 Python3 的差异,强调了参数处理的不同。
96 10
python__init__方法笔记
本文总结了Python中`__init__`方法的使用要点,包括子类对父类构造方法的调用规则。当子类未重写`__init__`时,实例化会自动调用父类的构造方法;若重写,则需通过`super()`或直接调用父类名称来显式继承父类初始化逻辑。文中通过具体代码示例展示了不同场景下的行为及输出结果,帮助理解类属性与成员变量的关系,以及如何正确使用`super()`实现构造方法的继承。
102 9
[oeasy]python093_find方法_指数为负数_index_实际效果
本文介绍了Python中`find`方法与索引(index)的使用,包括负数索引的实际效果。回顾了`eval`函数的应用,并强调类名如`str`、`int`、`list`不可用作变量名以避免覆盖。通过示例解析了负数索引在字符串和列表中的作用,以及`index`方法的三个参数(value、start、stop)的用法。同时对比了`index`和`find`方法的区别:`index`找不到子串时抛出`ValueError`,而`find`返回-1。最后总结了正负索引的使用场景及两者的特性,提供了相关学习资源链接。
307 8
|
2月前
|
Python 中__new__方法详解及使用
`__new__` 是 Python 中的一个特殊方法,用于控制对象的创建过程,在 `__init__` 之前执行。它是类的静态方法,负责返回一个实例。如果 `__new__` 不返回对象,`__init__` 将不会被调用。本文详细介绍了 `__new__` 的作用、特性及与 `__init__` 的区别,并通过实例演示了其在单例模式中的应用,同时对比了 Python2 和 Python3 中的写法差异。
Python 高级编程与实战:深入理解性能优化与调试技巧
本文深入探讨了Python的性能优化与调试技巧,涵盖profiling、caching、Cython等优化工具,以及pdb、logging、assert等调试方法。通过实战项目,如优化斐波那契数列计算和调试Web应用,帮助读者掌握这些技术,提升编程效率。附有进一步学习资源,助力读者深入学习。
用Python编程基础提升工作效率
一、文件处理整明白了,少加两小时班 (敲暖气管子)领导让整理100个Excel表?手都干抽筋儿了?Python就跟铲雪车似的,哗哗给你整利索!
81 11
[oeasy]python081_ai编程最佳实践_ai辅助编程_提出要求_解决问题
本文介绍了如何利用AI辅助编程解决实际问题,以猫屎咖啡的购买为例,逐步实现将购买斤数换算成人民币金额的功能。文章强调了与AI协作时的三个要点:1) 去除无关信息,聚焦目标;2) 将复杂任务拆解为小步骤,逐步完成;3) 巩固已有成果后再推进。最终代码实现了输入验证、单位转换和价格计算,并保留两位小数。总结指出,在AI时代,人类负责明确目标、拆分任务和确认结果,AI则负责生成代码、解释含义和提供优化建议,编程不会被取代,而是会更广泛地融入各领域。
136 28

推荐镜像

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问