【Python编程挑战】:单链表实现技巧与最佳实践

简介: 【Python编程挑战】:单链表实现技巧与最佳实践

🚀一、单链表的概念

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

链表是由一个个结点组成,每个结点之间通过链接关系串联起来,每个结点都有一个后继结点,最后一个结点的后继结点为空结点。

6e8c722fd495b5650b3a49da5aa43ad6_ac0116d28f8642768a708e6b00187a69.png


每个结点只设置一个指向后继结点的指针属性,这样的链表成为线性单项链接表,简称单链表;如果每个结点中设置两个指针属性,分别在于指向其前驱结点和后继结点,这样的链表称为线性双向链接表,简称双链表。无前驱结点或则后继结点的相应指针属性用常量None表示。

c21c5b75fa06f049b35c6b6a5e9de414_707c83f622584081b37d24f819df9e4b.png

注意:在Python中并不存在指针的概念,这里的指针属性实际上存放的是后继结点或者前驱结点的引用,但是为了表述方便仍然会采用 “指针” 一词。


🌈二、单链表的实现

⭐1. 单链表结点类

在单链表中,假定每个结点为LinkNode类对象,它包括存储元素的数据成员,这里用data表示,还包括存储后继结点的指针属性,这里用next表示。LinkNode的定义:

# 单链表结点类
class LinkNode:
    def __init__(self, data=None):
        self.data = data
        self.next = None

设计单链表类为LinkList,其中head属性为单链表的头结点,构造方法用于创建 这个头结点,并且设置head结点的next为空:

# 单链表类
class LinkList:
    def __init__(self):
        self.head = LinkNode()
        self.head.next = None


🎬2. 插入和删除操作

1、元素插入的概念

单向链表的元素插入,就是指给定一个索引 i 和一个元素 data,生成一个值为 data 的结点,并且插入到第 i 个位置上。


(1)、插入结点操作

p(即 pre)代表目前正在遍历的结点,当计数到 3 的时候,p 的后继结点 a (即 aft)也找到了,然后生成值为 5 的结点 vtx,将 p 的后继指向 vtx,将 vtx 的后继指向 a。

a85ee9fd4702920abdcc76205caea88c_fbce8de04672adad3655441896058ee5.gif

步骤:


  • 第1步:判断插入位置是否合法,如果不合法则抛出异常(比如:原本只有5个元素,给定的索引是100,那显然这个位置是不合法的)。
  • 第2步:对给定的元素,生成一个链表结点。
  • 第3步:如果插入位置是 0,则直接把生成的结点的后继结点,设置为当前的链表头结点,并且把生成的结点设置为新的链表头。
  • 第4步:如果插入位置不是 0,则遍历到插入位置的前一个位置,把生成的结点插入进来。
  • 第5步:更新链表的大小,即对链表的大小执行加一操作。

头插法:

# 头插法: 由数组a整体建立单链表
def CreateListF(self, a):
    for i in range(0, len(a)):
        s = LinkNode(a[i])
        s.next = self.head.next
        self.head.next = s

尾插法:

# 尾插法: 由数组a整体建立单链表
def CreateListR(self, a):
    t = self.head
    for i in range(0, len(a)):
        s = LinkNode(a[i])
        t.next = s
        t = s
    t.next = None

任意位置插入:

# 在线性表中序号为i的位置插入元素e
def Insert(self, i, e):
    assert i >= 0
    s = LinkNode(e)
    p = self.geti(i - 1)
    assert p is not None
    s.next = p.next
    p.next = s

上述指针修改用Python语句描述:

s.next = p.next

p.next = s

注意:这两个语句的顺序不能颠倒,如果先执行p.next = s语句,会找不到指向插入位置的下一个结点,再执行s.next = p.next语句,相当于执行s.next = s,导致插入操作错误。


2、元素删除的概念

单向链表的元素删除,就是指给定一个索引 i,将从链表头开始数到的第 i 个结点删除。


(1)、删除结点操作

删除运算是删除单链表中p结点的后继结点,就是将p结点的next修改为其后继结点的后继结点。


cba0f8a05dd2832889bbf5e607dbf0c8_7b814e2f3d10d7ea06f6b3af5ef21b9c.gif

步骤:


  • 第1步:判断删除位置是否合法,如果不合法则抛出异常。
  • 第2步:如果删除位置为首个结点,直接把链表头更新为它的后继结点。
  • 第3步:如果删除位置非首个结点,则遍历到要删除位置的前一个结点,并且把前一个结点的后继结点设置为它后继的后继。
  • 第4步:更新链表的大小,也就是将链表的大小执行减一操作。
# 在线性表中删除序号i的位置的元素
def Delete(self, i):
    assert i >= 0
    p = self.geti(i - 1)
    assert p.next is not None
    p.next = p.next.next

💥3. 元素查找

1、元素查找的概念

