前言
链表和顺序表都是线性表的一种，但是顺序表在物理结构和逻辑结构上都是连续的，但链表在逻辑结构上是连续的，而在物理结构上不一定连续；来看以下图片来认识链表与顺序表的差别
这里以动态顺序表为例，和链表中的单链表对比一下
动态顺序表 
单链表
这里就可以很清晰的看到顺序表的底层其实就是一个数组，数据的是连续存储的（顺序表物理结构连续）；而链表它每一个数据都不是连续的（链表物理结构上不一定连续）。
链表节点
通过观察上图，我们会发现链表每一个节点都存放在数据和下一个节点的地址。
那么来想一下，为了链表每一个节点都统一起来，都存储有效数据和下一个节点的地址，我们就需要创建应该结构体，来存储有效数据和下一个节点的指针；
注：这里只是单链表
typedef int SLType; typedef struct SLTNode { SLType data; struct SLTNode* next; }SLT;
创建好链表节点，接下来就来实习单链表存储数据的这些功能。
单链表实现
先来看一下单链表都实现都哪些功能
//输出链表 void SLTPrint(SLT* phead); //创建节点 SLT* SLTCreat(SLType x); //单链表头插 void SLTPushFront(SLT** pphead, SLType x); //单链表尾插 void SLTPushBack(SLT** pphead, SLType x); //单链表头删 void SLTPopFront(SLT** pphead); //单链表尾删 void SLTPopBack(SLT** pphead); //查找数据 SLT* SLTFind(SLT* phead, SLType x); //指定位置之前插入 void SLTInsert(SLT** pphead, SLT* pos, SLType x); //指定位置之后插入 void SLTInsertAfter(SLT* pos, SLType x); //删除指定节点 void SLTErase(SLT** pphead, SLT* pos); //删除指定位置后一个节点 void SLTEraseAfter(SLT* pos);
创建节点
这里创建节点，还是使用动态内存来创建，创建完成后，将数据存储进去，并把新节点的下一个节点置为NULL
代码如下：
//创建节点 SLT* SLTCreat(SLType x) { SLT* newnode = (SLT*)malloc(sizeof(SLT)); assert(newnode); newnode->data = x; newnode->next = NULL; return newnode; }
测试一下代码是否正确
可以看到代码没有问题。
输出链表
由于这里实现单链表，存储的是整型数据，就以整型的方式输出，若存储其他类型的数据，就以存储类型的方式输出。
输出链表，首先就要遍历链表，因为链表最后一个节点里存储的下一个节点的地址为空（即最后一个节点 ->next 为空）所以，遍历链表结束的条件就是ptail ==NULL，没输出一个就让ptail指向下一个节点，直到为空，遍历结束。
来写代码实现：
//输出链表 void SLTPrint(SLT* phead) { SLT* ptail = phead; while (ptail!= NULL)//也可以直接写成 ptail { printf("%d -> ", ptail->data); ptail = ptail->next; } printf("NULL\n"); }
这里先创建两个节点并存储数据输出看一下结果
int main() { SLT* plist = SLTCreat(1); plist->next = SLTCreat(2); SLTPrint(plist); return 0; }
这里也成功输出插入的两个数据。（最后一个节点的next指向空）
单链表头插
在链表头部插入数据，不用像顺序表那样去移动所以的有效数据，链表只需要改变一个指针的指向即可
假设现在链表中已经存在两个数据，再进行头插，这时就只需要改变plist的指向即可，当然新节点的next指针也要指向下一个节点(plist指向的节点)。
代码如下：
//单链表头插 void SLTPushFront(SLT** pphead, SLType x) { assert(pphead); SLT* newnode = SLTCreat(x); newnode->next = *pphead; *pphead = newnode; }
还有一种情况，如果现在链表中没有数据，再进行头插，这里代码也能实现链表没有数据时的头插 
单链表尾插
链表的尾插，因为指针传的是指向头节点的指针的地址，所以，我们需要先遍历链表，找到链表的尾部，再修改尾节点的next指针指向。 
假设现在链表中已经存在两个数据，再进行尾插，此时我们只需要找到链表的尾部，修改尾节点next指针指向即可，代码如下
//单链表尾插 void SLTPushBack(SLT** pphead, SLType x) { assert(pphead); SLT* newnode = SLTCreat(x); SLT* ptail = *pphead; //遍历链表 while (ptail->next) { ptail = ptail->next; } ptail->next = newnode; }
考虑了这种情况，再来看以下链表为空的情况，如果链表为空，这里ptail->next就对空指针进行解引用操作了；所以，我们需要判断链表是否为空？如果为空，插入的新节点就是头节点，直接让plist（即*pphead)指向新节点即可；如果不为空就正常进行尾插。
最终代码如下：
//单链表尾插 void SLTPushBack(SLT** pphead, SLType x) { assert(pphead); SLT* newnode = SLTCreat(x); if (*pphead == NULL) //判断链表是否为空 { *pphead = newnode; } else { SLT* ptail = *pphead; //遍历链表 while (ptail->next) { ptail = ptail->next; } ptail->next = newnode; } }
这里代码可以正常进行尾插。
单链表头删
链表头删，首先我们要判断链表是否为空，如果为空（空链表没有数据该如何删除呢 
）
链表头删，我们需要修改plist（*pphead）指向链表的下一个节点即头节点的next指针。
此外：因为我们的节点都是动态申请的内存，所以在删除时，需要把它释放掉。
思路很简单，写一下代码：
//单链表头删 void SLTPopFront(SLT** pphead) { assert(pphead && *pphead); SLT* del = (*pphead); *pphead = (*pphead)->next; free(del); del = NULL; }
再来看一个如果链表为空，又是啥结果呢？ 
现在链表已经为空，在执行一次头删代码 
这里assert断言报错。
单链表尾删
首先尾删与头删一样，链表不能为空。
尾删与尾插也有共同之处，就是遍历链表，找到链表的尾节点。找到尾节点，删除尾节点；然后修改尾节点上一个节点的next指针为NULL；所以在遍历链表时就要多记录一个节点。
//单链表尾删 void SLTPopBack(SLT** pphead) { assert(pphead && *pphead); SLT* ptail = *pphead; SLT* pcur = *pphead; //遍历链表 while (ptail->next) { pcur = ptail; ptail = ptail->next; } pcur->next = NULL; free(ptail); ptail = NULL; }
在测试的时候我们会发现一个问题，如果链表只有一个节点，删除之后我们的plist指针并没有置为空，而我们的空间已经释放掉了，这是很危险的 
；所以这里我们先判断一下链表是否只有一个节点，如果是，我们释放完空间以后，将(*pphead)置为空，以免出现野指针的情况。
完善后代码：
//单链表尾删 void SLTPopBack(SLT** pphead) { assert(pphead && *pphead); if ((*pphead)->next== NULL) { free(*pphead); *pphead = NULL; } else { SLT* ptail = *pphead; SLT* pcur = *pphead; //遍历链表 while (ptail->next) { pcur = ptail; ptail = ptail->next; } free(ptail); ptail = NULL; pcur->next = NULL; } }
测试没有问题，代码能够完成尾删这个功能。
查找数据
查找数据，遍历链表查找数据，如果找到就返回数据所在节点的地址，如果没有找到就返回NULL;
//查找数据 SLT* SLTFind(SLT* phead, SLType x) { SLT* ptail = phead; while (ptail) { if (ptail->data == x) { return ptail; } ptail = ptail->next; } return NULL; }
这里测试以下：
数据存在时 
数据不存在时 
指定节点之前插入
在链表指定节点之前插入数据，我们还需要知道指定节点的前一个节点，所以仍然需要遍历链表，寻找指定节点pos前一个节点。
//指定位置之前插入 void SLTInsert(SLT** pphead, SLT* pos, SLType x) { assert(pphead && *pphead); SLT* ptail = *pphead; if (ptail == pos)//头插 { SLTPushFront(pphead, x); } else { SLT* newnode = SLTCreat(x); while (ptail->next != pos)//找到pos位置 { ptail = ptail->next; } newnode->next = pos; ptail->next = newnode; } }
当然，这里如果故意传NULL给pos，（这就没啥意义了）这里也可以写以下assert断言pos。
指定节点之后插入
在指定节点之后插入数据，就不需要再进行遍历链表，这里直接插入即可。
//指定位置之后插入 void SLTInsertAfter(SLT* pos, SLType x) { assert(pos); SLT* newnode = SLTCreat(x); newnode->next = pos->next; pos->next = newnode; }
删除指定节点
删除链表中的指定节点，我们需要这个节点的上一个节点，所以又需要遍历链表，找到pos上一个节点，修改pos->next指针指向。
代码如下：
//删除指定节点 void SLTErase(SLT** pphead, SLT* pos) { //找到pos上一个节点 SLT* ptail = *pphead; while (ptail->next != pos) { ptail = ptail->next; } SLT* p = pos->next; free(pos); pos = NULL; ptail->next = p; }
删除指定节点后一个节点
删除链表指定节点后一个节点，因为pos就是删除节点的上一个节点，所以不需要遍历链表，直接删除即可。
//删除指定位置后一个节点 void SLTEraseAfter(SLT* pos) { assert(pos->next); SLT* del = pos->next; pos->next = pos->next->next; free(del); del = NULL; }
这里如果传过来的就是链表的尾节点，那 
删除后一个节点，所以断言pos->next；
代码总览
#include"SList.h" //创建节点 SLT* SLTCreat(SLType x) { SLT* newnode = (SLT*)malloc(sizeof(SLT)); assert(newnode); newnode->data = x; newnode->next = NULL; return newnode; } //输出链表 void SLTPrint(SLT* phead) { SLT* ptail = phead; while (ptail != NULL)//也可以直接写成 ptail { printf("%d -> ", ptail->data); ptail = ptail->next; } printf("NULL\n"); } //单链表头插 void SLTPushFront(SLT** pphead, SLType x) { assert(pphead); SLT* newnode = SLTCreat(x); newnode->next = *pphead; *pphead = newnode; } //单链表尾插 void SLTPushBack(SLT** pphead, SLType x) { assert(pphead); SLT* newnode = SLTCreat(x); if (*pphead == NULL) //判断链表是否为空 { *pphead = newnode; } else { SLT* ptail = *pphead; //遍历链表 while (ptail->next) { ptail = ptail->next; } ptail->next = newnode; } } //单链表头删 void SLTPopFront(SLT** pphead) { assert(pphead && *pphead); SLT* del = (*pphead); *pphead = (*pphead)->next; free(del); del = NULL; } //单链表尾删 void SLTPopBack(SLT** pphead) { assert(pphead && *pphead); if ((*pphead)->next== NULL) { free(*pphead); *pphead = NULL; } else { SLT* ptail = *pphead; SLT* pcur = *pphead; //遍历链表 while (ptail->next) { pcur = ptail; ptail = ptail->next; } free(ptail); ptail = NULL; pcur->next = NULL; } } //查找数据 SLT* SLTFind(SLT* phead, SLType x) { SLT* ptail = phead; while (ptail) { if (ptail->data == x) { return ptail; } ptail = ptail->next; } return NULL; } //指定位置之前插入 void SLTInsert(SLT** pphead, SLT* pos, SLType x) { assert(pphead && *pphead); SLT* ptail = *pphead; if (ptail == pos)//头插 { SLTPushFront(pphead, x); } else { SLT* newnode = SLTCreat(x); while (ptail->next != pos)//找到pos位置 { ptail = ptail->next; } newnode->next = pos; ptail->next = newnode; } } //指定位置之后插入 void SLTInsertAfter(SLT* pos, SLType x) { assert(pos); SLT* newnode = SLTCreat(x); newnode->next = pos->next; pos->next = newnode; } //删除指定节点 void SLTErase(SLT** pphead, SLT* pos) { //找到pos上一个节点 SLT* ptail = *pphead; while (ptail->next != pos) { ptail = ptail->next; } SLT* p = pos->next; free(pos); pos = NULL; ptail->next = p; } //删除指定位置后一个节点 void SLTEraseAfter(SLT* pos) { assert(pos->next); SLT* del = pos->next; pos->next = pos->next->next; free(del); del = NULL; }
感谢各位大佬支持并指出问题，
