C语言数据结构单链表接口函数全面讲解教程 C语言数据结构单链表接口函数

前言
一、链表的概念及结构

1.概念

二、链表的使用

1.遍历整个链表
2.尾插
3.头插
4.头删
5.尾删
6.任意位置插入数据
7.任意位置删除数据

后记

前言上一期数据结构专栏我们学习了顺序表后：C语言数据结构顺序表
在运用时，细心的同学可能会发现，如果要头插、尾插或者任意位置。如果原先的空间已经被占满了，你是需要扩容的，动态链表扩容往往是2倍，但是扩容后，如果后面没有使用完全扩容后空间就会造成空间浪费，为了解决这个问题，我们今天将学习链表。
提示：以下是本篇文章正文内容，下面案例可供参考

一、链表的概念及结构
1.概念
链表是一种物理存储结构上的非连续。非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

文章图片

（图片来自比特就业课）
上图是一个普通链表，它物理上是不连续的，那怎么让这些数据建立联系呢？链表每个位置会存放两个数据——1个是数据，另1个是指针

typedef int SLTDataType; //这里是方便将来改数据类型，在这里把int修改一下即可typedef struct SlistNode//一个位置放多个数据用结构体{ int data; struct SlistNode*next; //指针是指向下一个节点，下一个节点也是结构体，所以这里是结构体指针}SLTNode; //将结构体类型名用SLTNode重命名

我们用一张图来深入了解一下它的逻辑结构：

文章图片

图示是链表的三个相连元素，第一个元素存放数据1和第二个元素的地址，然后以此类推。那到这里可能有同学会问：“那每个都是有存放下一个地址，最后一个节点存放谁的地址？”是这样的，最后一个节点存放的是NULL空指针，空指针也是作为链表结尾的标记
到这里，我们知道，链表的每个节点放的是当前节点内容和下一个节点的指针，那我们怎么找到这条链表呢？毕竟你第一个节点放的是第二个节点的指针，事实上，我们会定义一个指针指向第一个节点，以此来确定该链表

二、链表的使用
1.遍历整个链表
代码如下（示例）：

void SListPrint(SLTNode*phead){ SLTNode*cur = phead; while (cur != NULL) {printf("%d", cur->data); cur = cur->next; }}

文章图片

我们以这张图来理解一下这段代码，我们创建一个结构体指针cur，并把链表首元素地址赋给cur，也就是说，cur指向了链表的首节点，我们知道首节点里是有第二个节点的地址的，我们通过cur = cur->next; 可以找到第二段节点，以此类推。

2.尾插

文章图片

（图片来自比特就业课）
想要尾插一个节点，我们首先要malloc（扩容函数）一块空间出来，开辟出那块空间之后，要把新节点与链表连接起来，就需要链表尾部节点的地址，我们用循环遍历得到，然后把新节点地址赋给之前链表的尾部节点即可
代码如下（示例）：

void SListPushBack(SLTNode**pphead, SLTDataType x){ SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode)); //开辟一块大小为一个SLTNode类型的空间出来，并强制转换成结构体指针赋给newnode newnode->data = https://www.it610.com/article/x; newnode->next = NULL; if (*pphead == NULL)//防止一开始链表里面什么也没有， {//由于pphead是头节点的地址的地址，*解引用一下得到头结点的地址*pphead = newnode; } else {SLTNode*tail = *pphead; while (tail->next != NULL)//寻找尾节点的指针{tail = tail->next; }tail->next = newnode; //新增的节点地址赋给尾结点存储 }}

这里为什么用二级指针传参？解释如下：
我们进行尾插时，要先找到链表所在嘛，然后这个是靠链表头节点地址确定的，你传了一个地址过去，注意这个地址是实参，你实参过去函数里会再创建一个形参也是这个地址，然后进行操作，改变的是形参里的东西，实参不会受影响。这里也就是传值调用和传址调用的区别，为了形参可以影响到实参，我们用传址调用，也就是传地址的地址

3.头插

文章图片

（图片来自比特就业课）
我们假设现在要在一个链表前面插入0这个数据（如上图所示），0所在地址为0x0006708，那是不是要把原链表首节点地址放到0这个节点里面，然后头节点地址更新为0这个新节点的地址。如下图：

文章图片

ps:plist/phead表示链表首节点地址
代码如下（示例）：

