1 链表的概念

链表是线性表的一种，其物理存储结构上是非连续、非顺序的存储结构，数据元素的逻辑存储结构是通过链表中指针链接次序实现的。即链表中：
（1）物理结构：不是线性的
（2）逻辑结构：一定是线性的
链表是由一个一个节点（结点）构成的，可以类比春运前与春运后火车的车厢数量，每一个车厢都可看作是一个节点，春运时就增加车厢数（节点数）来运送更多乘客（存储更多数据），非春运时就减少车厢数，可保证基本运作即可。
单链表中每一个节点是由两部分组成，第一是该节点所要存储的数据，第二是该节点所指向的下一个节点的指针（地址）。

具体代码如下：

typedefintSLTDataType;typedefstructSListNode{ SLTDataType data;structSListNode*next;//指向下一节点指针//在指向下一节点指针这里，它的类型要用重命名前的结构体类型}SLTNode;

注意，在指向下一节点指针这里，它的类型之所以不能使用重命名后的结构体类型SLTNode是因为在系统读取到该行时还没完成重命名的操作，故只能使用重命名前的名称struct SListNode来定义类型。

2 节点创建函数与链表打印函数

2.1 节点创建函数

在上面我们只是定义了节点的结构，但并没有真正创建节点。故我们自定义一个函数来完成这部分操作。既然要创建节点，那么就需要申请空间，因为此时不同于数组扩容，链表的物理结构并不是连续的，而是可以通过指针将每一个碎片化的节点连接起来，所以直接使用malloc来进行空间申请即可。这一部分与顺序表中的空间检查函数很相似。

//节点创建函数SLTNode*SLTBuyNode(SLTDataType x)//形参部分为data要初始化的值//下一节点部分也不知道指向哪里，先置为NULL即可{ SLTNode*newnode =(SLTNode*)malloc(sizeof(SLTNode));//malloc申请单链表节点空间if(newnode ==NULL)//如果申请失败，跳出函数{ perror("malloc fail !");exit(1);}//申请成功则进行对应的初始化newnode->data =x;newnode->next =NULL;//指向下一节点部分置为空returnnewnode;//将创建的节点作为返回值返回到调用处}

2.2 链表打印函数

在上文中我们已知，链表是靠指针来完成次序的连接，其无法做到任意访问，而是必须先访问前一个节点后再去访问后一个节点。比如，我们将第一个节点所对应的节点地址设为phead，那么下一个节点就是phead->next，再后面一个节点为phead->next->next，以此类推。
在上面的那种访问方式中，当我们要访问第n个节点时，phead后面会跟（n-1）个next。如此就显得非常冗余，所以我们可以另辟蹊径，用一个临时节点来做为过度节点（我们设为pcur），将链表的头节点赋值给pcur，然后通过循环让pcur不断指向后面的next完成对链表的遍历。实现如下：

SLTPrint(SLTNode*phead){ SLTNode*pcur =phead;//通过一个过渡节点的嫁接转换完成对链表的遍历访问while(pcur)//等价于pcur != NULL{ printf("%d->",pcur->data);pcur =pcur->next;}//如果传过来的本来就是空节点，那么就无法进入循环，打印为空printf("NULL\n");}

3 单链表尾插法与头插法

3.1 尾插函数

在原链表之尾插入一个新的节点，首先我们要调用节点创建函数建立一个新的节点，然后对原链表进行遍历找尾，最后将尾节点的next指向新创建的节点即可。
请审读下面尾插函数，分析其是否存在问题。

SLTNode*PushBack(SLTNode*phead,SLTDataType x){ //判断传参是否为空assert(phead);//创建要尾插的节点SLTNode*newnode =SLTBuyNode(x);//找尾SLTNode*ptail =phead;//思考此处循环判断条件应该是什么while(ptail->next)//若将ptail != NULL 设置为条件，当循环到尾节点时，此时不为空，会继续到后面的空节点，而此时这个空节点就不是链表的尾节点了。//故应设置为ptail->next != NULL，当循环到尾节点时，ptail->next == NULL 跳出循环，然后再将ptail->next赋值为newnode即完成尾插。{ ptail =ptail->next;//没找到尾节点就不断向后遍历}ptail->next =newnode;}

上面尾插程序看似十分完美，其实存在两点严重的问题：

1. 当链表为空链表时，phead与ptail都会成为空指针NULL，那么在while中的条件判断就成为了对空指针解引用的非法访问。
2. 在尾插函数中，我们想通过修改形参中的链表来完成实参中链表的修改，那么在形参中可以用一级指针接收传参吗？用一级指针接收传参可以保证实参改变吗？

我们先来解决第一个问题，既然有空链表的这种情况，那么就使用一个条件分支来区别二者（空链表与非空链表）。

voidPushBack(SLTNode*phead,SLTDataType x){ //判断传参是否为空assert(phead);//创建要尾插的节点SLTNode*newnode =SLTBuyNode(x);//空链表与非空链表区分if(phead ==NULL){ phead =newnode;}else{ //找尾SLTNode*ptail =phead;//思考此处循环判断条件应该是什么while(ptail->next)//若将ptail != NULL 设置为条件，当循环到尾节点时，此时不为空，会继续到后面的空节点，而此时这个空节点就不是链表的尾节点了。//故应设置为ptail->next != NULL，当循环到尾节点时，ptail->next == NULL 跳出循环，然后再将ptail->next赋值为newnode即完成尾插。{ ptail =ptail->next;//没找到尾节点就不断向后遍历}ptail->next =newnode;}}

然后我们再来解决第二个问题，形参如果想要影响实参的内容，我们传参时就要传地址而不是传数值（即使用传址调用）。测试文件中内容如下：

voidTest01(){ SLTNode*plist =NULL;SLTDataType x =1;PushBack(plist,x);SLTPrint(plist);}intmain(){ Test01();return0;}

在传参时我们是将plist作为实参，而plist是一个一级指针，其存储的是后面的空地址NULL。所以在传参时phead所接收的是plist所指向的NULL，属于传值调用。在前面函数已经讲过，传值调用时函数会在栈区开创栈帧空间来存储形参及函数内参数，也就是在栈帧空间内某一块空间被置为NULL，然后再由phead来存储。此时无论phead怎么改变，都与原来的plist毫无关系了，形参也就无法影响实参了。
所以在传参时我们不能传plist（等于传值），而是要传plist的地址（&plist）。相应的，因为传递的是一级指针的地址，所以在形参部分接收头节点的形参要使用二级指针（我们将其命名为pphead）。
最终尾插函数如下：

voidPushBack(SLTNode**pphead,SLTDataType x){ //判断传参是否为空assert(pphead);//创建要尾插的节点SLTNode*newnode =SLTBuyNode(x);//空链表与非空链表区分if(*pphead ==NULL)//等同于原来 phead == NULL。也等同于plist == NULL{ *pphead =newnode;//等同于原来的phead == newnode。也等同于plist == newnode}else{ //找尾SLTNode*ptail =*pphead;//思考此处循环判断条件应该是什么while(ptail->next)//若将ptail != NULL 设置为条件，当循环到尾节点时，此时不为空，会继续到后面的空节点，而此时这个空节点就不是链表的尾节点了。//故应设置为ptail->next != NULL，当循环到尾节点时，ptail->next == NULL 跳出循环，然后再将ptail->next赋值为newnode即完成尾插。{ ptail =ptail->next;//没找到尾节点就不断向后遍历}ptail->next =newnode;}}

在经过上面修改后，传参时一级指针的地址&plist作为实参，形参处的二级指针pphead来接收实参，形参实例化后开创栈帧来存储一级指针地址&plist，后续我们对pphead解引用操作时（*pphead），操作的就是测试文件中的一级指针plist，完成形参改变实参的操作。

3.2 头插函数

在原链表之头插入一个节点，我们在调用节点创建函数后只需要将新节点newnode->next赋值为存储链表头节点地址的一级指针plist，然后再将一级指针newnode赋值给plist就完成了头节点的转换。
具体如下：

voidPushFront(SLTNode**pphead,SLTDataType x){ //判断传参是否为空assert(pphead);//创建要尾插的节点SLTNode*newnode =SLTBuyNode(x);//进行头插newnode->next =*pphead;//将新节点next指向原头节点的地址*pphead =newnode;//将原头节点的地址更改为新节点的地址}

4 单链表尾删法与头删法

4.1 尾删函数

我们先来思考一下，能否从头遍历链表后直接free掉尾节点？
答案肯定是不能的。链表的每一节点间都通过next指针相连，若直接free掉尾节点，那么尾节点前面一个节点的next指针就会指向一块未初始化的空间，成为野指针。所以我们需要定义两个指针，一个是尾节点ptail，另一个是尾节点前面一个节点prev，free掉尾节点后，将ptail置为NULL，再将prev->next置为NULL。

voidPopBack(SLTNode**pphead){ //不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead &&*pphead);//定义需要使用的两个节点指针SLTNode*prev =*pphead;SLTNode*ptail =*pphead;//遍历单链表找尾while(ptail->next){ //寻找尾节点和其前一个节点prev =ptail;ptail =ptail->next;}free(ptail);//释放空间后将两处置为NULLptail =NULL;prev->next =NULL;}

在上面的逻辑中，情况是否全面不妨和前面一样，使用极端情况来检验。空链表的情况下会被assert断言发现，故被排除。那在只有一个节点时呢？因为ptail->next为空，故不进入循环。直接free并置为NULL，所以ptail与prev都为NULL。但是后面prev->next却又对空指针进行了非法访问，造成出错。故应在逻辑中分为链表只有一个节点和有多个节点。一个节点时直接free并置空，多个节点使在执行上面程序。
最终程序如下：

voidPopBack(SLTNode**pphead)//与前面一样，为了形参能改变实参，使用二级指针来接收头节点指针地址{ //不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead &&*pphead);//定义需要使用的两个节点指针SLTNode*prev =*pphead;SLTNode*ptail =*pphead;//链表有一个节点if((*pphead)->next ==NULL)// -> 优先级高于 *{ free(*pphead);*pphead =NULL;}//链表有多个节点else{ //遍历单链表找尾while(ptail->next){ //寻找尾节点和其前一个节点prev =ptail;ptail =ptail->next;}free(ptail);//释放空间后将两处置为NULLptail =NULL;prev->next =NULL;}}

4.2 头删函数

删掉单链表头节点只需要将头节点的next指针指向地址保留下来，释放头节点空间，然后将方才保留的地址转换为头节点地址即可。

voidPopFront(SLTNode**pphead){ //不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead &&*pphead);//保留头节点next节点指针SLTNode*next =(*pphead)->next;free(*pphead);//将保留的节点指针作为头节点指针，完成头节点转换*pphead =next;}

5 指定位置的插入与删除

5.1 在指定位置之前插入数据

在指定位置之前插入数据，首先我们思考一下，指定位置若是头节点，此时其就是头插法插入（特殊情况）。除此之外，我们若在指定位置之前直接插入新节点，那么指定位置之前原来的节点就会与pos节点断开。所以我们需要找到前一个节点地址，将前一个节点next指针指向newnode，newnode->next指向pos节点，如此完成连接。
具体见下：

voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){ //双判空assert(pphead &&*pphead);//插入值判空assert(pos);SLTNode*newnode =SLTBuyNode(x);//若 pos == *pphead ，说明是头插if(pos ==*pphead){ PushFront(pphead,x);}else//非头插，将前一个节点prev与newnode连接，newnode与pos连接{ SLTNode*prev =*pphead;//寻找pos前一个节点while(prev->next !=pos){ prev =prev->next;}//节点连接newnode->next =pos;prev->next =newnode;}}

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

在指定位置之后插入数据我们通过前文的讲述，自然会先考虑到尾插的情况，在pos 在尾节点时，pos->next == NULL，我们将pos->next直接赋值给newnode->next，然后将pos与newnode连接即可（pos->next==newnode）。在尾插情况之外，通过上面的连接操作同样可以完成插入数据，故不需要使用条件分支。
具体见下：

voidSLTInsertAfter(SLTNode**pphead,SLTNode*pos,SLTDataType x){ //双重判空assert(pphead &&*pphead);assert(pos);SLTNode*newnode =SLTBuyNode(x);//进行插入操作//将pos节点的下一个节点地址赋值给新节点 newnode 的 next 指针newnode->next =pos->next;//将pos节点的next指针指向新节点newnodepos->next =newnode;}

5.3 删除指定位置节点

在pos节点为头结点，此时删除操作符合头删法，即调用头删函数即可。除此情况之外，我们需要将pos前一个节点与后一个节点连接后再释放pos节点。
具体见下：

//删除指定位置pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos){ assert(pphead &&*pphead);assert(pos);//若 pos == *pphead，此时就是头删法删除if(pos ==*pphead){ PopFront(pos);}else//删除指定位置节点需要我们将pos之前与pos之后的节点连接起来{ SLTNode*prev =*pphead;//寻找pos前一个节点while(prev->next !=pos){ prev =prev->next;}prev->next =pos->next;free(pos);pos =NULL;}}

5.4 删除指定位置之后节点

与前面操作如出一辙，我们将pos与其后两个节点连接，最后再释放pos后一个节点置空即可。但在此处我们需要考虑pos是不是尾节点，即pos->next是否等于NULL。
具体见下：

voidSLTEraseAfter(SLTNode**pphead,SLTNode*pos){ assert(pphead &&*pphead);//判断传参 pos 是否为空以及 pos 是不是最后一个节点assert(pos &&pos->next);//先将pos之后的节点用del存储下来SLTNode*del =pos->next;//将pos与pos后第二个节点连接起来pos->next =del->next;//pos->next = pos->next->nextfree(del);del =NULL;}

6 链表数据的查找与链表的销毁

6.1 链表数据的查找

与顺序表的查找如出一辙，对整个链表遍历即可。找到就返回该节点，没找到就返回NULL。

SLTNode*SLTFind(SLTNode*phead,SLTDataType x){ SLTNode*pcur =phead;//查找节点while(pcur){ //找到节点直接返回if(pcur->data ==x){ returnpcur;}//没找到向后遍历pcur =pcur->next;}//遍历后不存在，返回空表示没找到returnNULL;}

6.2 链表的销毁

在对链表每个节点释放之前，我们需要先保留该节点的next指针的指向，从而能够销毁后续节点。

voidSLTDestroy(SLTNode**pphead){ assert(pphead &&*pphead);SLTNode*pcur =*pphead;while(pcur){ //定义 next节点以保留pcur->next的指向SLTNode*next =pcur->next;free(pcur);//将保留的next节点赋值给pcur，进而下一循环销毁后续节点pcur =next;}//全部销毁后将链表置为空*pphead =NULL;}

7 单链表全程序及演示结果

7.1 SList.h 文件

#pragmaonce#include#include#include//类型重命名typedefintSLTDataType;//定义节点结构//数据 + 指向下一节点指针typedefstructSListNode{ SLTDataType data;structSListNode*next;//指向下一节点指针//在指向下一节点指针这里，它的类型要用重命名前的结构体类型}SLTNode;//节点创建函数SLTNode*SLTBuyNode(SLTDataType x);//链表打印函数voidSLTPrint(SLTNode*phead);//尾插函数voidPushBack(SLTNode**pphead,SLTDataType x);//头插函数voidPushFront(SLTNode**pphead,SLTDataType x);//尾删函数voidPopBack(SLTNode**pphead);//头删函数voidPopFront(SLTNode**pphead);//在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x);//在指定位置之后插入数据voidSLTInsertAfter(SLTNode**pphead,SLTNode*pos,SLTDataType x);//删除pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos);//删除pos之后节点voidSLTEraseAfter(SLTNode**pphead,SLTNode*pos);//链表的查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x);//销毁链表voidSLTDestroy(SLTNode**pphead);

7.2 SList.c 文件

#include"SList.h"//节点创建函数SLTNode*SLTBuyNode(SLTDataType x)//形参部分为data要初始化的值//下一节点部分也不知道指向哪里，先置为NULL即可{ SLTNode*newnode =(SLTNode*)malloc(sizeof(SLTNode));//malloc申请单链表节点空间if(newnode ==NULL)//如果申请失败，跳出函数{ perror("malloc fail !");exit(1);}//申请成功则进行对应的初始化newnode->data =x;newnode->next =NULL;//指向下一节点部分置为空returnnewnode;//将创建的节点作为返回值返回到调用处}//链表的打印voidSLTPrint(SLTNode*phead){ SLTNode*pcur =phead;//通过一个过渡节点的嫁接转换完成对链表的遍历访问while(pcur)//等价于pcur != NULL{ printf("%d->",pcur->data);pcur =pcur->next;}//如果传过来的本来就是空节点，那么就无法进入循环，打印为空printf("NULL\n");}//链表的尾插法voidPushBack(SLTNode**pphead,SLTDataType x){ //判断传参是否为空assert(pphead);//创建要尾插的节点SLTNode*newnode =SLTBuyNode(x);//空链表与非空链表区分if(*pphead ==NULL){ *pphead =newnode;}else{ //找尾SLTNode*ptail =*pphead;//思考此处循环判断条件应该是什么while(ptail->next)//若将ptail != NULL 设置为条件，当循环到尾节点时，此时不为空，会继续到后面的空节点，而此时这个空节点就不是链表的尾节点了。//故应设置为ptail->next != NULL，当循环到尾节点时，ptail->next == NULL 跳出循环，然后再将ptail->next赋值为newnode即完成尾插。{ ptail =ptail->next;//没找到尾节点就不断向后遍历}ptail->next =newnode;}}//链表的头插法voidPushFront(SLTNode**pphead,SLTDataType x){ //判断传参是否为空assert(pphead);//创建要尾插的节点SLTNode*newnode =SLTBuyNode(x);//进行头插newnode->next =*pphead;//将新节点next指向原头节点的地址*pphead =newnode;//将原头节点的地址更改为新节点的地址}//链表的尾删法 voidPopBack(SLTNode**pphead){ //不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead &&*pphead);//定义需要使用的两个节点指针SLTNode*prev =*pphead;SLTNode*ptail =*pphead;//链表有一个节点if((*pphead)->next ==NULL){ free(*pphead);*pphead =NULL;}//链表有多个节点else{ //遍历单链表找尾while(ptail->next){ //寻找尾节点和其前一个节点prev =ptail;ptail =ptail->next;}free(ptail);//释放空间后将两处置为NULLptail =NULL;prev->next =NULL;}}//链表的头删法voidPopFront(SLTNode**pphead){ //不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead &&*pphead);//保留头节点next节点指针SLTNode*next =(*pphead)->next;free(*pphead);//将保留的节点指针作为头节点指针，完成头节点转换*pphead =next;}//在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){ //双判空assert(pphead &&*pphead);//插入值判空assert(pos);SLTNode*newnode =SLTBuyNode(x);//若 pos == *pphead ，说明是头插if(pos ==*pphead){ PushFront(pphead,x);}else{ SLTNode*prev =*pphead;while(prev->next !=pos){ prev =prev->next;}newnode->next =pos;prev->next =newnode;}}//在指定位置之后插入数据voidSLTInsertAfter(SLTNode**pphead,SLTNode*pos,SLTDataType x){ //双重判空assert(pphead &&*pphead);assert(pos);SLTNode*newnode =SLTBuyNode(x);//进行插入操作//将pos节点的下一个节点地址赋值给新节点 newnode 的 next 指针newnode->next =pos->next;//将pos节点的next指针指向新节点newnodepos->next =newnode;}//删除指定位置pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos){ assert(pphead &&*pphead);assert(pos);//若 pos == *pphead，此时就是头删法删除if(pos ==*pphead){ PopFront(pos);}else//删除指定位置节点需要我们将pos之前与pos之后的节点连接起来{ SLTNode*prev =*pphead;//寻找pos前一个节点while(prev->next !=pos){ prev =prev->next;}prev->next =pos->next;free(pos);pos =NULL;}}//删除指定位置之后的节点voidSLTEraseAfter(SLTNode**pphead,SLTNode*pos){ assert(pphead &&*pphead);//判断传参 pos 是否为空以及 pos 是不是最后一个节点assert(pos &&pos->next);//先将pos之后的节点用del存储下来SLTNode*del =pos->next;//将pos与pos后第二个节点连接起来pos->next =del->next;//pos->next = pos->next->nextfree(del);del =NULL;}//销毁链表voidSLTDestroy(SLTNode**pphead){ assert(pphead &&*pphead);SLTNode*pcur =*pphead;while(pcur){ //定义 next节点以保留pcur->next的指向SLTNode*next =pcur->next;free(pcur);//将保留的next节点赋值给pcur，进而下一循环销毁后续节点pcur =next;}//全部销毁后将链表置为空*pphead =NULL;}//链表的查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x){ SLTNode*pcur =phead;//查找节点while(pcur){ //找到节点直接返回if(pcur->data ==x){ returnpcur;}//没找到向后遍历pcur =pcur->next;}//遍历后不存在，返回空表示没找到returnNULL;}

7.3 SList_test.c 文件

#include"SList.h"voidTest01(){ SLTNode*plist =NULL;SLTDataType x =1;PushBack(&plist,x);PushBack(&plist,2);PushBack(&plist,3);PushBack(&plist,4);PushBack(&plist,5);SLTPrint(plist);SLTNode*find =SLTFind(plist,3);if(find ==NULL){ printf("没有找到！\n");}else{ printf("找到了！\n");}}intmain(){ Test01();return0;}

运行结果：

全文至此结束！！！
写作不易，不知各位老板能否给个一键三连或是一个免费的赞呢(^▽)(^▽)，这将是对我最大的肯定与支持！！！谢谢！！！(^▽)(^▽)