乔克视界 乔克视界
首页
  • 运维
  • 开发
  • 监控
  • 安全
  • 随笔
  • Docker
  • Golang
  • Python
  • AIOps
  • DevOps
  • 心情杂货
  • 读书笔记
  • 面试
  • 实用技巧
  • 博客搭建
友链
关于
收藏
  • 分类
  • 标签
  • 归档

乔克

云原生爱好者
首页
  • 运维
  • 开发
  • 监控
  • 安全
  • 随笔
  • Docker
  • Golang
  • Python
  • AIOps
  • DevOps
  • 心情杂货
  • 读书笔记
  • 面试
  • 实用技巧
  • 博客搭建
友链
关于
收藏
  • 分类
  • 标签
  • 归档
  • Docker

  • Golang

  • AIOps

  • Python

    • 基础知识

      • Python之链表
        • Python 之类的初识
        • Python之函数式编程
        • Python之匿名函数
        • Python之自定义函数
        • Python之异常处理
        • Python之条件与循环
        • Python之列表生成式
        • Python之生成器
        • Python之装饰器
        • Python之迭代器
        • Python之进程、线程、协程
        • Python之深浅拷贝
        • Python之反射
        • Python之并发编程
        • Python之垃圾回收机制
        • Python之断言assert
        • Python之上下文管理器和with语句
        • Python中JSON的对应关系
        • Python之单例模式
      • Django框架

      • 其他

    • DevOps

    • 专栏
    • Python
    • 基础知识
    乔克
    2025-07-19
    目录

    Python之链表

    在我的记忆里,链表是我在大学时候学 C 和数据结构的时候接触过,后面就很少去碰了,今天突然心血来潮刷一刷 Leetcode,遇到了如下链表的问题:

    497269376bbdbf0a70080188383078af MD5

    起初我以为可以当列表来玩(原谅自己是个菜鸟),发现行不通,就去搜索了一下 python 链表相关的知识,找到了一篇写的相对比较齐全的文档,我就厚颜无耻的抄录了。

    文章作者:Neal (opens new window)

    原始链接:http://zhaochj.github.io/2016/05/12/2016-05-12-数据结构-链表/ (opens new window)

    许可协议: "署名-非商用-相同方式共享 4.0" (opens new window) 转载请保留原文链接及作者。

    # 介绍

    链表是实现了数据之间保持逻辑顺序,但存储空间不必按顺序的方法。可以用一个图来表示这种链表的数据结构:

    aa7d9adc46270ccfbb50c71256a2cde4 MD5

    链表中的基本要素:

    1. 结点(也可以叫节点或元素),每一个结点有两个域,左边部份叫值域,用于存放用户数据;右边叫指针域,一般是存储着到下一个元素的指针
    2. head 结点,head 是一个特殊的结节,head 结点永远指向第一个结点
    3. tail 结点,tail 结点也是一个特殊的结点,tail 结点永远指向最后一个节点
    4. None,链表中最后一个结点指针域的指针指向 None 值,因也叫接地点,所以有些资料上用电气上的接地符号代表 None

    链表的常用方法:

    1. LinkedList() 创建空链表,不需要参数,返回值是空链表
    2. is_empty() 测试链表是否为空,不需要参数,返回值是布尔值
    3. append(data) 在尾部增加一个元素作为列表最后一个。参数是要追加的元素,无返回值
    4. iter() 遍历链表,无参数,无返回值,此方法一般是一个生成器
    5. insert(idx,value) 插入一个元素,参数为插入元素的索引和值
    6. remove(idx)移除 1 个元素,参数为要移除的元素或索引,并修改链表
    7. size() 返回链表的元素数,不需要参数,返回值是个整数
    8. search(item) 查找链表某元素,参数为要查找的元素或索引,返回是布尔值

    # 节点类

    python 用类来实现链表的数据结构,节点(Node)是实现链表的基本模块,每个节点至少包括两个重要部分。首先,包括节点自身的数据,称为“数据域”(也叫值域)。其次,每个节点包括下一个节点的“引用”(也叫指针)

    下边的代码用于实现一个 Node 类:

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    1
    2
    3
    4

    此节点类只有一个构建函数,接收一个数据参数,其中next表示指针域的指针,实例化后得到一个节点对象,如下:

    node = Node(4)
    
    1

    此节点对象数据为4,指针指向 None。

    这样一个节点对象可以用一个图例来更形象的说明,如下:

    4b40cb1e673fdd0c964c5fc10510d2d3 MD5

    图 2: 节点

    # 链表类

    先来看 LinkedList 类的构建函数:

    class LinkedList:
        def __init__(self):
            self.head = None
            self.tail = None
    
    1
    2
    3
    4

    此类实例后会生成一个链表对象,初始化了head和tail节点,且两节点都指向None,实例化代码如下:

    link_list = LinkedList()
    
    1

    也可以用图形象的表示这个链表对象,如下:

    afb40347f3ccc1259ce596c432b2f1b5 MD5

    图 3:空链表

    # is_empty 方法实现

    is_empty 方法检查链表是否是一个空链表,这个方法只需要检查head节点是否指向None即可,代码如下:

    def is_empty(self):
            return self.head is None
    
    1
    2

    如果是空列表返回True,否则返回False

    # append 方法实现

    append 方法表示增加元素到链表,这和 insert 方法不同,前者使新增加的元素成为链表中第一个节点,而后者是根据索引值来判断插入到链表的哪个位置。代码如下:

    def append(self, data):
            node = Node(data)
            if self.head is None:
                self.head = node
                self.tail = node
            else:
                self.tail.next = node
                self.tail = node
    
    1
    2
    3
    4
    5
    6
    7
    8

    既然要新增加节点,首先把 Node 类实例化得到一个 node 对象。这里有两种情况需要考虑,一是链表是一个空链表时怎样 append 一个节点;二是当链表不是空链表时又怎样 append 一个节点?

    当if self.head is None:为True时,把链表的head和tail都指向了node,假如我们执行了

    link_list(append(4))
    
    1

    此时的链表结构如下图:

    684cb4b12052d5b52b0d26ba130d398b MD5

    图 4:append-1

    当if self.head is None:为False时,说明链表已经增加了一个节点了,再增加一个节点时head已经指向了第一个节点,所以不为None,比如增加的第二个节点为:

    link_list(append(5))
    
    
    1
    2

    增加第二个节点的操作需要分两步完成,第一步:self.tail.next = node,即把上一个节点的next指针指向当前node;第二步:self.tail = node,把tail移动到node,如下图:

    7eac2d0837336cdd9e69625406f6f055 MD5

    移动完成后就成这样了:

    a54910a24bb3fa538347fb1e9feb15c0 MD5

    当增加第三个、第四个等节点时,按照上边的操作依次类推。

    # iter 方法实现

    iter 方法表示遍历链表。在遍历链表时也要首先考虑空链表的情况。遍历链表时从head开始,直到一个节点的next指向None结束,代码如下:

    def iter(self):
            if not self.head:
                return
            cur = self.head
            yield cur.data
            while cur.next:
                cur = cur.next
                yield cur.data
    
    1
    2
    3
    4
    5
    6
    7
    8

    当是遍历一个空链表时,if not self.head:为True,直接返回None;如果不是空链表就让一个局部变量cur指向head,并把head的data属性yield出来,再对cur的next指针指向的对象做while循环,直到next指向None,这样就遍历了链表。insert 方法实现

    假如采取append方法又增加了两个节点,增加完成后如下图:

    b3b24b3d1bc6acde4a84355e0eb129d4 MD5

    如果想在数据域为6的那节点处插入一个节点,需要做的操作有两步:

    1. 把新节点的 next 指针指向数据域为6的这个节点,即为数据域为5节点的 next 指向指向的对象
    2. 把数据域为5节点的 next 指针指向新加的节点

    注: 这两个步骤不能颠倒,如果颠倒,数据域为6的节点会被丢失,数据域为7的节点不再是链表的节点。

    示意图如下:

    b0928b47f7a8e3b3ec64df37976efab2 MD5

    还要额外考虑两种情况:

    1. 空链表时
    2. 插入位置超出链表节点的长度时
    3. 插入位置是链表的最后一个节点时,需要移动 tail

    当是在链表最后一个节点插入时,示意图如下:

    3b724c63995baed372e7eab9a12f8b30 MD5

    要在指定的索引位置插入一个节点,前提是需要找到这个位置,在链表中只有采用遍历的方式,具有 O(n)的速度,最糟糕时会遍历链表的所有节点,而当找到插入点时,我们并不需要当前节点的信息,而是需要前一个节点的信息,所以代码中巧妙的使用了while cur_idx < idx-1:的方式,这样能使用cur这个变量能指向插入点上一个节点对象。

    实现insert方法的代码如下:

    def insert(self, idx, value):
            cur = self.head
            cur_idx = 0
            if cur is None:
                raise Exception('The list is an empty list')
            while cur_idx < idx-1:
                cur = cur.next
                if cur is None:
                    raise Exception('list length less than index')
                cur_idx += 1
            node = Node(value)
            node.next = cur.next
            cur.next = node
            if node.next is None:
                self.tail = node
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

    # remove 方法实现

    remove 方法接收一个 idx 参数,表示要删除节点的索引,此方法要考虑以下几种情况:

    1. 空链表,直接抛出异常
    2. 删除第一个节点时,移动 head 到删除节点的 next 指针指向的对象
    3. 链表只有一个节点时,把 head 与 tail 都指向 None 即可
    4. 删除最后一个节点时,需要移动 tail 到上一个节点
    5. 遍历链表时要判断给定的索引是否大于链表的长度,如果大于则抛出异常信息

    请看下边图例:

    28e4037c1c00ff05972ae69ea0ae65d7 MD5

    3b54b8fbd1b537f8633741f28a1485d7 MD5

    以下为 remove 函数的代码:

    def remove(self, idx):
           cur = self.head
           cur_idx = 0
           if self.head is None:  # 空链表时
               raise Exception('The list is an empty list')
           while cur_idx < idx-1:
               cur = cur.next
               if cur is None:
                   raise Exception('list length less than index')
               cur_idx += 1
           if idx == 0:   # 当删除第一个节点时
               self.head = cur.next
               cur = cur.next
               return
           if self.head is self.tail:   # 当只有一个节点的链表时
               self.head = None
               self.tail = None
               return
           cur.next = cur.next.next
           if cur.next is None:  # 当删除的节点是链表最后一个节点时
               self.tail = cur
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21

    # size 函数实现

    size 函数不接收参数,返回链表中节点的个数,要获得链表的节点个数,必定会遍历链表,直到最后一个节点的next指针指向None时链表遍历完成,遍历时可以用一个累加器来计算节点的个数,如下代码:

    def size(self):
            current = self.head
            count = 0
            if current is None:
                return 'The list is an empty list'
            while current is not None:
                count += 1
                current = current.next
            return count
    
    1
    2
    3
    4
    5
    6
    7
    8
    9

    # search 函数实现

    search 函数接收一个 item 参数,表示查找节点中数据域的值。search 函数遍历链表,每到一个节点把当前节点的data值与item作比较,最糟糕的情况下会全遍历链表。如果查找到有些数据则返回True,否则返回False,代码如下:

    def search(self, item):
            current = self.head
            found = False
            while current is not None and not found:
                if current.data == item:
                    found = True
                else:
                    current = current.next
            return found
    
    1
    2
    3
    4
    5
    6
    7
    8
    9

    # Node 类与 LinkedList 类完整代码

    最后把Node类和LinkedList类的完整代码整理如下:

    Node 类:

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    1
    2
    3
    4

    LinkedList 类及调度代码:

    class LinkedList:
        def __init__(self):
            self.head = None
            self.tail = None
    
        def is_empty(self):
            return self.head is None
    
        def append(self, data):
            node = Node(data)
            if self.head is None:
                self.head = node
                self.tail = node
            else:
                self.tail.next = node
                self.tail = node
    
        def iter(self):
            if not self.head:
                return
            cur = self.head
            yield cur.data
            while cur.next:
                cur = cur.next
                yield cur.data
    
        def insert(self, idx, value):
            cur = self.head
            cur_idx = 0
            if cur is None:             # 判断是否是空链表
                raise Exception('The list is an empty list')
            while cur_idx < idx-1:   # 遍历链表
                cur = cur.next
                if cur is None:   # 判断是不是最后一个元素
                    raise Exception('list length less than index')
                cur_idx += 1
            node = Node(value)
            node.next = cur.next
            cur.next = node
            if node.next is None:
                self.tail = node
    
        def remove(self, idx):
            cur = self.head
            cur_idx = 0
            if self.head is None:  # 空链表时
                raise Exception('The list is an empty list')
            while cur_idx < idx-1:
                cur = cur.next
                if cur is None:
                    raise Exception('list length less than index')
                cur_idx += 1
            if idx == 0:   # 当删除第一个节点时
                self.head = cur.next
                cur = cur.next
                return
            if self.head is self.tail:   # 当只有一个节点的链表时
                self.head = None
                self.tail = None
                return
            cur.next = cur.next.next
            if cur.next is None:  # 当删除的节点是链表最后一个节点时
                self.tail = cur
    
        def size(self):
            current = self.head
            count = 0
            if current is None:
                return 'The list is an empty list'
            while current is not None:
                count += 1
                current = current.next
            return count
    
        def search(self, item):
            current = self.head
            found = False
            while current is not None and not found:
                if current.data == item:
                    found = True
                else:
                    current = current.next
            return found
    
    if __name__ == '__main__':
        link_list = LinkedList()
        for i in range(150):
            link_list.append(i)
    #    print(link_list.is_empty())
    #    link_list.insert(10, 30)
    
    #    link_list.remove(0)
    
        for node in link_list.iter():
            print('node is {0}'.format(node))
        print(link_list.size())
    #    print(link_list.search(20))
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97

    然后我们上面那个问题就可以解决了,

    • 从头遍历两个链表,将它们的值进行相加,如果其中有一个链表为 None,其值为 0
    • 用一个参数来记录其进位,进位的标准为 1 或者 0,如果相加的和大于 10,则进位为 1,反之为 0
    • 每做完一次相加,就将两个链表前进一位

    代码如下:

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def addTwoNumbers(self, l1, l2):
            # 定义一个进位标志
            carry = 0
            # 定义一个tmp用来存储计算结果
            res = ListNode(0)
            tmp = res
            # 循环条件为l1或者l2不为空
            while l1 or l2:
                # 取值计算结果
                val = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
                # 计算上面的计算结果是否有进位
                carry,val = val//10,val%10
                # 存储值
                tmp.next=ListNode(val)
                tmp=tmp.next
                # 将l1和l2前进一位
                l1,l2 = l1.next if l1 else None,l2.next if l2 else None
            # 处理最后carry>0的情况
            if carry>0:
                tmp.next = ListNode(1)
            return res.next
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28

    作者:乔克

    本文链接:https://jokerbai.com

    版权声明:本博客所有文章除特别声明外,均采用 署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0) 许可协议。转载请注明出处!

    上次更新: 2025/07/19, 11:33:23
    大模型入门实战
    Python 之类的初识

    ← 大模型入门实战 Python 之类的初识→

    最近更新
    01
    使用 Generic Webhook Trigger 触发 Jenkins 多分支流水线自动化构建
    07-19
    02
    使用Zadig从0到1实现持续交付平台
    07-19
    03
    基于Jira的运维发布平台
    07-19
    更多文章>
    Theme by Vdoing | Copyright © 2019-2025 乔克 | MIT License | 渝ICP备20002153号 |
    • 跟随系统
    • 浅色模式
    • 深色模式
    • 阅读模式