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

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

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

单向链表模型:

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

python实现一个节点对象:

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


定义一个链条对象:

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


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

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


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

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

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)


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

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


依此类推,我们可以像列表的方法一下来实现节点的方法,比如还可以设置查找索引,修改节点值等方法,这种数据数据结构和列表使用方法一样,只不过列表是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



相关文章
|
29天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
95 4
|
26天前
|
存储 索引 Python
Python编程数据结构的深入理解
深入理解 Python 中的数据结构是提高编程能力的重要途径。通过合理选择和使用数据结构,可以提高程序的效率和质量
134 59
|
26天前
|
存储 开发者 Python
Python 中的数据结构与其他编程语言数据结构的区别
不同编程语言都有其设计理念和应用场景,开发者需要根据具体需求和语言特点来选择合适的数据结构
|
3天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
41 20
|
26天前
|
存储 开发者 索引
Python 中常见的数据结构
这些数据结构各有特点和适用场景,在不同的编程任务中发挥着重要作用。开发者需要根据具体需求选择合适的数据结构,以提高程序的效率和性能
|
26天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
26天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
2月前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
30 3
|
2月前
|
存储 算法 Java
数据结构与算法学习八:前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式的学习,中缀转后缀的两个方法,逆波兰计算器的实现
前缀(波兰)表达式、中缀表达式和后缀(逆波兰)表达式的基本概念、计算机求值方法,以及如何将中缀表达式转换为后缀表达式,并提供了相应的Java代码实现和测试结果。
131 0
数据结构与算法学习八:前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式的学习,中缀转后缀的两个方法,逆波兰计算器的实现
|
2月前
|
存储
ES6中的Set数据结构的常用方法和使用场景
ES6中的Set数据结构的常用方法和使用场景