C语言链表：万字“链表”从概念开始到实际应用的“超详细”保姆指南（如果看不懂直接评论指出来）_C

本系列为C语言数据结构的学习笔记，希望和读者们一起一劳永逸的解决C语言中的数据结构问题
第一章万字“链表”从概念开始到实际应用的“超详细”保姆指南

文章目录

C语言数据结构
前言
1、链表基础知识
- 1.1 链表是什么
- 1.2 为什么使用链表
2、常用链表
- 2.1 静态链表
- 2.2 动态链表
- - 2.2.1 单链表
  - 2.2.2 双向链表
  - 2.2.3 循环链表
3、链表 *** 作/增删改查
- 3.1 单链表
- - 3.1.1 创建单链表
  - - 3.1.1.1 头插法创建单链表
    - 3.1.1.2 尾插法创建单链表
  - 3.1.2 单链表增加结点
  - 3.1.3 单链表删除结点
  - 3.1.3 单链表查找结点位置
  - 3.1.4 单链表修改结点数据
- 3.2 双向链表
- 3.3 循环链表
4 链表具体应用
- 4.1 单链表建立学生成绩
- 4.2 freertos的双向循环链表 *** 作
总结
参考文献：

前言

本系列记录自己学习C语言数据结构的学习过程，主要是对自己学习的总结和记录，本文设置关注作者才能阅读，希望您能看完目录之后确定是否需要再点关注，最后希望能有您的赞和评论，也算是对作者的肯定！前排感谢！
希望本文的读者也能静下心来一起学习，如果有不懂或者作者写错的地方，欢迎评论指出，我们在此一起来完成一篇适合所有人学习的数据结构博客。

1、链表基础知识

本节适合阅读时间：七分钟

1.1 链表是什么

链表的本质是一个结构体，只不过这个结构体有两部分内容：

一是数据域：负责记录当前结构体所需使用的数据（数据域可以是一个简单的数据类型来记录单个数据：如int /float /char类型;也可以是复杂的数据结构：如结构体，这样可以包含更多的数据（具体数据或者功能函数）信息）。

；
二是指针域：负责记录下一个链表结点结构体的内存地址（通过指针域可以很方便的寻找到下一个链表结点所存放的数据）；

具体结构示意图如下所示：

因此，链表的本质可以理解为大量相似类型数据的集和，这些数据通过指针域进行连接；像一串自行车的链条一样，链条的链板就是指针域，而轴套部分就是数据域，整个的一小节链条就是链表的一个结点。

1.2 为什么使用链表

链表像铁链一样将数据连接在一起，很适合增加、删减 *** 作；同时链表的内存更加离散，不需要大段地内存也是一个重要的优点。

形象一点的说法参考以下例子；

EX:学生信息

试想咱们现在想做一个学生信息系统管理的系统（信息包括该生的姓名及各科成绩），首先比较容易想到的是：每个学生的数据信息比较方便易存的数据类型是结构体，因此咱们可以构造一个结构体包括学习的姓名及各科成绩；
但是如何把这些结构体进行连接形成一个整体，进而方便多个学生成绩的输入和打印呢？
首先比较容易想到的是：数组，我们可以把这些结构体的指针放到一个数组里面，这样就可以放到一起进行管理；但是数组有以下的缺点：1数组内存的大小不容易确定（内存初始化大了浪费空间；小了又不够存储数据）且数组需要的是连续的内存，2数组的增删复杂度要更高,假在你需要在a[2]处增加一个数据，我们后面的数据都需要进行相应地移后的 *** 作（换句话说：数组所有的元素所在的位置都为绝对位置，链表所在的位置为相对位置，只和该结点所在位置的前后相邻元素相关）
那么以上数组的缺点就是链表相应的优点，具体原因在后面可以慢慢体会；
现在介绍链表的 *** 作，通过链表咱们可以很方便的将学生信息放到结点的数据域中进行管理；当需要对下一个学生的信息进行 *** 作（填写或者打印）时，可以通过指针域很方便地找到下一个结点，然后对其数据域进行 *** 作；当需要删除或者增添一个学生的信息时，咱们只需要通过指针域将这个学生的结点从链表中增添（或去掉）就好（可以想象一下将一小节链条从整节链条中进行增加或去掉，只需要对这个结点的前后结点链板进行 *** 作即可，不需要对其他结点进行 *** 作）。

