之前我们学习了动态顺序表，今天我们来讲一讲单链表是如何进行增删改查的
一、单链表
1.1、单链表概念
概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
1.2、链表与顺序表的区别：
链表不像顺序一样，空间给少了不够，给多了浪费，链表是你需要多少空间，就申请多少空间。
链表中一个结点就是一个数据，结点中必须包含两个数据，一个是我们需要存放的数据，另外一个就是下一个数据的地址。
每存放一个数据，我们就需要申请一个结点，直到最后一个结点指向的地址为NULL
淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。
在链表⾥，每节“⻋厢”是什么样的呢？
1.3、链表的打印
为什么提前讲链表是如何打印的，而不是先讲插入删除，初始化，这是因为比较好理解，这个理解的，接下来在看增删查改理解就会快了。
当pcur为头结点时，需要打印第一个结点的数据，第一个结点的数据为pcur这个结构体中的data数据，所有我们需要获取data数据进行打印。当需要打印第二个结点里data数据时候，pcur需要往前走一个结点，走到的结点是pcur结构体中存放的下一个结点的地址进行解引用，然将解引用得到的数据赋值给pcur，此时pcur就往前前进了一位。直到pcur等于NULL才停止循环。
二、增删改查
在这一部分，只写node.c中增删改查实现的函数代码，总代码可在最后进行查看。
2.1、结点的创建（结构体）
node.htypedef int SLTDataType; //将int类型定义为SLTDataType，方便修改数据类型typedef struct SListNode {SLTDataType data; struct SListNode* next; //指向的下一个结点
}SLTNode;
struct SListNode* next;这段代码是创建一个为类型大小为struct SListNode指针的next，next指向下一个结点，为什么不是这样写struct SListNode next; 如果这样的话，每个结点都包含一个完整的 SListNode ,那么造成了巨大的空间浪费，在进行移动的时候，占用非常大的计算。
这样写struct SListNode* next; 那么在进行两个结点连接时，next可以存储另外一个结点的地址，可以快速找到下一个数据
2.2、创建头结点
test.cint main()
{SLTNode* plist = NULL; //创建头结点return 0;
}为什么需要使用SLTNode* plist = NULL; 那是因为plist是一个指向SLTNode的一个指针，我们可以用这个来指向链表的头结点，并且在链表的动态中进行改变他的值。
SLTNode plist = NULL;这样写的意思是plist的类型是SLTNode并且等于NULL，这是一个极其错误的写法。
所以如果我们想要动态的使用结点，就需要创建一个头结点指向SLTNode，这样就可以使用结构体中的数据。
那为什么不这样写 SLTNode plist；然后对结构体进行初始化。那是因为，我们所创建的不是一个顺序表，我们需要记录下一个空间存入的数据与该空间的下一个结点。
2.3、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//pphead --> &plist// *pphead --> plist//申请新节点SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾结点SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}//pcur newnodepcur->next = newnode;}
}void SLTPushBack(SLTNode** pphead, SLTDataType x)注意这里使用了二级指针。
为什么要使用二级指针？
由于我们需要修改头指针的内容，而传递指针本质上是值传递，所以我们需要通过二级指针来直接操作头指针的地址，才能真正修改头指针的值。
在顺序表中，由于你是在固定大小的数组上操作，数组的大小和起始地址是固定的，不需要动态分配和改变，所以不需要二级指针。
在链表中，如果直接将创建的头结点的值传入函数中，那么就相当于传值调用，在程序运行完以后，栈帧也会消失，所以需要取地址进行函数调用，这样头结点内容就被修改了。
2.4、申请新结点
//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;
}在链表中使用malloc来扩容，而非增容（realloc），当创建好一个新结点时，把数据（x）存放到新结点中的data里面，新结点指向的下一个指针next先置为空，在接下来增删改查时候再做修改。
2.5、尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead); //判断pphead是否为NULL//申请新节点SLTNode* newnode = SLTBuyNode(x); //创建一个新结点if (*pphead == NULL){*pphead = newnode; //如果*pphead是已经初始化为NULL，那么直接将新结点等于头结点}else{//找尾结点SLTNode* pcur = *pphead; //创建一个新指针等于pphead的while (pcur->next) //pcur->next不等于NULL就一直运行{pcur = pcur->next; //一直将pcur往后遍历，直到pcur->next等于NULL}pcur->next = newnode; //将原链表pcur->next指向NULL的结点指针指向新的结点}
}为什么我们不适用*pphead来遍历链表，因为我们在打印链表的时候，需要从头结点开始遍历，如果使用*pphead来遍历的话，此时*pphead就走到了链表的末尾，在打印链表的时候就无法打印，所以就需要创建一个指针等于*pphead，借助新创建的指针来进行链表的修改，当新指针走到了链表的末尾，*pphead还是在链表的头结点。
2.6、头插
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x); //创建新结点newnode->next = *pphead; //将新创建的头结点中指向下一个结点的指针直接指向*pphead*pphead = newnode; //将*pphead等于newnode，此时头结点还是*pphead
} 2.7、尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{//链表为空：不可以删除assert(pphead && *pphead);//处理只有一个结点的情况:要删除的就是头结点 if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找 prev ptailSLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}
............................................
第四个图中，newtail->next = NULL，此时循环停止，将prev->next置为NULL，此时prev就是最后一个结点，接着将不需要的结点newtail中的空间给释放掉.
2.8、头删
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;//记录头结点指向的下一个结点free(*pphead); //释放头结点*pphead = next; //将*pphead等于刚刚记录下来的结点，此时就完成了头结点的删除操作
}
2.9、查找链表中的数据
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}当链表中存放的数据等于x时，返回pcur，否则就返回NULL
2.10、在指定位置之前插⼊数据
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos); //查找的数据不能为空，需要是一个有效的数if (pos == *pphead){SLTPushFront(pphead, x); 如果pos等于头结点，那么直接进行头插}else{SLTNode* newnode = SLTBuyNode(x);//找prev :pos的前一个结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}
例如需要查找的数是pos=3，prev->next中的地址解引用得到的结果就是3，所以prev停止pos结点之前的一个结点。
将newnode->next指针指向pos，接着将prev->next指向newnode。这样就完成了链表的插入。
2.11、在指定位置之后插⼊数据
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}例如pos=2，那么图就是这这样的
2.12、删除pos结点
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//头删if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
2.13、删除pos之后的结点
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}
2.14、销毁链表
//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next; //遍历每一个结点，将每一个结点空间进行释放free(pcur);pcur = next; //将释放后的结点，等于下一个结点，直到pcur=NULL}*pphead = NULL; //释放完全部结点以后，将*pphead也置为NULL
}三、全部源代码
node.h#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义链表（结点）的结构
typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//插入
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);//删除
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** pphead);test.c#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//1->2->3->4->NULL//SLTPushBack(NULL, 3);//SLTPushFront(&plist, 1);//SLTPushFront(&plist, 2);//SLTPushFront(&plist, 3);//SLTPushFront(&plist, 4);//SLTPrint(plist); //4->3->2->1->NULL//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);////SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTNode* find = SLTFind(plist, 4);//if (find == NULL)//{// printf("未找到！\n");//}//else//{// printf("找到了！\n");//}//SLTInsert(&plist, find, 11);//4->3->2->11->1->NULL//SLTInsertAfter(find, 11);//SLTPrint(plist);1->11->2->3->4->NULL//SLTErase(&plist, find);// 1->2->3->NULL//SLTEraseAfter(find);//SLTPrint(plist);SListDestroy(&plist);SLTPrint(plist);
}int main()
{SListTest01();return 0;
}node.c#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;
}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//pphead --> &plist// *pphead --> plist//申请新节点SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾结点SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}//pcur newnodepcur->next = newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{//链表为空：不可以删除assert(pphead && *pphead);//处理只有一个结点的情况:要删除的就是头结点 if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找 prev ptailSLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;//*pphead --> nextfree(*pphead);*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);//找prev :pos的前一个结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev newnode --> posnewnode->next = pos;prev->next = newnode;}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode --> pos->nextnewnode->next = pos->next;pos->next = newnode;
}
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//头删if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);//pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}
//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
