单链表的头删
头删不需要遍历单链表，只需释放头节点即可。
当然，删除前需要找到头节点的下一个节点，这是因为头节点删除后，单链表的头需要更新，而新的头也就是删除的那个头节点的下一个节点。
要更新新的头也就是需要改变头指针，因此这里也是需要用到二级指针的。
既然是删除，当然也要判断单链表是否为空。
下面是相关接口函数的代码：
// 单链表头删 void SListPopFront(SListNode** pplist) { // 判断pplist是否为空指针，判断单链表是否为空 assert(pplist && *pplist); // 先存放下一个节点 SListNode* cur = (*pplist)->next; // 释放头节点 free(*pplist); // 更新头节点 *pplist = cur; }
单链表的查找
查找比较简单，就是遍历单链表看看val与那个节点的数据相等，相等则返回该节点的地址，如果遍历完单链表都没有找到，那么返回NULL。
查找函数不需要判断单链表是否为空，因为如果单链表为空的话，循环就不进去，直接返回空，就说明找不到，当然啦，空的单链表当然找不到啦。
下面是相关接口函数的代码：
// 单链表查找 SListNode* SListFind(SListNode* plist, SLTDataType x) { SListNode* cur = plist; // 当cur为空时结束循环 while (cur) { if (cur->data == x) return cur; cur = cur->next; } // 如果没找到就返回NULL return NULL; }
单链表节点数据的修改
该函数是将你想修改的节点的数据改为你想要的值。
一般的，修改函数与查找函数是一起用的，因为有了前面的查找函数，我们可以先查找在修改。因此该函数的第一个参数为指向单链表节点的指针。
当然，这里需要判断一下节点指针是否合法，如果该指针为NULL，说明在查找的时候没有找到对应数据的节点，此时直接暴力结束。
下面是相关接口函数的代码：
// 单链表修改节点的data void SListModify(SListNode* pos, SLTDataType NewData) { // 一般以find的返回值作为pos参数 // 如果pos为空，说明没有这个节点，这里断言一下 assert(pos); pos->data = NewData; }
单链表在pos位置之后插入节点
- 既然是
pos位置之后，因此我们需要先利用查找函数来确定你想要的pos，然后再进行插入。 - 插入需要先获取一个节点，调用BuySListNode函数。
- 插入操作前，我们需要一个节点指针指向
pos位置的下一个节点，这样是为了连接，然后插入操作如下图：
- 当然，这里也需要判断一下
pos的合法性。
下面是相关接口函数的代码：
// 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDataType x) { // 判断pos就间接的判断了单链表是否为空的情况 assert(pos); SListNode* newnode = BuySListNode(x); // 存放pos节点的下一个节点 SListNode* tmp = pos->next; pos->next = newnode; newnode->next = tmp; }
单链表在pos位置之前插入节点
- 既然是在
pos位置之前插入，但单链表具有单向性，因此这里需要遍历单链表找到pos位置的前一个节点，然后再进行插入。 - 可以取巧的是，如果
pos刚好指向头节点，此时直接调用头插。 - 由于这里调用了头插，而头插使用的是二级指针，因此该函数也是需要二级指针来操作的。
下面是相关接口函数的代码：
// 单链表在pos位置之前插入x void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x) { // 如果pos不合法，就说明要么再查找时没有该节点，要么单链表为空，因此这里间接判断了单链表是否为空的情况 assert(pplist && pos); // 如果pos为第一个节点，直接调用前面的头插 if (*pplist == pos) SListPushFront(pplist, x); else { SListNode* newnode = BuySListNode(x); SListNode* cur = *pplist; // 找pos位置的前面一个节点 while (cur->next != pos) cur = cur->next; // 连接 cur->next = newnode; newnode->next = pos; } }
单链表删除pos位置之后的节点
由于是直接对pos节点后面的节点进行操作，因此不需要传递头节点。
对于pos，如果pos合法，就说明单链表一定不为空。
因此这里只需要判断pos的合法性，当然，如果pos恰好指向最后一个节点，此时就删不了了，所以这种情况也需要assert断言。
对于删除操作，首先需要找到pos的下一个节点的下一个节点，这是为了连接，然后再对pos的下一个节点进行删除。
下面是相关接口函数的代码：
// 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos) { // 直接判断pos assert(pos && pos->next); // 存放pos下一个节点的下一个节点 SListNode* tmp = pos->next->next; // 释放pos的下一个节点 free(pos->next); // 连接 pos->next = tmp; }
单链表删除pos位置之前的节点
在之前，同样的，需要遍历单链表，找到pos节点的前一个节点和pos节点的前一个节点的前一个节点。
如果pos刚好指向头节点，这是删不了的，会出问题，因此需要assert断言；如果pos刚好指向头节点的下一个节点，这里直接调用头删完成删除。
下面是相关接口函数的代码：
// 单链表删除pos位置之前的值 // 使用二级指针是因为调用头删函数需要传递二级指针，当然二级指针便于操作 void SListEraseBefore(SListNode** pplist, SListNode* pos) { // pplist不能为NULL // pos要合法，间接体现了单链表是否为空 // pos不能指向头节点，因为头节点的前面没有节点 assert(pplist && pos && pos != *pplist); // 如果pos指向头节点的下一个节点，直接调用头删函数完成删除 if ((*pplist)->next == pos) SListPopFront(pplist); else // 正常情况 { // cur最终要指向pos的前一个结点，tmp最终要指向pos的前一个节点的前一个节点 SListNode* cur = *pplist, * tmp = NULL; // 循环找位 while (cur->next != pos) { tmp = cur; cur = cur->next; } // 删除前一个结点 free(cur); // 连接 tmp->next = pos; } }
单链表删除pos位置的节点
如果pos刚好指向头节点，直接调用头删；如果pos刚好指向尾节点（用pos->next == NULL ? 判断），直接调用尾删。
因为头删尾删都需要传递二级指针，因此该函数也运用二级指针，而且二级指针也便于操作。
一般情况，我们只需要遍历单链表找到pos节点的前一个结点和存放pos的后一个节点，然后将pos节点删除，连接pos的前一个节点和pos的后一个节点即可。
下面是相关接口函数的代码：
// 单链表删除pos位置的值 void SListErasePos(SListNode** pplist, SListNode* pos) { assert(pplist && pos); if (*pplist == pos) SListPopFront(pplist); // 如果pos是指向头节点，直接复用头删 else if (!pos->next) SListPopBack(pplist); // 如果pos是指向尾节点，直接复用尾删 else // 一般情况 { // cur为pos的前一个结点 SListNode* cur = *pplist; while (cur->next != pos) cur = cur->next; // tmp为pos的后一个结点 SListNode* tmp = pos->next; // 删除pos结点 free(pos); // 将pos的前一个节点与pos的后一个节点连接 cur->next = tmp; } }
整体代码
SList.h
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SListNode; // 动态申请一个节点 SListNode* BuySListNode(SLTDataType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDataType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDataType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDataType x); // 单链表修改节点的data void SListModify(SListNode* pos, SLTDataType NewData); // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDataType x); // 单链表在pos位置之前插入x void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos); // 单链表删除pos位置的值 void SListErasePos(SListNode** pplist, SListNode* pos); // 单链表删除pos位置之前的值 void SListEraseBefore(SListNode** pplist, SListNode* pos); // 单链表的销毁 void SListDestroy(SListNode** pplist);
SList.c
#include "SList.h" // 动态申请一个节点 SListNode* BuySListNode(SLTDataType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); assert(newnode); newnode->data = x; newnode->next = NULL; return newnode; } // 单链表打印 void SListPrint(SListNode* plist) { SListNode* cur = plist; while (cur) { printf("%d ", cur->data); cur = cur->next; } printf("NULL\n"); } // 单链表的销毁 void SListDestroy(SListNode** pplist) { assert(pplist); SListNode* cur = *pplist; while (cur) { SListNode* tmp = cur; cur = cur->next; free(tmp); } *pplist = NULL; } // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDataType x) { assert(pplist); SListNode* newnode = BuySListNode(x); if (*pplist == NULL) *pplist = newnode; else { SListNode* cur = *pplist; while (cur->next) cur = cur->next; cur->next = newnode; } } // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDataType x) { assert(pplist); SListNode* newnode = BuySListNode(x); if (*pplist == NULL) *pplist = newnode; else { newnode->next = *pplist; *pplist = newnode; } } // 单链表的尾删 void SListPopBack(SListNode** pplist) { assert(pplist && *pplist); if (!(*pplist)->next) free(*pplist), * pplist = NULL; else { SListNode* cur = *pplist, * tmp = NULL; while (cur->next) { tmp = cur; cur = cur->next; } free(cur); tmp->next = NULL; } } // 单链表头删 void SListPopFront(SListNode** pplist) { assert(pplist && *pplist); SListNode* cur = (*pplist)->next; free(*pplist); *pplist = cur; } // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDataType x) { // 这里可以不断言，但建议断言，因为使用find返回NULL可能是单链表本身就是空的， // 但一般是找不到才返回NULL assert(plist); SListNode* cur = plist; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } // 单链表修改节点的data void SListModify(SListNode* pos, SLTDataType NewData) { // 一般以find的返回值作为pos参数 // 如果pos为空，说明没有这个节点，这里断言一下 assert(pos); pos->data = NewData; } // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos); SListNode* newnode = BuySListNode(x); SListNode* tmp = pos->next; pos->next = newnode; newnode->next = tmp; } // 单链表在pos位置之前插入x void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x) { assert(pplist && pos); if (*pplist == pos) SListPushFront(pplist, x); else { SListNode* newnode = BuySListNode(x); SListNode* cur = *pplist; while (cur->next != pos) cur = cur->next; cur->next = newnode; newnode->next = pos; } } // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos) { assert(pos && pos->next); SListNode* tmp = pos->next->next; free(pos->next); pos->next = tmp; } // 单链表删除pos位置的值 void SListErasePos(SListNode** pplist, SListNode* pos) { assert(pplist && pos); if (*pplist == pos) SListPopFront(pplist); // 如果pos是指向头节点，直接复用头删 else if (!pos->next) SListPopBack(pplist); // 如果pos是指向尾节点，直接复用尾删 else { SListNode* cur = *pplist; while (cur->next != pos) cur = cur->next; SListNode* tmp = pos->next; free(pos); cur->next = tmp; } } // 单链表删除pos位置之前的值 void SListEraseBefore(SListNode** pplist, SListNode* pos) { assert(pplist && pos && pos != *pplist); if ((*pplist)->next == pos) SListPopFront(pplist); else { SListNode* cur = *pplist, * tmp = NULL; while (cur->next != pos) { tmp = cur; cur = cur->next; } free(cur); tmp->next = pos; } }
test.c
这里有多个测试用例，可以自己捣鼓。
#include "SList.h" void TestList1() { SListNode* plist = NULL; SListPrint(plist); SListPushBack(&plist, 1); SListPrint(plist); SListPushBack(&plist, 2); SListPrint(plist); SListPushBack(&plist, 3); SListPrint(plist); SListPushBack(&plist, 4); SListPrint(plist); SListPushBack(&plist, 5); SListPrint(plist); SListPushBack(&plist, 6); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListDestroy(&plist); } void TestList2() { SListNode* plist = NULL; SListPrint(plist); SListPushFront(&plist, 1); SListPrint(plist); SListPushFront(&plist, 2); SListPrint(plist); SListPushFront(&plist, 3); SListPrint(plist); SListPushFront(&plist, 4); SListPrint(plist); SListPushFront(&plist, 5); SListPrint(plist); SListPushFront(&plist, 6); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListDestroy(&plist); } void TestList3() { SListNode* plist = NULL; SListPrint(plist); SListPushFront(&plist, 1); SListPrint(plist); SListPushFront(&plist, 2); SListPrint(plist); SListPushFront(&plist, 3); SListPrint(plist); SListPushFront(&plist, 4); SListPrint(plist); SListPushFront(&plist, 5); SListPrint(plist); SListPushFront(&plist, 6); SListPrint(plist); SListModify(SListFind(plist, 1), 99999); SListPrint(plist); SListModify(SListFind(plist, 2), 99999); SListPrint(plist); SListModify(SListFind(plist, 3), 99999); SListPrint(plist); SListModify(SListFind(plist, 4), 99999); SListPrint(plist); SListModify(SListFind(plist, 5), 99999); SListPrint(plist); SListModify(SListFind(plist, 6), 99999); SListPrint(plist); SListDestroy(&plist); } void TestList4() { SListNode* plist = NULL; / SListInsertAfter SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPushFront(&plist, 6); SListPrint(plist); SListInsertAfter(SListFind(plist, 1), 999999); SListPrint(plist); SListInsertAfter(SListFind(plist, 6), 999999); SListPrint(plist); SListInsertBefore SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPushBack(&plist, 6); SListPrint(plist); SListInsertBefore(&plist, SListFind(plist, 6), 999999); SListPrint(plist); SListInsertBefore(&plist, SListFind(plist, 1), 999999); SListPrint(plist); / SListEraseAfter SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPushBack(&plist, 6); SListPrint(plist); SListEraseAfter(SListFind(plist, 1)); SListPrint(plist); SListEraseAfter(SListFind(plist, 3)); SListPrint(plist); SListEraseAfter(SListFind(plist, 5)); SListPrint(plist); // 传递最后一个节点位置会出问题 //SListEraseAfter(SListFind(plist, 5)); //SListPrint(plist); / SListErasePos SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPushBack(&plist, 6); SListPrint(plist); SListErasePos(&plist, SListFind(plist, 1)); SListPrint(plist); SListErasePos(&plist, SListFind(plist, 6)); SListPrint(plist); SListErasePos(&plist, SListFind(plist, 2)); SListPrint(plist); SListErasePos(&plist, SListFind(plist, 3)); SListPrint(plist); SListErasePos(&plist, SListFind(plist, 4)); SListPrint(plist); SListErasePos(&plist, SListFind(plist, 5)); SListPrint(plist); / SListEraseBefore SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPushBack(&plist, 6); SListPrint(plist); SListEraseBefore(&plist, SListFind(plist, 6)); SListPrint(plist); SListEraseBefore(&plist, SListFind(plist, 6)); SListPrint(plist); SListEraseBefore(&plist, SListFind(plist, 6)); SListPrint(plist); SListEraseBefore(&plist, SListFind(plist, 6)); SListPrint(plist); 不能传第一个节点的位置 //SListEraseBefore(&plist, SListFind(plist, 1)); //SListPrint(plist); SListEraseBefore(&plist, SListFind(plist, 6)); SListPrint(plist); SListDestroy(&plist); } int main() { //TestList1(); //TestList2(); //TestList3(); TestList4(); return 0; }
写在最后
对于单链表来说，其难度主要在于对指针的运用，能够自我实现单链表，对我们代码能力的提升有很大的帮助。当然，在后续的一些数据结构的学习当中，单链表的一些思想是能用上的。
感谢阅读本小白的博客，错误的地方请严厉指出噢！