单向链表的元素查找,是指在链表中查找指定元素 x 是否存在,如果存在则返回该结点,否则返回 NULL。由于需要遍历整个链表进行元素对比,所以查找的时间复杂度为 O(n) 。

9665913ecaca2e1a7ea72a50186593da_c1f67574018d60262632d682d1731f9f.gif

2、元素查找的步骤


  • 第1步:遍历整个链表,对链表中的每个元素,和指定元素进行比较,如果相等则返回当前遍历到的结点;
  • 第2步:如果遍历完整个链表,都没有找到相等的元素,则返回 NULL。
# 求序号i的元素
def __getitem__(self, i):
    assert i >= 0
    p = self.geti(i)
    assert p is not None
    return p.data

❤️4. 单向链表的元素索引

1、元素索引的概念

单向链表的元素索引,是指给定一个索引值 i,从链表头结点开始数,数到第 i 个结点并且返回它,时间复杂度 O(n)。

2、元素索引的步骤


  • 第1步:首先判断给定的索引是否合法,不合法就抛出异常。
  • :直接通过索引访问即可获得对应的元素。

# 查找第一个为e的元素的序号
def GetNo(self, e):
    j = 0
    p = self.head.next
    while p is not None and p.data != e:
        j += 1
        p = p.next
    if p is None:
        return -1
    else:
        return j
☔5. 单向链表的元素修改

1、元素修改的概念

单向链表的元素修改是指将链表中指定索引的元素更新为新的值。

2、元素修改的步骤

  • 第1步:直接通过索引访问即可获得对应的结点,修改成指定的值。

19124f910ddaeec95072f24ed5894dd3_3cf15161fdc981623aa3a24f3fcb672f.gif

# 设置序号为i的元素
def __setitem__(self, i, x):
    assert i >= 0
    p = self.geti(i)
    assert p is not None
    p.data = x

返回序号为i的结点

返回序号为i的结点

# 返回序号为i的结点
👊6. 输出单链表

顾名思义就是一次便利单链表中各数据结点并输出结点值。

# 输出线性表
def display(self):
    p = self.head.next
    while p is not None:
        print(p.data, end=' ')
        p = p.next
    print()

时间复杂度为O(n),n表示顺序表中的元素个数。

🚀三、完整代码

# 单链表结点类
class LinkNode:
    def __init__(self, data=None):
        self.data = data
        self.next = None


# 单链表类
class LinkList:
    def __init__(self):
        self.head = LinkNode()
        self.head.next = None

    # 头插法: 由数组a整体建立单链表
    def CreateListF(self, a):
        for i in range(0, len(a)):
            s = LinkNode(a[i])
            s.next = self.head.next
            self.head.next = s

    # 尾插法: 由数组a整体建立单链表
    def CreateListR(self, a):
        t = self.head
        for i in range(0, len(a)):
            s = LinkNode(a[i])
            t.next = s
            t = s
        t.next = None

    # 返回序号为i的结点
    def geti(self, i):
        p = self.head
        j = -1
        while j < i and p is not None:
            j += 1
            p = p.next
        return p

    # 在线性表的末尾添加一个元素e
    def Add(self, e):
        s = LinkNode(e)
        p = self.head
        while p.next is not None:
            p = p.next
        p.next = s

    # 返回长度
    def getsize(self):
        p = self.head
        cnt = 0
        while p.next is not None:
            cnt += 1
            p = p.next
        return cnt

    # 求序号i的元素
    def __getitem__(self, i):
        assert i >= 0
        p = self.geti(i)
        assert p is not None
        return p.data

    # 设置序号为i的元素
    def __setitem__(self, i, x):
        assert i >= 0
        p = self.geti(i)
        assert p is not None
        p.data = x

    # 查找第一个为e的元素的序号
    def GetNo(self, e):
        j = 0
        p = self.head.next
        while p is not None and p.data != e:
            j += 1
            p = p.next
        if p is None:
            return -1
        else:
            return j

    # 在线性表中序号为i的位置插入元素e
    def Insert(self, i, e):
        assert i >= 0
        s = LinkNode(e)
        p = self.geti(i - 1)
        assert p is not None
        s.next = p.next
        p.next = s

    # 在线性表中删除序号i的位置的元素
    def Delete(self, i):
        assert i >= 0
        p = self.geti(i - 1)
        assert p.next is not None
        p.next = p.next.next

    # 输出线性表
    def display(self):
        p = self.head.next
        while p is not None:
            print(p.data, end=' ')
            p = p.next
        print()

🚲四、代码验证

if __name__ == '__main__':
    L = LinkList()
    print('建立空单链表L')
    a = [1, 2, 3, 4, 5, 6]
    print('1~6创建L')
    L.CreateListR(a)
    print('L[长度 = %d]: ' % (L.getsize()), end=' '), L.display()
    print('插入6~10')
    for i in range(6, 11):
        L.Add(i)
    print('L[长度 = %d]: ' % (L.getsize()), end=' '), L.display()
    print('序号为2的元素 = %d' % (L[2]))
    print('设置序号为2的元素为20')
    L[2] = 20
    print('L[长度 = %d]: ' % (L.getsize()), end=' '), L.display()
    x = 6
    print('第一个值为%d的元素序号 = %d' % (x, L.GetNo(x)))
    n = L.getsize()
    for i in range(n - 2):
        print('删除首元素')
        L.Delete(0)
        print('L[长度 = %d]: ' % (L.getsize()), end=' '), L.display()

