前言
前边关于链表的基础如果已经理解透彻，那么接下来就是对链表各功能的实现，同时也希望大家能把这部分内容熟练于心，这部分内容对有关链表部分的刷题很有帮助。废话不多讲我们步入正题。
前边已经实现了头插、尾插的操作，今天主要的内容是：头删、尾删、位置删除、位置后删除、查找、位置前插入、位置后插入。
尾删
要想进行尾删，就要先找到链表的尾。
我们知道单链表的缺点之一就是只可以单向遍历，所以要想删除最后一个节点，就要先找到倒数第二个节点，然后释放掉最后一个节点，将倒数第二个节点的next（指针域）置为NULL。
具体代码实现：
void SLPopBlack(SLNode** pphead) { assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } SLNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; }
这里为什么要传二级指针？有人可能会有这样的疑惑， 传二级指针就是为了防止链表被删空的情况，在链表的许多情节中都要考虑像链表删空等这种极端情况，要做到面面俱到。
当然我们也可以选择不使用二级指针，而是直接返回头指针的地址。但这样函数的类型就变成了结构体指针类型，而要调用这个函数还需要相同类型的结构体指针变量接收，这种情况在刷题中经常遇到，但在写链表时不推荐，这样写调用函数会比较麻烦。
头删
头删大家可以先思考一下，需不需要使用二级指针。
有这样一个链表：
想要删除第一个节点，只需要把头指针指向的位置改为指向第二个节点。把头指针修改，这是修改结构体指针，到这里想必大家已经清楚，需要使用二级指针。
接下来我们理一下删除的逻辑，直接将头指针指向第二个节点，这样就会造成第一个节点丢失没办法释放掉空间。如果先将第一个节点释放就会使第二个节点丢失，头指针无法连接剩余节点。
这要怎么解决呢？这里就需要创建一个新的变量来存储一下第二个节点的地址，然后再将第一个节点释放。
具体代码实现：
void SLPopFront(SLNode** pphead) { assert(*pphead); SLNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; }
查找
查找很简单，顺序表的查找返回的是下标，而链表返回的是节点的地址，后续的操作也是比较简单，我就不再画逻辑图。
SLNode* SLFind(SLNode* phead, Datatype x) { SLNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
位置前插入
位置前插入，如果是在第一个节点位置前插入，就是头插，其次是要想在位置前插入就必须要知道前有个节点，单链表是无法逆向遍历的，所以要想知道前一个节点就必须要传头指针。然后将前一个节点的next置为新节点的地址，新节点的next置为pos位置节点的地址。
void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x) { assert(pos); if (pos == *pphead) { SLPushFront(pphead, x); } else { SLNode* prev = *pphead; SLNode* newnode = NewNode(x); while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } }
位置后插入
位置后插入，可以不需要头指针。操作也非常简单，把pos位置的下一个节点赋给新节点的next，把新节点的地址赋给pos位置节点的next。这里有人可能会有疑惑，不考虑极端情况吗？位置后插入是无法进行头插的，如果链表为空，传进来pos就为空，就会直接保错，至于尾插，这段代码也是可以解决的。
void SLAfterInsert(SLNode* pos, Datatype x) { assert(pos); SLNode* newnode = NewNode(x); newnode->next = pos->next; pos->next = newnode; }
位置删除
位置删除，需要把pos位置前一个节点的next置为pos位置下一个节点的地址，同时还需要将删除的节点释放空间。考虑极端情况，如果删除位置是第一个节点，这种方法就失效了，因为没有第一个节点的前一个节点，这时也就是头删，我们可以调用前边已经实现的函数接口。
void SLErase(SLNode** pphead, SLNode* pos) { assert(pphead); assert(pos); if (pos == *pphead) { SLPopFront(pphead); } else { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
位置后删除
位置后删除，如果位置为最后一个节点，就不需要删除，且位置后删除无法进行头删，然后是正常情况，把pos位置节点的next置为pos位置后第二个节点的地址，就完成了。那是否可以这样写呢？
pos->next = pos->next->next
答案是不可以，这样会造成pos后一个节点丢失，无法释放。所以这里我们需要分成两步来写：
void SLEraseAfter(SLNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { SLNode* posnext = pos->next;//不可以写成一步，否则pos后一个节点就会丢失，无法释放 pos->next = posnext->next; free(posnext); posnext = NULL; } }
链表销毁
执行完所有操作后，就需要将链表销毁了
void SLDestory(SLNode** pphead) { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next =cur->next; free(cur); cur = next; } *pphead = NULL; }
完整代码：
SList.c
#include"SList.h" void SLprint(SLNode* phead) { SLNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } SLNode* NewNode(Datatype x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } void SLPushBlack(SLNode** pphead, Datatype x) { assert(pphead); SLNode* newnode = NewNode(x); SLNode* tail = *pphead; if (*pphead == NULL) { *pphead = newnode; } else { while (tail->next) { tail = tail->next; } tail->next = newnode; } } void SLPushFront(SLNode** pphead, Datatype x) { assert(pphead); SLNode* newnode = NewNode(x); newnode->next = *pphead; *pphead = newnode; } void SLPopBlack(SLNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } SLNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } void SLPopFront(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; } SLNode* SLFind(SLNode* phead, Datatype x) { SLNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x) { assert(pphead); assert(pos); if (pos == *pphead) { SLPushFront(pphead, x); } else { SLNode* prev = *pphead; SLNode* newnode = NewNode(x); while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } } void SLAfterInsert(SLNode* pos, Datatype x) { assert(pos); SLNode* newnode = NewNode(x); newnode->next = pos->next; pos->next = newnode; } void SLErase(SLNode** pphead, SLNode* pos) { assert(pphead); assert(pos); if (pos == *pphead) { SLPopFront(pphead); } else { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } void SLEraseAfter(SLNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { SLNode* posnext = pos->next; pos->next = posnext->next; free(posnext); posnext = NULL; } } void SLDestory(SLNode** pphead) { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next =cur->next; free(cur); cur = next; } *pphead = NULL; }
SList.h
#include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int Datatype; typedef struct SLNode { Datatype data; struct SLNode* next; }SLNode; //打印链表 void SLprint(SLNode* phead); //创建新节点 SLNode* NewNode(Datatype x); //尾插 void SLPushBlack(SLNode** phead, Datatype x); //头插 void SLPushFront(SLNode** pphead, Datatype x); //尾删 void SLPopBlack(SLNode** pphead); //头删 void SLPopFront(SLNode** pphead); //查找 SLNode* SLFind(SLNode* phead, Datatype x); //pos位置前插入 void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x); //pos位置后插入 void SLAfterInsert(SLNode* pos, Datatype x); //pos位置后删除 void SLEraseAfter(SLNode* pos); //pos位置删除 void SLErase(SLNode** pphead, SLNode* pos); void SLDestory(SLNode** pphead);
test.c
这里基本都是测试接口，没有什么太大的参考价值，代码如下，便于大家调试。
#include"SLNode.h" void test1() { SLNode* plist = NULL; int n = 0; printf("请输入链表的长度\n"); scanf("%d", &n); printf("请输入数据\n"); for (int i = 0; i < n; i++) { int val = 0; scanf("%d", &val); SLNode *newnode= NewNode(val); newnode->next = plist; plist = newnode; } SLNode* pos= SLFind(plist, 2); if (pos) { pos->data *= 10; } SLFrontInsert(&plist, pos, 10); SLprint(plist); SLPushBlack(&plist,100); SLprint(plist); SLPushFront(&plist, 200); SLprint(plist); SLPopBlack(&plist); SLprint(plist); SLPopFront(&plist); SLprint(plist); } void test2() { SLNode* plist = NULL; SLPushBlack(&plist, 1); SLPushBlack(&plist, 2); SLPushBlack(&plist, 3); SLPushBlack(&plist, 4); SLPushBlack(&plist, 5); SLprint(plist); SLNode* pos = SLFind(plist, 5); SLAfterInsert(pos, 20); SLprint(plist); SLFrontInsert(&plist, pos, 10); SLprint(plist); } void test3() { SLNode* plist = NULL; SLPushBlack(&plist, 1); SLPushBlack(&plist, 2); SLPushBlack(&plist, 3); SLPushBlack(&plist, 4); SLPushBlack(&plist, 5); SLprint(plist); SLNode* pos = SLFind(plist, 1); //SLErase(&plist, pos); SLEraseAfter(pos); SLprint(plist); SLDestory(&plist); } int main() { test2(); return 0; }
总结
好的，内容到这里就要结束了，这部分内容或许看来很繁琐，但在刷链表相关的题时就会惊奇的发现，题解都是这些操作的变形。熟练这部分内容，可以让你在刷链表相关的题时会感觉非常的爽，刷题也会更加顺利。最后，感谢阅读！
