算法通关村第一关——链表青铜挑战笔记

2023-07-26

字数：7k字 | 预计阅读时长：25分钟

摘要：🌱从这篇文章开始，我将记录📝在算法村的算法学习笔记，以及自己的理解与知识点补充。这篇 链表青铜挑战包括：理解Python是如何构造出链表的、链表插入节点、链表删除节点等链表的基本操作，细节满满，小白友好哦🤓。

关卡名	青铜级——小白也能学会的链表
核心内容	1.Python是如何构造出链表的
核心内容	2.链表如何进行增删改查

一、什么是链表

链表是一种最基本的结构，普通的单链表就是只给你一个指向链表头的指针head，如果想要访问其他元素，就只能从head开始一个个向后找，遍历链表最终会在访问尾节点之后如果继续访问，就会返回null。

1.单向链表的结构

🖇一种叫做单向链表的东西，它是由很多小盒子 📦连在一起的，每个小盒子里面有两个东西，一个是你想要放进去的数据（存放数据的变量data），比如数字🔢、字母🔡、图片🌠等，另一个是一个箭头（指向下一个结点的指针next） ➡️，它指向下一个小盒子的位置。这样你就可以通过找到第一个小盒子，然后沿着箭头的方向，一步一步找到你想要的数据。

比如，你有一个单向链表，它里面存放了你和你的朋友们的名字和年龄，像这样：
你可以看到，每个小盒子里面有两个东西，一个是名字和年龄的数据，另一个是箭头。箭头指向下一个小盒子的位置。第一个小盒子没有箭头指向它，所以它是头结点，最后一个小盒子的箭头指向了空白处，表示没有下一个小盒子了，所以它是尾结点。
20230726113834
如果你想要找到你自己的名字和年龄，你就可以从头结点开始，沿着箭头的方向，依次查看每个小盒子里面的数据，直到找到你自己为止。如果你想要找到你朋友小红的名字和年龄，你也可以用同样的方法。但是如果你想要从后往前找，就不行了，因为箭头只能指向前面的小盒子，不能指向后面的小盒子。这就是为什么叫做单向链表，因为它只能往一个方向走。
每个结点有一个指向后继元素的next指针。表中最后一个元素的next指向null。

名词	解释
链表（linked list）	是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成
节点	在链表中，每个点都是由值和指向下一个结点的地址组成的独立单元，称为一个结点，有时也称节点，含义都是一样的
头节点	第一个结点最重要，对于单链表，如果知道了第一个元素，就可以通过遍历访问整个链表
虚拟结点	虚拟结点是一种特殊的结点，它没有值，只有一个指针，指向链表的头结点

虚拟结点的作用是为了方便我们操作链表，比如插入、删除、反转等。有了虚拟结点，我们就不用担心链表为空或者头结点变化的情况，因为虚拟结点始终存在，始终指向头结点。

在做题以及在工程里经常会看到虚拟结点的概念，其实就是一个结点dummyNode，其next指针指向head，也就是dummyNode.next=head。
因此，如果我们在算法里使用了虚拟结点，则要注意如果要获得head结点，或者从方法（函数）里返回的时候，则应使用dummyNode.next。
另外注意，dummyNode的val不会被使用，初始化为0或者-1等都是可以的。既然值不会使用，那么虚拟结点有啥用呢？简单来说，就是为了方便我们处理首部结点，否则我们需要在代码里单独处理首部结点的问题。在链表反转里，我们会看到该方式可以大大降低解题难度。

🖇你可以把虚拟结点想象成一个小助手，它帮助我们管理链表。它总是站在链表的最前面，告诉我们链表的头结点在哪里。它也可以帮助我们在链表中插入或删除任何一个结点，只要我们告诉它要操作的位置。
但是虚拟结点并不是链表的一部分，它只是一个工具。所以当我们要获取或返回链表的时候，我们不能使用虚拟结点，而要使用它的后继，也就是真正的头结点。否则我们会得到一个错误的结果。

思考一下：单链表

你是否理解链表的含义了呢？思考下面两个图，是否都满足单链表的要求，为什么？

图一
图二

解析：
上面第一个图是满足单链表要求的，因为我们说链表要求环环相扣，核心是一个结点只能有一个后继，但不代表一个结点只能有一个被指向。
图一，c1被a2和b3同时指向，这是没关系的。
所以图2不满足要求，因为c1有两个后继a5和b4.