594c022f4f777cefa02652f1c9e070e0_b5c4608c519f4f74abe2c77b13c037f3.png

相关文章
|
12天前
|
安全 Python
告别低效编程!Python线程与进程并发技术详解,让你的代码飞起来!
【7月更文挑战第9天】Python并发编程提升效率:**理解并发与并行,线程借助`threading`模块处理IO密集型任务,受限于GIL;进程用`multiprocessing`实现并行,绕过GIL限制。示例展示线程和进程创建及同步。选择合适模型,注意线程安全,利用多核,优化性能,实现高效并发编程。
26 3
|
14天前
|
开发者 Python
Python元类实战:打造你的专属编程魔法,让代码随心所欲变化
【7月更文挑战第7天】Python的元类是编程的变形师,用于创建类的“类”,赋予代码在构建时的变形能力。
34 1
|
15天前
|
设计模式 存储 Python
Python元类大揭秘:从理解到应用,一步步构建你的编程帝国
【7月更文挑战第6天】Python元类是创建类的对象的基石,允许控制类的生成过程。通过自定义元类,可在类定义时动态添加方法或改变行为。
20 0
|
10天前
|
数据采集 存储 API
Python虚拟环境数据共享技术解析:最佳实践与常见误区
本文探讨了Python爬虫开发中如何在虚拟环境中管理数据,提倡使用共享目录、数据库和API进行数据共享。通过创建虚拟环境、安装依赖并提供一个使用代理IP爬取微博数据的示例,阐述了如何配置代理、解析网页及保存数据到共享路径。强调了避免硬编码路径、忽视依赖管理和数据安全性的误区。
32 11
Python虚拟环境数据共享技术解析:最佳实践与常见误区
|
12天前
|
数据采集 大数据 数据安全/隐私保护
Python编程:如何有效等待套接字的读取与关闭
Python网络编程中,套接字事件处理至关重要。利用`selectors`模块和代理IP能增强程序的稳定性和可靠性。代码示例展示了如何通过代理连接目标服务器,注册套接字的读写事件并高效处理。在代理IP配置、连接创建、事件循环及回调函数中,实现了数据收发与连接管理,有效应对网络爬虫或聊天应用的需求,同时保护了真实IP。
Python编程:如何有效等待套接字的读取与关闭
|
3天前
|
Python
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
【7月更文挑战第18天】并查集,数据结构超级英雄,用于不相交集合的合并与查询。Python实现包括初始化、查找根节点和合并操作。应用广泛,如社交网络分析、图论问题、集合划分等。示例代码展示了解决岛屿数量问题,统计连通的“1”单元格数。掌握并查集,提升编程效率,解决复杂问题。
20 6
|
2天前
|
存储 开发者 Python
从理论到实践:Python中Trie树与Suffix Tree的完美结合,开启编程新篇章!
【7月更文挑战第19天】在编程实践中,Trie树和Suffix Tree优化了字符串处理。Trie树用于快速拼写检查,如在构建词库后,能高效判断单词是否存在。Suffix Tree则助力文本相似度检测,找寻共同子串。通过Python示例展示了Trie树插入和搜索方法,并指出Suffix Tree虽复杂但能提升性能。结合两者,实现复杂功能,展现数据结构的强大。
16 3
|
7天前
|
数据挖掘 开发者 Python
如何自学Python编程?
【7月更文挑战第14天】如何自学Python编程?
19 4
|
10天前
|
Python
不容错过!Python中图的精妙表示与高效遍历策略,提升你的编程艺术感
【7月更文挑战第11天】在Python编程中,图以邻接表或邻接矩阵表示,前者节省空间,后者利于查询连接。通过字典实现邻接表,二维列表构建邻接矩阵。图的遍历包括深度优先搜索(DFS)和广度优先搜索(BFS)。DFS使用递归,BFS借助队列。这些基础技巧对于解决复杂数据关系问题,如社交网络分析或迷宫求解,至关重要,能提升编程艺术。
17 5
|
12天前
|
存储 算法 Python
震撼!Python算法设计与分析,分治法、贪心、动态规划...这些经典算法如何改变你的编程世界!
【7月更文挑战第9天】在Python的算法天地,分治、贪心、动态规划三巨头揭示了解题的智慧。分治如归并排序,将大问题拆解为小部分解决;贪心算法以局部最优求全局,如Prim的最小生成树;动态规划通过存储子问题解避免重复计算,如斐波那契数列。掌握这些,将重塑你的编程思维,点亮技术之路。
19 1