链表——单链表的简单介绍

目录

​编辑

前提须知：

顺序表的缺点：

链表：

图例：

单链表的创建： 

 创建几个节点组成一个链表，并打印链表

头文件部分： （打印函数头文件部分）

打印部分：

主函数部分： 

数据的插入：

指针的插入：

“火车头的安装”和打印函数的调用： 

打印效果：

​编辑

前提注意：

尾插： 

开辟空间函数： 

头文件： 

源文件：

​编辑

主函数部分：

为什么有些地方使用 二级指针有些地方使用一级指针

头插： 

开辟空间函数：

头文件： 

源文件：

主函数部分：

尾删：

头文件：

没有节点：

多个节点： 

一个节点： 

图例：

源文件： 

 主函数部分：

 头删：

分析：

源文件：

头文件： 

主函数部分：

​编辑

指定位置之前插入数据：

步骤分析：

插入数据需要的是一个新的空间：

开辟空间函数：

指定的位置需要进行查找：

查找位置函数： 

头文件部分：

源文件： 

主函数部分：

本质：

源文件：

完整版：

头文件：

 主函数部分：

在指定位置之后插入数据:

本质：

头文件：

源文件：

主函数部分：

删除指定位置节点： 

头文件：

一个节点和没有节点：

多个节点： 

源文件：

主函数部分：

删除指定位置之后的节点： 

头文件： 

本质： 

源文件：

​编辑

主函数部分： 

链表的销毁：

 头文件：

源文件： 

主函数部分： 

额外：在指定位置pos插入数据——思路 

---

前提须知：

顺序表的简单介绍_明 日 香的博客-CSDN博客

顺序表的缺点：

• 从之前的博客中，我们得知，顺序表的本质实际上是一种数组。
• 而数组的最大特征就是连续的空间。
• 也因此，在线性表中，顺序表是一种物理上和逻辑上都连续的直线。

但是因为物理意义上的连续，顺序表有着众多的不便之处：

• 空间的浪费和多余
• 开辟空间时，所在空间的结余不多，会出现重新开辟和拷贝数据的操作，具体参考realloc函数调整空间的操作，realloc-CSDN博客 

链表：

• 因为顺序表的不足之处，从而产生了链表。
• 链表在线性表中，是一个逻辑上连续，但是物理上并不连续的结构。
• 链表实质上是由多个节点，依次链接构成的一个类火车车厢的结构类型，每一个节点都是独立存在的。

图例：

• 如图所示，plist就如同火车的车头，车头连接着车厢，这个链接点是靠车头内的地址来进行指引的。 
• 同样，车厢和车厢之间也是靠着地址进行联系。
• 而地址，是需要存储在指针中才会起到链接作用。
• 所以，每一个节点分为了两个部分，一个是需要进行存储的数据，一个是指向下一个节点的指针，这个指针中存储的是下一个节点的地址！

单链表的创建： 

• 与其说是单链表的创建，不如说是单链表的节点的创建。 

• 如图，data是存储节点的数据，next是节点结构体类型，指向的是下一个节点，存储是下一个节点的地址。
• 同时注意，因为我们为了之后的方便，对节点结构体进行了重命名操作，但是在节点结构体成员中，指向下一个节点的指针 这个成员的类型，不能使用重命名后的结构体名字作为类型。 

 创建几个节点组成一个链表，并打印链表

在创建节点和打印节点之前，我们要创造一个 “火车车头”   

SLNode*phead就是火车车头，它指向的是第一个节点，所以它是指针，其中SLNode*则是指针的类型，因为节点是结构体类型的。

头文件部分： （打印函数头文件部分）

打印部分：

打印部分的关键在于循环遍历，因此使用循环结构

而循环结构的判定关键在于下一个节点是否存在，这与链表的结构有着密切的关系。

 如图我们得知，链表结束的标志其实就是是否存在下一个节点，而判断下一个节点是否存在就是看节点内，指向下一个节点的指针指向的是否是NULL 