🖇可以把链表想象成一些火车车厢，每个车厢就是一个结点，每个车钩就是一个指针。单链表就像一列没有头没有尾的火车，你可以从任何一个车厢开始往前或者往后看，只能看到一个车厢。但是你也可以把两列没有也没有尾的火车拼接在一起，让它们共享一个车厢。
判断一个结点有几个后继，就是看它的指针指向哪里。
如果它的指针指向空，就说明它没有后继。如果它的指针指向另一个结点，就说明它有一个后继。如果它的指针指向多个结点，就说明它有多个后继。但是这种情况是不可能发生的，因为每个结点只能有一个指针。所以在单链表中，每个结点要么没有后继，要么只有一个后继。

另外在做题的时候需要注意比较的是值还是结点，有时可能两个结点的值相等，但并不是同一个结点，例如下图中，有两个结点的值都是1，但并不是同一个结点。

20230726154508

二、创建链表

算法的基础是数据结构，任何数据结构的基础都是创建➕增删改查，所有的链表算法题分解到最后，都是这几个操作，所以我们也从这五项开始学习链表。
如何构造链表，首先要理解JVM是怎么构建出链表的，我们知道JVM里有栈区和堆区，栈区主要存引用，也就是一个指向实际对象的地址，而堆区存的才是创建的对象

栈区的特点是后进先出，也就是说最后放进去的变量最先被取出来。
栈区也可以存储一种特殊的变量，叫做引用。
引用就是一个指向另一个地方的箭头，告诉我们在哪里可以找到真正的数据。
堆区的特点是无序的，也就是说我们可以随意地在堆区里创建或删除对象。
堆区里的对象不能直接被访问，只能通过引用来找到它们。

名词	解释
JVM	JVM是Java虚拟机的简称，它是一种软件，可以让我们的电脑运行Java程序。JVM里有不同的区域，用来存储不同的数据。其中两个重要的区域叫做栈区和堆区。
栈区	栈区是一种类似于盒子的结构，它可以存储一些变量，比如数字或者字母。每个变量都有一个名字，比如a或者b。
堆区	堆区是一种类似于仓库的结构，它可以存储一些对象，比如链表或者数组。每个对象都有一个地址，比如1001或者2002。
链表	链表是一种对象，它由多个结点组成，每个结点都有一个值和一个指针。为了构造链表，我们需要在栈区和堆区里分别做一些操作。

🤓首先，在栈区里创建一个引用变量，比如head，它表示链表的头结点。然后，在堆区里创建一个结点对象，比如A，它有一个值和一个指针。接着，让head指向A，也就是说head的箭头指向A的地址。这样就完成了第一个结点的创建。接下来，在堆区里再创建一个结点对象，比如B，它也有一个值和一个指针。然后，让A的指针指向B，也就是说A的箭头指向B的地址。这样就完成了第二个结点的创建。重复这样的步骤，我们就可以在堆区里创建任意多个结点，并且让前一个结点指向后一个结点。最后，在栈区里只需要保留head这个引用变量，它就可以帮助我们找到整个链表。
20230726155535

🖇你可以把栈区想象成一些✉️信封放在一起，每个信封里有一张照片🌠。你可以把堆区想象成一些玩具熊🐻散落在地上，每只玩具熊上有一张照片🌅。你可以把链表想象成一些玩具熊拥抱在一起，每只玩具熊上有一张照片。为了构造链表，你需要在信封里放一张照片，指向第一只玩具熊；然后在每只玩具熊上放一张照片，指向下一只玩具熊。

例如我们定义这样一个类：

1
2
3

class Course:
    teacher = None
    student = None

20230727100613

这里的teacher和student就是指向堆区引用，假如我们这样定义：

class Course:
    def __init__(self, val):
        self.val = val
        self.next = None

20230727100646

Course类

这个类有一个特殊的方法，叫做__init__。这个方法是在创建对象的时候自动调用的，它可以用来初始化对象的属性。这个方法有两个参数，self和val。self表示对象本身，val表示传入的值。
这个类有两个属性，self.val和self.next。self.val表示对象的值，它等于传入的val。self.next表示对象的后继，它默认为None，也就是空。

名词	解释
类	类是一种模板，可以用来创建对象
对象	对象是一种数据，可以有属性和方法
属性	属性是对象的特征，比如颜色或者大小
方法	方法是对象的行为，比如跑或者叫

🖇你可以把这个类想象成一个课程表，每个对象就是一个课程。每个课程都有一个值，比如数学或者英语。每个课程也有一个后继，表示下一个要上的课程。如果没有下一个课程，就用None表示。
为了创建一个课程对象，你需要用这个类的名字加上括号，并且在括号里写上课程的值。比如：
math = Course("Math")
创建了一个叫做math的课程对象，它的值是”Math”，它的后继是None。你可以用点号来访问或修改对象的属性。比如：
print(math.val) # 打印出"Math"
math.next = Course("English") # 让math的后继指向一个新的课程对象
这样就把math和English连在一起，形成了一个链表。这个时候next就指向下一个同为Course类型的对象了.
20230726161607
例如这里通过栈中的引用（也就是地址），就可以找到val(1)，然后val(1)结点又存了指向val(2)的地址，而val(3)又存了指向val(4)的地址，所以就构造出了一个链条访问结构。