2、常用链表

本节建议阅读十分钟
链表主要分类为静态链表和动态链表，其中动态链表的方式有多种，但都大同小异，本文采取的分类方法如下图所示：

动态链表每个存储单元的内存都是系统动态分配获得的，是链表使用的大多数情况。

2.1 静态链表

静态链表比较基础、简单，你可以理解为一堆数组，然后通过指针域进行连接，具备链表的基础特征；

下面我们以一个简单（数据域为int型）的例子对静态链表进行说明：
1️⃣首先我们定义一个结构体作为静态链表的结点：

struct Node{
	int data;                //数据域
	struct Node* next_p;     //指针域，指向下一个结点，如果没有指向下一个结点，可以为NULL
};

2️⃣我们先定义三个不相关的结构体的结点：

struct Node Node1 = {1 ,NULL};
struct Node Node2 = {2, NULL};
struct Node Node3 = {3, NULL};

3️⃣最后我们将三个结点进行指针连接就组成了链表：

Node1.next_p = &Node2;
Node2.next_p = &Node3;

测试程序（将所有的数据域进行打印）和结果如下：

	struct Node* node = &Node1;
	while (node != NULL )
	{
		printf("%d\r\n",node->data);       //打印当前结点数据域
		node = node->next_p;               //获得下一结点
	}

总体代码如下所示：

#include "stdio.h"
#include "stdlib.h"

//定义结点类型
struct Node{
	int data;               //数据域
	struct Node* next_p;    //指针域
};

int main()
{
	struct Node Node1 = {1 ,NULL};
	struct Node Node2 = {2, NULL};
	struct Node Node3 = {3, NULL};

	Node1.next_p = &Node2;
	Node2.next_p = &Node3;

	struct Node* node = &Node1;
	while (node != NULL )
	{
		printf("%d\r\n",node->data);
		node = node->next_p;
	}

	system("pause");
    return 0;
}

2.2 动态链表

动态链表主要的特点是内存的动态申请（不需要大段的连续内存，并且需要多少结点的内存就申请多少内存）：即每次添加结点时都要进行临时的内存申请。

动态申请内存的方法一般需要以下的语句完成：

struct Node* nodex = (struct Node*)malloc(sizeof(struct Node));
/*
*malloc(sizeof(struct Node)) 表示申请(struct Node)大小的一段内存；
*(struct Node*)malloc(sizeof(struct Node)) 表示将刚刚申请的(struct Node)大小的一段内存强制转化为(struct Node*)的数据类型；这样这段内存的大小和类型都和(struct Node)一样；
*等式的左边表示将等式右边申请的内存起一个名字叫做nodex
*/

2.2.1 单链表

常见的带头结点单链表示意图如下所示：

Head名称为头指针，指向带头结点单链表的头节点。

头指针的概念非常重要，因为链表中的每个结点的内存地址都存储在前一节点的指针域中，但头节点没有前一节点，因此必须用头指针来获得其内存地址！用一句话总结其重要性为：在链表中可以没有头结点，但是不能没有头指针！！！

链表的结点主要有以下几类：头结点，中间结点，尾结点。

头结点是链表开始的第一个结点，此结点的特征是一般没有数据域，但有时也会将数据域定为链表中结点的个数，指针域指向下一个结点；
中间结点是链表的大多数结点，这类结点既有数据域储存数据，也有指针域进行结点的前后连接；
尾结点是链表的最后一个结点，此结点的特征是有数据域，但指针域指向一般为空/NULL（循环链表除外）。

除了带头结点单链表之外还有不带头结点的单链表，其主要的区别在于没有头节点，头指针直接指向开始结点。

2.2.2 双向链表

由于单链表的有向性，只能由开始结点指向结束；但反之从结尾指向开始就会非常难，为此设计了双向链表，即在单链表的基础上增加了指向前面结点的指针域。

具体示意图如下所示：

也有不带头结点的双向链表，但差异和单链表类似，故在此不做赘述。

2.2.3 循环链表

