C语言加强篇——（1）学习笔记 之 变量、指针、关键字
C语言加强篇——（2）学习笔记 之 结构体、结构体指针、函数指针
C语言加强篇——（3）学习笔记 之 链表的增、删、改、查
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。
上面对链表的解释是百度百科上的解释，这看起来是不是比较难理解呢 ？接下来我带领大家来通过通俗易懂的例子来深入学习链表及链表的相关操作。
谍战片大家都看过吧，接下来将以谍战片里的某个身份来深入的学习链表；
以谍战片中的间谍来形象地表述链表。
间谍有自己下线间谍，每个间谍都知道怎么去找自己的下线间谍；而下线间谍不知道怎么去找他的上线间谍；他们单线联系；单线联系的间谍有个领导；
其中，领导就是头节点，最后一个间谍就是尾节点，知道怎么去找自己的下线就是指针，间谍传递的信息、指令就是数据。
也就是说这个节点，既有自己传递的信息（数据），又知道如何去找自己的下线间谍（指向下一个节点的指针）。如下图：
这些节点不就是我们上一篇文章中所讲述的结构体吗 ！！！是的。
那么，接下来我们就可以定义一个间谍（节点）结构体：
/*间谍（节点）结构体*/
typedef struct spy {
char name[8]; //间谍的名字
struct spy * next; //下一个间谍的地址，指针指向的是下一个间谍的地址
}spy, *p_spy;
定义完间谍结构体后，我们就可以来定义间谍了：
p_spy head; //定义一个间谍的头头的地址（间谍的头头也是间谍所以定义间谍结构体指针）
/*定义间谍；在去告诉间谍他的下线的地址*/
spy spy1 = {"spy1", NULL};
spy spy2 = {"spy2", NULL};
spy spy3 = {"spy3", NULL};
spy spy4 = {"spy4", NULL};
head = &spy1; //间谍头头的地址指向间谍1
spy1.next = &spy2; //spy1.next 表示间谍1的下一个间谍的地址，spy2要取地
spy2.next = &spy3;
spy3.next = &spy4;
spy4.next = NULL; //最后一个间谍没有下线了，指向空
我们再次来看一下这个关系图：
这就是一个单链表，是不是这样理解起来简单多了呢 ！！！
我们把单链表定义出来了，当我们需要将这个链表里的数据全部打印出来时，就需要对链表进行遍历，下面是链表的遍历：
while(head) //把头指针作为遍历链表的指针，当指针指向空时，链表结束；
{
printf("%s\r\n", head->name); //打印当前节点名字
head = head->next; //打印完成后指针指向当前的下一个结点
}
节点的插入我们可以分为三类 ：① 在链表的头部插入节点。 ② 在链表的中间插入节点。③ 在链表的尾部插入节点；我们接下来将这三类插入节点的形式封装成一个插入节点函数，废话不多说先看图解详情，再看代码能够更直观，更清晰地了解链表的插入：
原链表图解，如下图：
链表的插入需要先在内存中申请一个节点结构体类型的空间，将需要插入的节点信息存入申请的空间中，下面是插入不同位置的图解：
① 在链表的头部插入节点图解
在链表的头部插入节点就应该，先将节点1的地址给新插入节点的 next ，再让头指针 head 指向新节点。最后返回头指针。
② 在链表的中间插入节点图解
在链表的中间插入节点应该，先找到插入位置的前一个位置，然后将他的下一个节点地址给到新节点的next，最后将新节点的地址给前一个节点的next。
③ 在链表的尾部插入节点图解
在链表的尾部插入节点 与 在链表的中间插入节点是一样的，只不过一个是将空地址给新节点的next，一个是将 地址给新节点的next；
下面是插入节点函数的代码：
/**
* @说明 调用函数 insert_spy 可以在链表的任意位置插入节点
* @参数 head : head 是节点结构体指针类型参数，传入的值是：现有链表的头指针
* @参数 n : n 是插入节点的位置。如：在链表头节点前插入就传入 1 ；也就是说第 n 个节点的位置是新插入的节点。
* @返回值 返回节点结构体指针类型，返回的是头节点指针。（当在链表的头部插入需要返回新的头部节点）
*/
p_spy insert_spy(p_spy head, int n)
{
int i; //定义 i 为了查找插入位置的前一个节点
p_spy p, pr; //定义节点结构体指针 p 指向新节点， pr 用来指向插入位置之前的节点
p = (p_spy)malloc(sizeof(spy)); //要申请一个空间用来存放新节点，让 p 指向新建节点的地址
printf("输入新节点的名字:\r\n");
scanf("%s", p->name); //将输入的名字存放至新节点的 name 里。
pr = head; //赋初始值，从头节点开始查找插入的位置
i = 1; // i 从 1 开始循环，来寻找插入的地址
if(n == 1 && pr != NULL) //这个判断是用来判断是否在头节点的位置插入新节点，n == 1 是在头节点插入新节点
{
p->next = pr; //依据前面图解对照写出指针的指向代码
head = p;
}else
{
while(i < n-1 && pr != NULL) //找到插入节点的前一个节点位置
{
pr = pr->next; //pr 后移，直至找到插入位置的前一个位置
i++;
}
if(pr != NULL) //插入位置的前一个位置不为空，可以是链表的末尾插入
{
p->next = pr->next; //依据前面图解对照写出指针的指向代码
pr->next = p;
}else
{
printf("节点不存在\r\n");
}
}
return head; //返回头节点，如在头节点插入新节点，head 会变化，所以返回
}
节点的删除和节点的插入类似 ：① 在链表的头部删除节点。 ② 在链表的中间删除节点。③ 在链表的尾部删除节点；我们还是来先看图解，在看代码：
① 在链表的头部删除节点图解。
在链表的头部删除节点应该，将头指针 head，指向原来头节点的下一个地址，然后把原头节点所在的空间释放掉。
② 在链表的中间删除节点图解。
在链表的中间删除节点应该，先找到删除位置的节点以及删除位置之前节点的位置，然后让删除节点之前位置的 next 指向删除的节点的 next，最后把删除的节点空间释放掉。
③ 在链表的尾部删除节点
在链表的尾部删除节点 与 在链表的中间删除节点是一样的道理。
下面是删除节点函数的代码：
/**
* @说明 调用函数 delete_spy 可以在链表的任意位置删除节点
* @参数 head : head 是节点结构体指针类型参数，传入的值是：现有链表的头指针
* @参数 n : n 是要删除节点的位置。如：在将链表头节点删除就传入 1 ；也就是说第 n 个节点的位置是要删除的节点。
* @返回值 返回节点结构体指针类型，返回的是头节点指针。（当在链表的头部删除需要返回新的头部节点）
*/
p_spy delete_spy(p_spy head, int n)
{
int i; //定义 i 为了查找删除位置的节点
p_spy p, pr; // p 指向删除的节点， pr 指向删除之前的节点
pr = head;
p = head; //赋初始值
i = 1;
if(n == 1 && p != NULL) //n == 1 说明要删除头节点
{
head = p->next; //将原头节点的 next， 给新的头节点指针
free(p); // free(); 释放空间函数
}else
{
while(i < n && p != NULL) // 找到要删除的节点指针 p,,,以及要删除节点之前的节点指针 pr
{
pr = p;
p = p->next;
i++;
}
if(p != NULL)
{ //不理解的可以对照上面图解，带入具体示例来辅助学习
pr->next = p->next; //将删除节点的 next 给删除节点之前的 next
free(p); //将删除的节点空间释放掉。
}else
{
printf("删除的节点不存在\r\n");
}
}
return head; //最后返回头指针
}
节点的修改只需要找到要修改节点的位置，将其的数据就行修改就行了，下面直接上代码：
/**
* @说明 调用函数 delete_spy 可以在链表的任意位置删除节点
* @参数 head : head 是节点结构体指针类型参数，传入的值是：现有链表的头指针
* @参数 n : n 是要修改节点的位置。如：在将链表头节点修改就传入 1 ；也就是说第 n 个节点的位置是要修改的节点。
* @返回值 无
*/
void change_spy(p_spy head, int n)
{
p_spy p; //定义要修改的节点指针 p
int i = 1;
while(i < n && p != NULL) //查找要修改的节点的位置 n
{
p = p->next;
i++;
}
if(p != NULL)
{
printf("该节点的原始值为：%s\r\n", p->name); //可以将原始值打印出来，看是否位置找的正确
printf("请输入修改后的值：\r\n"); // 输入修改后的值
memset(p->name, '\0', sizeof(p->name)); //将原始值清空，防止新输入字符比原字符短，防止出现错误
scanf("%s", p->name);
}else
{
printf("该节点不存在\r\n");
}
}
在学习完链表的增加、删除、修改后，节点的查找就不用再去仔细的详解了，请看上面代码。
对比单链表，双链表就是节点既有下一个节点的地址，又有上一个节点的地址，其双链表图解如下：
对比单链表的各种操作我们也不难写出双链表对应的函数，在这里就不详细写双链表了。
本文主要写单链表的遍历以及增、删、改、查的操作。感谢大家观看
本专栏文章：
C语言加强篇——（1）学习笔记 之 变量、指针、关键字
C语言加强篇——（2）学习笔记 之 结构体、结构体指针、函数指针
C语言加强篇——（3）学习笔记 之 链表的增、删、改、查