根据面对对象理解，在python里规范的链表应该这么定义

class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        
    def get_data(self):
        return self.data

	def set_data(self, data):
        self.data = data

	def get_next(self):
        return self.next

	def set_next(self, next):
        self.next = next

20230727100714

ListNode类

这个类的属性是self.data和self.next，分别表示结点的数据和后继。
这个类有四个方法，分别是get_data，set_data，get_next和set_next。这些方法都是用来访问或修改对象的属性的。get_data和get_next是用来获取对象的数据和后继的，它们都返回相应的属性值。set_data和set_next是用来设置对象的数据和后继的，它们都接受一个参数，并且把相应的属性值改为参数值。

但是在LeetCode中算法题经常使用这样的方式来创建链表

这里的val就是当前结点的值，next指向下一个结点。因为两个变量都是public的，创建对象后能直接使用listnode.val和listnode.next来操作，虽然违背了面向对象的设计要求，但是下面的代码更为精简，因此在算法题目中应用广泛。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
listnode = ListNode(1)

20230727100743

🖇想象一下这个类就像是一个盒子，它有一个方法，叫做__init__。当你创建一个新的对象时，你可以给它一个数字和后面写的数字，比如listnode = ListNode(1, 2)就表示对盒子说1和2，然后盒子就会给你一张卡片，上面写着1，在后面写着2。如果你不给它任何数字，那么它就会默认为0和None，比如listnode = ListNode()就表示对盒子什么也不说，然后盒子就会给你一张卡片，上面写着0，在后面什么也没有。
你可以通过点号来看或改变卡片上的数字或后面写的数字，比如listnode.val就表示看卡片上的数字，listnode.next就表示看后面写的数字。你也可以用点号来改变它们，比如listnode.val = 5就表示把卡片上的数字改成5，listnode.next = 3就表示把后面写的数字改成3。

三、遍历链表

对于单链表，不管进行什么操作，一定是从头开始逐个向后访问，所以操作之后是否还能找到表头非常重要。一定要注意“狗熊掰棒子”问题，也就是只顾当前位置而将标记表头的指针丢掉了。

20230727092319

代码如下：

def length(self):
    """链表长度"""
    # cur初始时指向头结点
    cur = self._head
    count = 0
    # 尾结点指向None，当未到达尾部时
    while cur != None:
        count += 1
        # 将cur后移一个结点
        cur = cur.next
    return count

20230727100805

length方法:用来计算链表的长度的，也就是链表里有多少个结点。
一个参数self，表示链表对象本身。
三个变量:cur、count、return。cur表示当前的结点，count表示结点的数量，return表示返回的结果。

🖇你可以把这个方法想象成一个计数器，它可以帮助我们数一数链表里有多少个珠子。每次数一个珠子，就让计数器加一。每次数完一个珠子，就看看下一个珠子在哪里。直到没有下一个珠子了，就停止计数，并且告诉我们结果。

四、插入节点

1.尾部插入

尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可
20230727093026

2.头部插入

🖇注意容易忘记head需要重新指向表头，链表就像是一串珍珠，每个节点就像是一个珍珠，它有一个值和一个指向下一个节点的指针。
当我们创建一个新节点newNode，它就像是一个新的珍珠，它有一个值和一个指针。我们想把它放在链表的最前面，就要把它的指针指向原来的第一个节点head，就像把线绑在原来第一个的珍珠上一样。这样就可以用newNode.next=head来表示。之后我们要遍历新链表就要从newNode开始一路next向下了，就像从新的珍珠开始一路看颜色一样。但我们还是习惯让head来表示链表的第一个节点，所以我们可以让head=newNode，就像把新的珍珠叫做head一样。如下图：
20230727093549

3.中间插入

🖇想象一下你有一串珍珠，每个珍珠都有一个颜色。你想在这串珍珠的中间某个位置加上一个新的珍珠，比如紫色的。怎么办呢？你可以先找到你想插入的位置，比如在蓝色和绿色之间，然后把紫色的珍珠用线穿起来，然后把线的一头绑在蓝色的珍珠上，把线的另一头绑在绿色的珍珠上，这样就把紫色的珍珠放在了中间。这样你就可以按照颜色的顺序看到所有的珍珠了。
20230727093416
这个过程就像是在链表的中间位置插入一个新的节点。链表就像是一串珍珠，每个节点就像是一个珍珠，它有一个值和一个指向下一个节点的指针。当我们创建一个新节点newNode，它就像是一个新的珍珠，它有一个值和一个指针。我们想把它放在链表的中间某个位置，就要先找到那个位置，比如在cur和cur.next之间，cur就像是蓝色的珍珠，cur.next就像是绿色的珍珠。