“循环”的含义是指将尾结点的指针指向头结点（不带头结点单链表指向开始结点），它的意义或者优势在于从结点任意结点位置出发都可以遍历得到整个链表的值，而普通的单链表只能遍历得到它之后的结点信息，双向链表只能一次性得到它之后或之前的值。

循环双链表的概念与区别本节的单链表类似，故不作赘述，仅留下示意图如下所示：

3、链表 *** 作/增删改查

本节建议阅读时间30分钟

3.1 单链表

本节主要介绍单链表的创建，增加结点，删减结点，改动节点，查找结点

3.1.1 创建单链表 3.1.1.1 头插法创建单链表

1️⃣ 首先我们创建一个头节点：

//创建带头结点单链表
//函数的返回类型为（struct Node *）型的函数
struct Node * creatList()
{
	struct Node * headNode = (struct Node * )malloc(sizeof(struct Node));  //开辟了一片内存，将其声明为头结点

	//headNode->data = 1; 头结点没有数据域，故将其注释掉
	headNode->next_p = NULL;  //由于只有一个结点，没有下一个结点，因此指针域为NULL

	return headNode;
}

2️⃣ 通过头插法插入一个新节点；
头插法概念如下图所示：在头结点的后面增加新增的结点（同理尾插法的概念时在尾结点的后面新增结点）。

代码如下所示：

//创建一个普通的单结点
struct Node * creatNode(int data)
{
	struct Node * newNode = (struct Node *)malloc(sizeof(struct Node));
	
	newNode->data = data;
	newNode->next_p = NULL;

	return newNode;
}

//从头结点处插入新结点
//思路是先创建一个新结点，然后将其插入到头节点的后面
void insertNodeByHead(struct Node * headNode,int data)
{
	struct Node * newNode = creatNode(data);
	
	newNode->next_p = headNode->next_p;  //此行程序和下一行不可以交换，一定要先记录下来当前链表的next_p，即原来第二个结点的地址，上图步骤1
	headNode->next_p = newNode;          //将新结点添加仅原链表中，上图步骤2
}

3️⃣ 在main函数中持续进行头插法就可以创建单链表，代码如下所示：

int main()
{
	struct Node * headNode = creatList();
	insertNodeByHead(headNode, 3);   //添加新结点HeadNode->3
	insertNodeByHead(headNode, 2);   //添加新结点HeadNode->2->3
	insertNodeByHead(headNode, 1);   //添加新结点HeadNode->1->2->3
	
	system("pause");
    return 0;
}

4️⃣最后添加测试函数，代码如下所示：

//有头结点的链表打印函数
void printListWithHead(struct Node * headNode)
{
	struct Node * moveNode_p = headNode->next_p; //头节点中没有数据域，从它的下一个结点开始打印

	while(moveNode_p)            //当前结点不为空时执行下面语句
	{
		printf("%d",moveNode_p->data);     //打印当前的数据域
		moveNode_p = moveNode_p->next_p;   //指向下一结点
		printf("\r\n");
	}
	printf("\r\n");
}

单链表头插法的综合代码如下所示：

#include "stdio.h"
#include "stdlib.h"

//定义结点类型
struct Node{
	int data;               //数据域
	struct Node* next_p;    //指针域
};

//创建带头结点单链表
struct Node * creatList()
{
	struct Node * headNode = (struct Node * )malloc(sizeof(struct Node));  //开辟了一片内存，将其声明为头结点

	//headNode->data = 1; 头结点没有数据域，故将其注释掉
	headNode->next_p = NULL;

	return headNode;
}

//创建结点
struct Node * creatNode(int data)
{
	struct Node * newNode = (struct Node *)malloc(sizeof(struct Node));

	newNode->data = data;
	newNode->next_p = NULL;

	return newNode;
}

//从头结点处插入新结点
void insertNodeByHead(struct Node * headNode,int data)
{
	struct Node * newNode = creatNode(data);

	newNode->next_p = headNode->next_p;  //此行程序和下一行不可以交换，一定要先记录下来当前链表的next_p，即原来第二个结点的地址
	headNode->next_p = newNode;          //将新结点添加仅原链表中
}

