目录
一、为什么要使用链表
二、链表（单链表）是什么
三、链表的基础操作（增删查改）
一、为什么要使用链表
二、链表（单链表）是什么
头节点，头指针和首元节点
三、链表的基础操作
链表的创建（初始化）
链表插入元素
链表删除元素
链表查找元素
链表更新元素
单片机爱好者之家3群 企鹅群：630442960
一、为什么要使用链表
链表作为 C 语言中一种基础的数据结构，在平时写程序的时候用的并不多，但在操作系统里面使用的非常多。不管是RTOS还是Linux等使用非常广泛，所以必须要搞懂链表，链表分为单向链表和双向链表，单向链表很少用，使用最多的还是双向链表。单向链表懂了双向链表自然就会了。
二、链表（单链表）是什么
- 链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。
- 使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。
- 例如，使用链表存储 {1,2,3}，各个元素在内存中的存储状态可能是：
我们看到，上图 根本无法体现出各数据之间的逻辑关系。对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。如下图所示：
可以看到，数据不仅没有集中存放，在内存中的存储次序也是混乱的。那么，链表是如何存储数据间逻辑关系的呢？
链表存储数据间逻辑关系的实现方案是：为每一个元素配置一个指针，每个元素的指针都指向自己的直接后继元素，如下图所示：
显然，我们只需要记住元素 1 的存储位置，通过它的指针就可以找到元素 2，通过元素 2 的指针就可以找到元素 3，以此类推，各个元素的先后次序一目了然。
像图 2 这样，数据元素随机存储在内存中，通过指针维系数据之间“一对一”的逻辑关系，这样的存储结构就是链表
结点
很多教材中，也将“结点”写成“节点”，它们是一个意思。
在链表中，每个数据元素都配有一个指针，这意味着，链表上的每个“元素”都长下图这个样子
数据域用来存储元素的值，指针域用来存放指针。数据结构中，通常将图 3 这样的整体称为结点。
也就是说，链表中实际存放的是一个一个的结点，数据元素存放在各个结点的数据域中。举个简单的例子，图 2 中 {1,2,3} 的存储状态用链表表示，如下图所示：
因此，链表中每个节点的具体实现，需要使用 C 语言中的结构体，具体实现代码为：
typedef struct Linklist{
int elem;//代表数据域
struct Linklist *next;//代表指针域，指向直接后继元素
}Linklist; //link为节点名，每个节点都是一个 link 结构体提示：由于指针域中的指针要指向的也是一个节点，因此要声明为 Link 类型（这里要写成 struct Link* 的形式）。
头节点，头指针和首元节点
其实，图 4 所示的链表结构并不完整。一个完整的链表需要由以下几部分构成：
- 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
- 节点：链表中的节点又细分为头节点、首元节点和其他节点：
头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
其他节点：链表中其他的节点；
因此，一个存储{1,2,3} 的完整链表结构如下图 所示：
注意：链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。
明白了链表的基本结构，下面我们来了解如何创建一个链表。
三、链表的基础操作
链表的创建（初始化）
创建一个链表需要做如下工作：
- 声明一个头指针（如果有必要，可以声明一个头节点）；
- 创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；
例如，创建一个存储{1,2,3,4 }且无头节点的链表，C 语言实现代码如下：
linklist * initlinklist(){
linklist * p=NULL;//创建头指针
linklist * temp = (linklist*)malloc(sizeof(linklist));//创建首元节点
//首元节点先初始化
temp->elem = 1;
temp->next = NULL;
p = temp;//头指针指向首元节点
//从第二个节点开始创建
for (int i=2; i<5; i++) {
//创建一个新节点并初始化
linklist *a=(linklist*)malloc(sizeof(linklist));
a->elem=i;
a->next=NULL;
//将temp节点与新建立的a节点建立逻辑关系
temp->next=a;
//指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对
temp=temp->next;
}
//返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
return p;
}
如果想创建一个存储{1,2,3,4}且含头节点的链表，则 C 语言实现代码为：
linklist * initlinklist(){
linklist * p=(linklist*)malloc(sizeof(linklist));//创建一个头结点
linklist * temp=p;//声明一个指针指向头结点，
//生成链表
for (int i=1; i<5; i++) {
linklist *a=(linklist*)malloc(sizeof(linklist));
a->elem=i;
a->next=NULL;
temp->next=a;
temp=temp->next;
}
return p;
}我们只需在主函数中调用 initLink 函数，即可轻松创建一个存储 {1,2,3,4} 的链表，C 语言完整代码如下：
#include <stdio.h>
#include <stdlib.h>
//链表中节点的结构
typedef struct Linklist{
int elem;
struct Linklist *next;
}linklist;
//初始化链表的函数
linklist * initlinklist();
//用于输出链表的函数
void display(linklist *p);
int main() {
//初始化链表（1，2，3，4）
printf("初始化链表为：\n");
linklist *p=initlinklist();
display(p);
return 0;
}
linklist * initlinklist(){
linklist * p=NULL;//创建头指针
linklist * temp = (linklist*)malloc(sizeof(linklist));//创建首元节点
//首元节点先初始化
temp->elem = 1;
temp->next = NULL;
p = temp;//头指针指向首元节点
for (int i=2; i<5; i++) {
linklist *a=(linklist*)malloc(sizeof(linklist));
a->elem=i;
a->next=NULL;
temp->next=a;
temp=temp->next;
}
return p;
}
void display(linklist *p){
linklist* temp=p;//将temp指针重新指向头结点
//只要temp指针指向的结点的next不是Null，就执行输出语句。
while (temp) {
printf("%d ",temp->elem);
temp=temp->next;
}
printf("\n");
}程序运行结果为：
初始化链表为：
1 2 3 4
注意：如果使用带有头节点创建链表的方式，则输出链表的 display 函数需要做适当地修改：
void display(linklist *p){
linklist* temp=p;//将temp指针重新指向头结点
//只要temp指针指向的结点的next不是Null，就执行输出语句。
while (temp->next) {
temp=temp->next;
printf("%d",temp->elem);
}
printf("\n");
}链表插入元素
同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：
- 插入到链表的头部（头节点之后），作为首元节点；
- 插入到链表中间的某个位置；
- 插入到链表的最末端，作为链表中最后一个数据元素；
虽然新元素的插入位置不固定，但是链表插入元素的思想是固定的，只需做以下两步操作，即可将新元素插入到指定的位置：
- 将新结点的 next 指针指向插入位置后的结点；
- 将插入位置前结点的 next 指针指向插入结点；
例如，我们在链表{1,2,3,4}的基础上分别实现在头部、中间部位、尾部插入新元素 5，其实现过程如下图 所示：
从图中可以看出，虽然新元素的插入位置不同，但实现插入操作的方法是一致的，都是先执行步骤 1 ，再执行步骤 2。
注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，会导致插入位置后续的部分链表丢失，无法再实现步骤 1。
通过以上的讲解，我们可以尝试编写 C 语言代码来实现链表插入元素的操作：
//p为原链表，elem表示新数据元素，add表示新元素要插入的位置
linklist * insertElem(linklist * p,int elem,int add){
linklist * temp=p;//创建临时结点temp
//首先找到要插入位置的上一个结点
for (int i=1; i<add; i++) {
if (temp==NULL) {
printf("插入位置无效\n");
return p;
}
temp=temp->next;
}
//创建插入结点c
linklist * c=(linklist*)malloc(sizeof(linklist));
c->elem=elem;
//向链表中插入结点
c->next=temp->next;
temp->next=c;
return p;
}链表删除元素
从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除，但作为一名合格的程序员，要对存储空间负责，对不再利用的存储空间要及时释放。因此，从链表中删除数据元素需要进行以下 2 步操作：
- 将结点从链表中摘下来;
- 手动释放掉结点，回收被结点占用的存储空间;
其中，从链表上摘除某节点的实现非常简单，只需找到该节点的直接前驱节点 temp，执行一行程序：
temp->next=temp->next->next;
例如，从存有{1,2,3,4}的链表中删除元素 3，则此代码的执行效果如下图 所示：
因此，链表删除元素的 C 语言实现如下所示：
//p为原链表，add为要删除元素的值
linklist * delElem(linklist * p,int add){
linklist * temp=p;
//temp指向被删除结点的上一个结点
for (int i=1; i<add; i++) {
temp=temp->next;
}
linklist * del=temp->next;//单独设置一个指针指向被删除结点，以防丢失
temp->next=temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
free(del);//手动释放该结点，防止内存泄漏
return p;
}我们可以看到，从链表上摘下的节点 del 最终通过 free 函数进行了手动释放。
链表查找元素
在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的NULL（比对失败的标志）。
因此，链表中查找特定数据元素的 C 语言实现代码为：
//p为原链表，elem表示被查找元素、
int selectElem(linklist * p,int elem){
//新建一个指针t，初始化为头指针 p
linklist * t=p;
int i=1;
//由于头节点的存在，因此while中的判断为t->next
while (t->next) {
t=t->next;
if (t->elem==elem) {
return i;
}
i++;
}
//程序执行至此处，表示查找失败
return -1;
}注意：遍历有头节点的链表时，需避免头节点对测试数据的影响，因此在遍历链表时，建立使用上面代码中的遍历方法，直接越过头节点对链表进行有效遍历。
链表更新元素
更新链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。
直接给出链表中更新数据元素的 C 语言实现代码：文章来源：https://www.toymoban.com/news/detail-728212.html
//更新函数，其中，add 表示更改结点在链表中的位置，newElem 为新的数据域的值
linklist *amendElem(linklist * p,int add,int newElem){
linklist * temp=p;
temp=temp->next;//在遍历之前，temp指向首元结点
//遍历到被删除结点
for (int i=1; i<add; i++) {
temp=temp->next;
}
temp->elem=newElem;
return p;
}以上内容详细介绍了对链表中数据元素做"增删查改"的实现过程，这里是传送门链式存储结构,除此之外，想要了解更多的C,C++,嵌入式开发等相关知识的童鞋，欢迎来我的博客，我们一起讨论！接下来我会持续更新其他算法，敬请期待！文章来源地址https://www.toymoban.com/news/detail-728212.html
到了这里，关于关于链表，看这一篇就足够了！（新手入门）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
