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

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

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

单向链表模型:

2019-04-03-22_17_36.png

链表是一个个节点连接而成,节点由两部分构成:元素域、链接域;链接域链接下一个节点,从而构成一条链条,而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


2019-04-03-22_17_36.png


相关文章
|
3天前
|
算法 开发者 计算机视觉
燃爆全场!Python并查集:数据结构界的网红,让你的代码炫酷无比!
在编程的世界里,总有一些数据结构以其独特的魅力和高效的性能脱颖而出,成为众多开发者追捧的“网红”。今天,我们要介绍的这位明星,就是Python中的并查集(Union-Find)——它不仅在解决特定问题上大放异彩,更以其优雅的设计和强大的功能,让你的代码炫酷无比,燃爆全场!
10 0
|
2天前
|
存储 索引 Python
反转Python列表的4种方法
反转Python列表的4种方法
10 2
|
4天前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
3天前
|
Python
深入解析 Python 中的对象创建与初始化:__new__ 与 __init__ 方法
深入解析 Python 中的对象创建与初始化:__new__ 与 __init__ 方法
10 1
|
1天前
|
安全 数据安全/隐私保护 开发者
保护敏感数据:使用Python加密数据的实用方法
保护敏感数据是一项基本的安全实践,Python通过上述库提供了强大的加密工具来实现这一目标。选择哪种方法取决于具体的应用场景和安全需求:对称加密(如AES)适合快速处理大量数据,而非对称加密(如RSA)更适合安全地交换密钥或进行身份验证。哈希函数则用于验证数据的完整性和一致性。通过合理使用这些技术,开发者可以大大增强其应用程序的安全性。
9 0
|
2天前
|
算法 Java C语言
【数据结构】后缀(逆波兰)表达式的计算以及中缀转后缀的方法
【数据结构】后缀(逆波兰)表达式的计算以及中缀转后缀的方法
12 0
|
2天前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
在数据结构的广袤领域中,图是一种强大而复杂的结构,而深度优先搜索(DFS)和广度优先搜索(BFS)则是遍历图的两把利剑。Python 以其简洁和强大的特性,为我们提供了实现和运用这两种算法的便捷途径。
15 0
|
3天前
|
Python
深入理解Python中的类方法、类实例方法和静态方法
深入理解Python中的类方法、类实例方法和静态方法
8 0
|
3天前
|
程序员 Python 容器
python 中的 collections 模块:常用数据结构和工具详解
python 中的 collections 模块:常用数据结构和工具详解
6 0
|
3天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
77 64