下图中，如果要在7的前面插入，当cur.next=node(7)了就应该停下来，此时cur.val=15。然后需要给newNode前后接两根线，此时只能先让new.next=node(15).next（图中虚线），然后node(15).next=new，而且顺序还不能错。

想一想为什么不能颠倒顺序？

由于每个节点都只有一个next，因此执行了node(15).next=new之后，节点15和7之间的连线就自动断开了，如下图所示：

20230727094321

综上，我们写出链表插入方法的如下所示：

# 指定位置添加
def insert (self, pos, item):
    """指定位置添加元素"""
    # 若指定位置pos为第一个元素之前，则执行头部插入
    if pos <= 0:
        self.add(item)
    # 若指定位置超过链表尾部，则执行尾部插入
    elif pos > (self.length() - 1):
        self.append(item)
    # 找到指定位置
    else:
        node = Node(item)
        count = 0
        # pre用来指向指定位置pos的前一个位置pos-1，初识从头节点开始移动到指定位置
        pre = self._head
        while count < (pos - 1):
            count += 1
            pre = pre.next
        # 先将新节点node的next指向插入位置的节点
        node.next = pre.next
        # 将插入位置的前一个节点的next指向新节点
        pre.next = node

20230727100843

这段代码告诉电脑怎么把一些东西放到一条线上。这条线上有很多盒子，每个盒子里有一个东西和一根绳子。绳子可以把盒子连起来，形成一条线。
self：这条线本身、pos：要放东西的位置、item：要放的东西。

这段代码有几种情况：

如果pos是0或者负数，表示要把东西放到线的最前面。那么就找一个新盒子，把item放进去，并用绳子把它和原来的第一个盒子连起来。
如果pos比线上盒子的数量还多，表示要把东西放到线的最后面。那么就找一个新盒子，把item放进去，并用绳子把它和原来的最后一个盒子连起来。
如果pos在0和盒子数量之间，表示要把东西放到线中间某个地方。那么就找一个新盒子，把item放进去，并用绳子把它和原来那个位置前后两个盒子连起来。

这里需要再补充一点head = null的时候该执行什么操作呢？如果是null的话，你要插入的结点就是链表的头结点，也可以直接抛出不能插入的异常，两种处理都可以，一般来说我们更倾向前者。

判断pre是否是None，如果是，就让链表的头部指向node，这样就可以替换头节点；如果不是，就让pre的next链接指向node，这样就可以插入到中间或者尾部。

如果链表是单调递增的，一般会让你将元素插入到合适的位置，序列仍然保持单调，你可以尝试一下该如何实现。

思考：这个问题是要你在一条线上放东西的时候，保证线上的东西是从小到大排列的。比如，如果线上有1，3，5，7这四个盒子，你要放一个4的盒子，你就要把它放在3和5之间。这样线上的盒子就是1，3，4，5，7，还是从小到大的。如果你要放一个8的盒子，你就要把它放在7后面。如果你要放一个2的盒子，你就要把它放在1前面。

要实现这个功能，你可以用以下的步骤：

先找到一个变量pre，让它指向线的第一个盒子。
然后用一个循环，不断地检查pre指向的盒子和下一个盒子里的东西和你要放的东西的大小关系。如果pre指向的盒子里的东西比你要放的东西小，而下一个盒子里的东西比你要放的东西大或者等于，那么就找到了要放东西的位置。如果没有找到，就让pre指向下一个盒子，继续循环。
当找到了位置后，就用和前面一样的方法，创建一个新盒子，把item放进去，并用绳子把它和pre指向的盒子和下一个盒子连起来。
如果循环结束了还没有找到位置，表示你要放的东西比线上所有盒子里的东西都大，那么就把它放在最后面。