而同时，循环遍历的关键也是寻找下一个节点是否存在，如若存在，变需要将当前指针变为下一个节点中的指针，指向更后面的节点。

• 因为指针需要进行更变，从指向当前节点的指针，变为指向下一个节点的指针，且为了进行循环，所以这就需要pcur= pcur->next 

主函数部分： 

数据的插入：

相比于顺序表，链表的每一个节点都是单独存在的，所以直接使用malloc对内存进行空间的申请 

指针的插入：

• data是指向节点中的数据
• next是节点中，指向下一个节点的指针 

“火车头的安装”和打印函数的调用： 

需要对火车头进行存放第一个节点的地址！ 

打印效果：

前提注意：

操作中的调用函数里面的  最开始的  形参中的指针变量    其实指向的是“火车头” 

尾插： 

• 本质上，尾插操作就是向内存申请空间，然后存入数据和指向下一个节点的指针，以及将自己的地址交给上一个节点。 
• 但是，尾插也分为两种情况。
• 第一种便是当前的链表为空，这时就直接将自己新开辟的空间地址交予火车头即可
• 第二种便是链表不为空，这时我们需要寻找当前链表最后面一个节点内部的指向下一个节点的指针，将其从NULL变为新开辟空间的地址。

 但是！无论是第一种情况还是第二种情况，我们都需要向内存申请一个空间，进行存放我们需要插入的数据所以我们再次之前创建一个开辟空间的函数，在尾插函数中进行调用

开辟空间函数： 

1. x表示插入的数据
2. node表示当前空间的地址，或者说是当前空间结构体的变量名
3. 将指向下一个空间的指针变为NULL
4. 同时最后返回当前空间的地址，以便尾插的操作 

注意事项： 

• 在进行尾插操作之前，还需要注意一点，别被指针变量迷惑！
• 因为我们要改变的是 指针变量内部存储的地址  ，也就是说我们要改变指针变量的值，所以我们要传递指针变量的地址，也就是传递&plist  传递plist这个指针变量的地址
• 单纯的传递一级指针，是改变不了指针变量内部的地址，只能改变最外面一层指针变量的名字。

头文件： 

源文件：

• 当为链表空时，直接将新开辟的空间地址交给“火车头” （SLNdoe**PPhead）
• 不为空的时候，需要进行遍历循环操作，找到最后一个节点的指向下一个节点的指针，然后传给这个指针新开辟的地址。

主函数部分：

• 传递plist这个指针变量的地址

为什么有些地方使用 二级指针有些地方使用一级指针

如上图所示，*pphead表示为二级指针，而prev->next表示一级指针。

这时因为他们所代表的东西不同。

• 当我们在进行链表的增删查改的时候，我们需要考虑链表是否为空链表，链表是否只有一个节点，而我们对于是否是空链表是否是头一个节点的最直接的改变就是头节点的改变。
• 而头节点是一个指针，想要改变指针指向或者说想要改变指针变量的数值，且要在内存中直接发生变化，我们必须使用传址调用，且因为是指针的原因，我们必须传递更高一级的指针。

所以传递头指针的时候我们用二级指针，因为我们要改变的是指针的指向，或者说我们要改变指向结构体的指针指向。

而后面一系列的一级指针，如上图中的一级指针操作，只是改变节点内部的指针指向，改变的是结构体内部的指针指向。 

 

就如图所示，*pphead就是个壳子，我们要把这个壳子挪走，就得传递这个壳子的内容，而prev和ptail就是里面的壳子，把里面的壳子进行改变只需要在内部进行改变即可。 

---

 

头插： 

头插的本质，其实就是，"火车头"内部的指针指向插入的节点，插入的节点的内部的指针，指向原来的第一个节点。

同时插入的本质，就是需要开辟空间，于是在头插中，我们也是要用到之前的开辟空间函数。