void SListPushFront(SLTNode**pphead, SLTDataType x){ SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode)); //开辟一块大小为一个SLTNode类型的空间出来，并强制转换成结构体指针赋给newnode newnode->data = https://www.it610.com/article/x; //插入节点的数据 newnode->next = *pphead; //把原先节点首元素地址赋给新节点 *pphead = newnode; //新节点首元素地址用新插入的节点地址赋值}

4.头删
关于头删，很多同学可能有一种想法，就是直接把头结点free（对动态分配的内存进行释放）掉，剩下的就是我们需要的链表。但这里会有一个问题，就是你把头节点去了，因为链表是用地址连接的，我们原本是用头节点地址找到该链表，现在头节点去掉了，我们怎么知道剩下的链表在哪里。所以这里的解决方案是，先把第二个节点地址保存起来然后再释放掉头节点
代码如下（示例）：

void SListPopFront(SLTNode**pphead){ SLTNode*next = (*pphead)->next; free(*pphead); *pphead = next; }

5.尾删
尾删和头删有同样的问题，我们能不能直接把尾部节点给free掉？答案也是不可以的，同学你细想一下，尾部节点是不是连接着倒数第二个节点，而倒数第二个节点保存着尾结点地址，你把尾结点free掉了，那倒数第二个节点保存的就是野指针了，这显然是不行的，所以我们需要把倒数第二个节点存储的指针变成空指针，然后free掉尾结点

void SListPopBack(SLTNode**pphead){ if (*pphead == NULL)//如果节点本来就没有，那就没有删除的说法了 {return; } else if ((*pphead)->next == NULL)//如果本来链表只有一个节点，你删除一个，之前会有一个指针指向首节点来记录这个链表，你现在把唯一的节点删除了，那个记录链表的指针就成野指针了 {free(*pphead); *pphead = NULL; } else {SLTNode*prev = NULL; //prev为tail前个节点指针SLTNode*tail = *pphead; while (tail->next != NULL){prev = tail; tail = tail->next; }free(tail); prev->next = NULL; }}

这里还是有注意的点的，比如你要删除的链表本来就是空链表，删除就无从谈起了，还有就是原先链表只有一个节点，你删除一个，之前会有一个指针指向首节点来记录这个链表，你现在把唯一的节点删除了，那个记录链表的指针就成野指针了

6.任意位置插入数据

文章图片

上图红色是原有链表，我们要在2和3直接插入一个30怎么做？首先我们要把2、30、3这3个节点连接起来，也就是说，2节点要指向30这个节点，30这个节点要指向3这个节点。这里如何操作呢？我们需要设计一个函数先找到2节点和3节点的地址，然后进行插入操作
查找函数和插入函数如下

SLTNode* SListFind(SLTNode*phead, SLTDataType x)//查找链表{ SLTNode*cur = phead; while (cur)//非空指针则进行循环 {if (cur->data =https://www.it610.com/article/= x)//给定链表中一个数据进行查找{return cur; //返回所查找位置指针}cur = cur->next; } return NULL; }void SListInsert(SLTNode**pphead,SLTNode*pos, SLTDataType x)//在pos前插入x，x是要插入的数{ if (pos == *pphead)//原链表只有1个节点 {SListPushFront(pphead, x); } else {SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode)); //开辟一块大小为一个SLTNode类型的空间出来，并强制转换成结构体指针赋给newnodenewnode->data = https://www.it610.com/article/x; newnode->next = NULL; //开辟1个新节点SLTNode*prev = *pphead; while (prev->next != pos){prev = prev->next; }prev->next = newnode; newnode->next = pos; //把新节点连接上去 }}

两个函数一起调用是这样的

if (pos)//防止该位置是空指针 {SlistInsert(&plist, pos, 30); } SListPrint(&plist); }

7.任意位置删除数据

文章图片

比如说我们现在要把3删除，那这里就会出现一个需要：3删除了，要把2和4连接起来，然后把3节点释放掉

void SListErase(SLTNode**pphead, SLTNode*pos)//删除pos位置的值{ SLTNode*prev = *pphead; while (prev->next != pos)//找到3节点的位置 {prev = prev->next; } prev->next = pos->next; //prev是2，pos是3，pos->next是4，要把4接上2 free(pos); //2和4接上之后就可以free掉3了}

ps:上述prev是2，pos是3这种是方便同学你理解，并不特指它真的是2和3
然后这里进行函数调用的时候，依然需要进行find定位一下需要删除位置地址