def insert(self, pos, item):
    # 判断pos是否是一个合法的整数，如果不是，就抛出一个异常
    if not isinstance(pos, int):
        raise TypeError("pos must be an integer")

    # 判断链表是否为空，如果为空，直接调用self.add(item)方法
    if self.is_empty():
        self.add(item)
        return

    # 先找到一个变量pre，让它指向链表的第一个节点
    pre = self._head
    # 用一个变量count来记录当前遍历到的位置，初始化为0
    count = 0

    # 用一个循环，不断地检查pre指向的节点和下一个节点里的数据和item的大小关系
    while pre.next is not None:
        # 如果count等于pos，表示找到了要插入的位置，结束循环
        if count == pos:
            break

        # 如果pre指向的节点的数据小于item，而下一个节点的数据大于等于item，
        表示找到了要插入的位置，结束循环
        if pre.item < item and pre.next.item >= item:
            break

        # 如果没有找到位置，就让pre指向下一个节点，并让count加一，继续循环
        pre = pre.next
        count += 1

    # 创建一个新节点node，并把item赋值给它
    node = Node(item)

    # 判断item和头节点或者尾节点的数据的大小关系
    # 如果小于头节点，就把新节点插入到头部
    if item < self._head.item:
        node.next = self._head
        self._head = node

    # 如果大于尾节点，就把新节点插入到尾部
    elif cur is None and item > pre.item:
        pre.next = node
        node.next = None

    # 否则就把新节点插入到pre和cur之间或者尾部
    else:
        node.next = cur
        pre.next = node

20230727101009
20230727101026

⚠️ count+1

如果你用没有count加一的代码，你只能根据大小关系来确定插入的位置，也就是找到一个位置，使得pre指向的节点的数据小于等于item，而cur指向的节点的数据大于等于item。
但是，如果你想插入一个2的节点，你会发现没有这样的位置，因为链表中所有的节点的数据都大于2。所以，你会在循环结束后，把2插入到链表的尾部，也就是7后面。但是这样就不符合链表是单调递增的要求，因为2小于7。所以，没有count加一的代码不能实现你想要的功能。
如果你用有count加一的代码，你可以根据pos参数来确定插入的位置，也就是找到一个位置，使得count等于pos。这样，你就可以自由地选择插入的位置，而不受大小关系的限制。
比如，如果你想插入一个2的节点，你可以指定pos为1，表示要插入到第一个位置，也就是1和3之间。这样，你就可以保持链表是单调递增的，并且满足你的需求。所以，有count加一的代码可以更灵活地控制插入的位置。

五、删除节点

1.尾部删除

例如下图中删除40，其前驱结点为7.遍历的时候需要判断cur.next是否为40，如果是，则只要执行cur.next=null即可，此时结点40变得不可达，最终会被JVM回收掉。

20230727095623

2.头部删除

一般只要执行head=head.next就行了，如下图:

20230727095748

3.中间删除

删除中间结点时，也会要用cur.next来比较，找到位置后，将cur.next指针的值更新为cur.next.next就可以解决，如下图所示：

20230727095830

完整代码实现

# 删除结点
def remove(self, item):
    """删除结点"""
    cur = self._head
    pre = None
    while cur != None:
        # 找到了指定元素
        if cur.item == item:
            # 如果第一个就是删除的结点
            if not pre:
                # 将头指针指向头结点的后一个结点
                self._head = cur.next
            else:
                # 将删除位置前一个结点的next指向删除位置的后一个结点
                pre.next = cur.next
            break
        else:
            # 继续按链表后移结点
            pre = cur
            cur = cur.next

20230727101059

self:这条线本身、item：要拿走的东西。

🖇告诉电脑怎么把一条线上的某个东西拿走。这条线上有很多盒子，每个盒子里有一个东西和一根绳子。绳子可以把盒子连起来，形成一条线。

先找到两根箭头cur和pre，让cur指向线的第一个盒子，pre指向空气。
然后用一个游戏规则，不断地看看cur指向的盒子里有什么东西和item是不是一样。如果一样，表示找到了要拿走的盒子。如果不一样，就让pre指向cur，cur指向下一个盒子，继续游戏。

当找到了要拿走的盒子后，有两种情况：

如果pre指向空气，表示要拿走的盒子是线的第一个盒子，那么就让线的头部指向cur指向的下一个盒子，这样就把第一个盒子从线上拿走了。
如果pre不指向空气，表示要拿走的盒子不是线的第一个盒子，那么就让pre指向的绳子指向cur指向的下一个绳子，这样就把cur指向的盒子从线上拿走了。
当拿走了盒子后，就结束游戏。

⚠️如果链表本身是单调的，那么你任意删除一个节点后，它仍然是单调的。因为删除一个节点不会影响其他节点的顺序，只会让链表变短。

🌿到此介绍Python是如何构造出链表的、链表插入节点、链表删除节点等链表的基本操作就结束啦～

-------------本文结束感谢您的阅读-------------

本文作者： 金金
本文链接： http://example.com/2023/07/26/算法通关村第一关——链表青铜挑战笔记/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！