开辟空间函数：

头文件： 

x表示插入的数据 

源文件：

• node->next = *pphead 
• node->next指的是新节点内部的指针，指向的下一个节点是第一个节点
• *pphead指的是原第一个节点地址，pphead是火车头内部的指针。
• *pphead = node  将火车头内部指针的指向进行修改，变成新节点的地址。

主函数部分：

尾删：

• 尾删的本质是删除最后一个节点，对最后一个节点进行释放，倒数第二个节点内部的指针，指向为NULL 

头文件：

但是！尾删可以分为多种情况！第一种含有多个节点，第二种没有节点，一个节点。

没有节点：

没有节点，就意味着只有火车头，且火车头内部指针指向的是NULL，所以没有必要尾删

多个节点： 

• 对于多个节点，我们需要进行循环遍历，找到最后一个节点，然后释放。
• 但同时我们也需要找到倒数第二个节点，对第二个节点的内部指针指向进行修改。

可是，在先释放最后一个节点和先将倒数第二个节点内部的指针进行修改，我们产生了分歧。

原因如下：

1. 如若先释放最后一个节点，那我们难以找到倒数第二个节点
2. 如若先将倒数第二个节点内部的指针修改，那我们无法找到最后一个节点。

• 而解决的方案，则是设立两个指针变量，两个指针同时进行遍历，但不同的是，其中一个指针会赋予第一个节点的地址，另一个则赋予NULL
• 被赋予NULL的指针会比被赋予第一节点地址的指针更慢一步。 
• 当跳出循环后，我们将会得到倒数第二个节点以及倒数第一个节点的地址。 
• 随后进行修改和释放。 
• 同时释放最后一个节点结构体所在的空间（free），然后指针NULL避免野指针(ptail = NULL)

注意：上图中的patail->next ，patail是最后一个节点，它内部的指针指向的是NULL 

一个节点： 

在多个节点的基础上，如果只有一个节点，那么两个指针变量进行遍历会出现错误！ 

所以需要进行区分，区分为一个节点和多个节点的情况 

图例：

如图所示，如果是只有一个节点，那么只需要在"火车头"内部的指针中进行修改，直接释放第一个节点的指针，然后"火车头"内部指针修改为NULL，即可。 

源文件： 

因为无节点尾删是无效的，所以使用assert进行判定

 主函数部分：

 头删：

分析：

•  和尾删类似，将第一个节点进行释放，而后将"火车头"内部的指针变量的地址改成第二个节点的地址，同时释放第一个节点的空间和指针
• 但是我们不能先改变"火车头"的内部的指针变量的值。
• 而是使用一个零时变量，指向第一个节点，然后在改变火车头内部的指针变量值 
• 当然这里链表为空的状态不行，因为为空连节点都没有，所以应该先判断链表是否为空
• 而对于头删的只有一个节点情况和有多个节点情况我们可以使用，将删除的节点的内部的指针指向的地址，赋予"火车头"，这样，如果是多个节点，"火车头"指向的就是原第二个节点，而如果是一个节点，"火车头"指向的就是NULL

源文件：

头文件： 

主函数部分：

指定位置之前插入数据：

步骤分析：

1. 插入数据需要的是一个新的空间
2. 指定的位置需要进行查找
3. 前后指针指向的修改

插入数据需要的是一个新的空间：

开辟空间函数：

指定的位置需要进行查找：

• 对于指定的位置插入数据，我们首先要知道指定的位置是在哪里，改如何查找和遍历到指定的位置。
• 为此我们写一个遍历到指定位置的函数。

查找位置函数： 

头文件部分：

我们查找指定位置的节点是通过查找节点内的数值进行查找

也是通过数值是否相同来证明，我们所需要查找的指定节点是否存在，存在则返回整个节点的地址，交给之后的插入函数。 

源文件： 

主函数部分：

本质：