//有头结点的链表打印函数
void printListWithHead(struct Node * headNode)
{
	struct Node * moveNode_p = headNode->next_p; //头节点中没有数据域，从它的下一个结点开始打印

	while(moveNode_p)
	{
		printf("%d",moveNode_p->data);
		moveNode_p = moveNode_p->next_p;
		printf("\r\n");
	}
	printf("\r\n");
}

int main()
{
	struct Node * headNode = creatList();
	insertNodeByHead(headNode, 3);
	insertNodeByHead(headNode, 2);
	insertNodeByHead(headNode, 1);

	printListWithHead(headNode);

	system("pause");
    return 0;
}

代码的测试结果如下所示：

3.1.1.2 尾插法创建单链表

尾插法创建单链表的过程与上一节头插法类似，主要难点在于通过遍历寻找尾节点。

其核心代码如下所示：

//尾插法增加新结点
void insertNodeByEnd(struct Node * headNode, int data)
{
	struct Node * endNode_p = creatNode(data);   //创建一个新的结点用来插入
	struct Node * moveNode_p = headNode; //头节点中没有数据域，从它的下一个结点开始打印，它的作用是寻找尾节点

	while (moveNode_p->next_p)           //如果当前结点的下一指针域不为空：即有下一结点执行下面语句
	{
		moveNode_p = moveNode_p->next_p;  //令moveNode_p指向下一节点
	}

	moveNode_p->next_p = endNode_p;    //上图步骤3
}

单链表尾插法的综合代码如下所示：

#include "stdio.h"
#include "stdlib.h"

//定义结点类型
struct Node{
	int data;               //数据域
	struct Node* next_p;    //指针域
};

//创建带头结点单链表
struct Node * creatList()
{
	struct Node * headNode = (struct Node * )malloc(sizeof(struct Node));  //开辟了一片内存，将其声明为头结点

	//headNode->data = 1; 头结点没有数据域，故将其注释掉
	headNode->next_p = NULL;

	return headNode;
}

//创建结点
struct Node * creatNode(int data)
{
	struct Node * newNode = (struct Node *)malloc(sizeof(struct Node));

	newNode->data = data;
	newNode->next_p = NULL;

	return newNode;
}

//尾插法增加新结点
void insertNodeByEnd(struct Node * headNode, int data)
{
	struct Node * endNode_p = creatNode(data);
	struct Node * moveNode_p = headNode; //头节点中没有数据域，从它的下一个结点开始打印

	while (moveNode_p->next_p)
	{
		moveNode_p = moveNode_p->next_p;
	}

	moveNode_p->next_p = endNode_p;
}

//有头结点的链表打印函数
void printListWithHead(struct Node * headNode)
{
	struct Node * moveNode_p = headNode->next_p; //头节点中没有数据域，从它的下一个结点开始打印

	while(moveNode_p)
	{
		printf("%d",moveNode_p->data);
		moveNode_p = moveNode_p->next_p;
		printf("\r\n");
	}
	printf("\r\n");
}

int main()
{
	struct Node * headNode = creatList();
	insertNodeByEnd(headNode, 3); //H->3
	insertNodeByEnd(headNode, 2); //H->3->2
	insertNodeByEnd(headNode, 1); //H->3->2->1

	printListWithHead(headNode);

	system("pause");
    return 0;
}

测试结果如下图所示：

3.1.2 单链表增加结点

在前文我们已经介绍了链表的头插法与尾插法，此节的增加结点是从链表的中间的指定位置插入新结点，同理只要将新增结点前面结点的指针域指向新增结点同时新增结点的指针域指向下一结点就可以了。

具体过程如下图所示：

由上图可知增加结点所需要的参数为（链表名称，新结点数据域的值，新插入结点的位置）
核心代码如下文所示：

//从链表中间增添新结点
void insertNode(struct Node * headNode, int data, int loc)
{
	struct Node * newNode = creatNode(data);
	struct Node * moveNode = headNode;

	for (int i = 0;i < loc;i++)
	{
		if (moveNode == NULL)
		{
			printf("位置输出错入");
			return;
		}
		moveNode = moveNode->next_p;
	}

	newNode->next_p = moveNode->next_p;  //此行程序和下一行不可以交换，一定要先记录下来当前链表的next_p，即原来第二个结点的地址，上图步骤1
	moveNode->next_p = newNode;          //将新结点添加仅原链表中，上图步骤2
}