•  指定位置的地址交给新开辟空间的，新开辟空间的地址交原先指定位置前的节点 

源文件：

 同时在指定位置插入数据也是分为三种情况，没有节点，一个节点和多个节点。

• 链表为空就是没有节点，没有节点就不能在指定为之前插入，所以不能没有节点。

•  而只有一个节点的时候，火车头内部的指针要指向新开辟的空间，而新开辟的空间指向原先的第一个节点。 

• 多个节点，则遵循本质来进行敲打代码。

• ！= pos是为了找到指定位置后打破循环，而打破循环后，prev就是指定位置的前一个节点。
• node->next= pos 将开辟空间内部的指针指向指定位置。
• prev->next =node 将指定位置前一个节点内部的指针指向新开辟的空间。 

注意：最后这两行代码是不分先后顺序的 

完整版：

          

头文件：

 主函数部分：

注意在主函数部分记得使用  find （查找指定位置函数的返回值）

find调用后，在调用函数的形参是叫 pos

在指定位置之后插入数据:

本质：

• 在指定的位置后，插入一个新的节点。
• 新节点的指向变为原指定位置的后一个节点，新节点的地址，交给指定位置的节点。

注意事项：在此处，必须先将原指定位置的后一个节点地址交给新节点，如果说先进行指定位置节点内部指针的指向修改，则会找不到后一个节点的位置。

头文件：

 

源文件：

• 别忘记，插入节点的本质还需要开辟空间。 

• 至于为什么不需要火车头指针，是因为这里可以直接从pos后面获取后面一个节点位置，不需要从头遍历 

主函数部分：

因为是指定位置，所以我们还是需要用到之前的查找函数，进行查找指定的位置。

删除指定位置节点： 

本质就是删除指定位置节点，就是将指定位置前一个节点指向指定位置后一个节点，指定位置后一个节点地址交给指定位置前一个节点 

头文件：

同时也有三种情况：

1. 没有节点，这个是不存在的
2. 一个节点，直接删了，然后火车头指向的空间变成NULL
3. 多个节点则按照本质来算 

一个节点和没有节点：

• 没有节点是不存在的，所以进行断言处理
• 而一个节点则将原先那一个节点的指向（指向NULL）交给“火车头”，然后释放。

多个节点： 

1.  多个节点则需要找到指定位置之前的节点和指定位置后的节点。
2. 指定位置后的节点不需要查找，指定从指定位置获取。
3. 指定位置前的节点则需要进行遍历。
4. 然后先将指定位置内部的指向赋予指定位置前内部的指针。

源文件：

主函数部分：

别忘记指定位置还得使用查找函数 

删除指定位置之后的节点： 

头文件： 

不使用“火车头”内第一个节点地址的原因：

因为这里是删除指定位置之后，而指定位置在查找函数中会进行从头遍历，找到后会进行返值，因此我们得到是已经遍历过的

本质： 

• 本质上是要先将指定位置后一个节点的指向交给指定位置
• 然后才能将之后这个节点删除
• 而且是有先后顺序的
• 但是我们还有多种情况，那就是pos之后的节点是否存在，不存在则是不行的，所以要先进行断言 

源文件：

主函数部分： 

• 别忘记使用查找函数的返回值 

链表的销毁：

 头文件：

• 销毁链表的前提是节点存在
• 且如果要销毁链表那么则要将链表的每一个节点进行销毁
• 因此使用循环，但是因为贸然删除了一个节点，就无法通过这个节点找到下一个节点。
• 所以要先保存当前节点的下一个节点，而后把当前节点销毁。

源文件： 

主函数部分： 

---

 

额外：在指定位置pos插入数据——思路 

做法就是和在指定位置pos之后插入数据一样，但是不同的是将pos位置的数据进行转移，转移到新节点中，而新节点的数据转移到pos位置中

本质就是在pos位置后插入元素，然后数据交换。 

---