//main函数设置如下所示：
int main()
{
	struct Node * headNode = creatList();
	insertNodeByEnd(headNode, 3); //H->3
	insertNodeByEnd(headNode, 2); //H->3->2
	insertNodeByEnd(headNode, 1); //H->3->2->1

	insertNode(headNode, 4, 1);   //H->4->3->2->1

	printListWithHead(headNode);

	system("pause");
    return 0;
}

测试结果如下所示：

3.1.3 单链表删除结点

单链表删除结点的方法也十分简单，只需要将要删除结点的前一结点的指针域指向要删除结点的后一结点即可。

具体实现的示意图如下所示：

核心代码如下文所示：

//从链表中间删除结点
void deleteNode(struct Node * headNode, int loc)
{

	struct Node * moveNode = headNode;

	for (int i = 0;i < loc;i++)
	{
		if (moveNode == NULL)
		{
			printf("位置输出错入");
			return;
		}
		moveNode = moveNode->next_p;
	}
	moveNode->next_p = (moveNode->next_p)->next_p;
}


//main函数相应的代码如下所示：
int main()
{
	struct Node * headNode = creatList();
	insertNodeByEnd(headNode, 3); //H->3
	insertNodeByEnd(headNode, 2); //H->3->2
	insertNodeByEnd(headNode, 1); //H->3->2->1

	insertNode(headNode, 4, 1);   //H->4->3->2->1

	deleteNode(headNode, 0);     //H->4->2->1
	printListWithHead(headNode);

	system("pause");
    return 0;
}

测试结果如下所示：

3.1.3 单链表查找结点位置

主要通过遍历的方法得到结点的位置，通过当前结点数据域与所要寻找的值进行匹配得到结点的位置，核心代码与main函数调用如下所示：

//从链表中间寻找结点
int findNode(struct Node * headNode, int data)
{
	int i=1;
	struct Node * moveNode = headNode->next_p;

	while (moveNode)
	{
		if (moveNode->data == data)
		{
			return i;
		}
		moveNode = moveNode->next_p;
		i++;
	}

	return -1;
}

//main函数调用如下所示：
int main()
{
	struct Node * headNode = creatList();
	insertNodeByEnd(headNode, 3); //H->3
	insertNodeByEnd(headNode, 2); //H->3->2
	insertNodeByEnd(headNode, 1); //H->3->2->1

	insertNode(headNode, 4, 1);   //H->4->3->2->1

	deleteNode(headNode, 0);     //H->4->2->1
	printListWithHead(headNode);

	printf("1的位置为：%d",findNode(headNode, 1));

	system("pause");
    return 0;
}

测试结果如下所示：
单

3.1.4 单链表修改结点数据

修改结点的方式主要有两种，一种是修改特定位置的值，核心代码及测试结果如下所示：

//从链表特定位置修改结点
void updataNode(struct Node * headNode, int loc, int data)
{
	struct Node * moveNode = headNode;

	for (int i = 0;i < loc;i++)
	{
		if (moveNode == NULL)
		{
			printf("位置输出错入");
			return;
		}
		moveNode = moveNode->next_p;
	}
	moveNode->data = data;    //对值进行修改
}

int main()
{
	struct Node * headNode = creatList();
	insertNodeByEnd(headNode, 3);
	insertNodeByEnd(headNode, 2);
	insertNodeByEnd(headNode, 1);

	insertNode(headNode, 4, 1);

	deleteNode(headNode, 0);


	printListWithHead(headNode);

	printf("1的位置为：%d\r\n\r\n\r\n",findNode(headNode, 1));

	updataNode(headNode, 1, 5);
	printListWithHead(headNode);
	printf("1的位置为：%d",findNode(headNode, 1));

	system("pause");
    return 0;
}

另一种是统一修改特定的值(如将链表中的数据3统一改为4)，可以根据本文的查找 *** 作进行简单修改，在此不作赘述。

3.2 双向链表

由于双向链表与单向链表的创建及 *** 作十分相似，因此本节只对其基本结构进行介绍，具体 *** 作可以参考本文4.2 freertos的双向循环链表 *** 作。

双向链表的结点具体结构如下所示：

//定义结点类型
struct Node{
	int data;               //数据域
	struct Node* next_p;    //指向后面结点指针域
	struct Node* prior_p;   //指向前面结点指针域
};

3.3 循环链表

循环链表的 *** 作与单链表 *** 作十分类似，具体 *** 作可以参考本文4.2 freertos的双向循环链表 *** 作。

4 链表具体应用 4.1 单链表建立学生成绩

本节主要参考[b站视频，一小时学会单链表](https://www.bilibili.com/video/BV1Rb411F738?spm_id_from=333.337.search-card.all.click)，此处未改信息，如有侵权，联系我会主动修改
首先定义学生的结构体即链表的结点：

//定义学生类型
struct student
{
	char name[20];
	int num;
	int score;
}

剩下的 *** 作和上一节的单链表 *** 作类似，具体代码如下所示：

#include "stdio.h"
#include "stdlib.h"

//定义学生类型
struct student
{
	char name[20];
	int num;
	int score;
};


//定义结点类型
struct Node{
	struct student data;               //数据域
	struct Node* next_p;    //指针域
};

//创建带头结点单链表
struct Node * creatList()
{
	struct Node * headNode = (struct Node * )malloc(sizeof(struct Node));  //开辟了一片内存，将其声明为头结点

	//headNode->data = 1; 头结点没有数据域，故将其注释掉
	headNode->next_p = NULL;

	return headNode;
}

//创建结点
struct Node * creatNode(struct student data)
{
	struct Node * newNode = (struct Node *)malloc(sizeof(struct Node));

	newNode->data = data;
	newNode->next_p = NULL;

	return newNode;
}

//从头结点处插入新结点
void insertNodeByHead(struct Node * headNode,struct student data)
{
	struct Node * newNode = creatNode(data);

	newNode->next_p = headNode->next_p;  //此行程序和下一行不可以交换，一定要先记录下来当前链表的next_p，即原来第二个结点的地址
	headNode->next_p = newNode;          //将新结点添加仅原链表中
}

//从链表中间删除结点
void deleteNode(struct Node * headNode, int num)
{

	struct Node * moveNode = headNode->next_p;
	struct Node * moveNodeFront = headNode;

	if(moveNode ==NULL)
	{
		printf("无法删除链表为空");
	}
	else
	{
		while(moveNode->data.num != num)	
		{
			moveNodeFront = moveNode;
			moveNode = moveNode->next_p;
			if(moveNode == NULL)
			{
				printf("没有找到相关信息，无法删除\n");
				return;
			}
		}

		moveNodeFront->next_p = moveNode->next_p;
		free(moveNode);
	}
}


//打印函数
void printListWithHead(struct Node * headNode)
{
	struct Node * moveNode_p = headNode->next_p; //头节点中没有数据域，从它的下一个结点开始打印
	printf("name\tnum\tscore\n");
	while(moveNode_p)
	{
		printf("%s\t%d\t%d\n",moveNode_p->data.name,moveNode_p->data.num,moveNode_p->data.score);
		moveNode_p = moveNode_p->next_p;
	}
	printf("\n");
}


int main()
{
	struct Node * List = creatList();
	struct student info;

	while(1)
	{
		printf("请输入学生的姓名，学号，成绩:");
		setbuf(stdin,NULL);
		scanf("%s%d%d",info.name,&info.num,&info.score);

		insertNodeByHead(List,info);
		setbuf(stdin,NULL);
		printf("continue(Y/N)?\n");
		int choice = getchar();
		if(choice == 'N'||choice == 'n')
		{
			break;
		}
	}

	system("pause");
    return 0;
}

测试结果如下所示：

4.2 freertos的双向循环链表 *** 作

考虑到本文的时长，怕读者阅读比较疲倦，正在想要不要写这一部分内容，在这写或者新开一个系列freertos源码的文章，希望评论高速作者。

总结

本文对c语言链表的特性及 *** 作进行了详细的介绍和说明。

参考文献：

http://data.biancheng.net/view/5.html
b站视频，一小时学会单链表

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/607320.html

C语言链表：万字“链表”从概念开始到实际应用的“超详细”保姆指南（如果看不懂直接评论指出来）

发表评论

评论列表（0条）