单链表专题（中）

我们接着上一篇文章，继续对单链表的实现进行扩充

链表的头删

我们在进行头删的时候，不能先释放掉头节点再将头节点传到第二节点上，这样会导致找不到第二个节点了

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);  //链表不能为空SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}   

链表的查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//此时 pcur == NULLreturn NULL;
}

我们注意看一下只有一个节点的情况：

只有一个节点的时候，此时 next = NULL, *pphead = NULL，符合一个节点头删后变成空链表的情况，所以该代码适用于所有情况。

在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead)；assert(pos);}

这里的 pos 为链表中的某个指定的位置

这里请注意 *pphead 不能为空，因为如果 *pphead 为空了，那 pos 肯定也为空，我们是无法在空指针前面插入数据的，所以断言一下

所以我们的思路是：

1. 根据 pos 节点找到前一个节点和后一个节点
2. 创建一个新的节点
3. 将三者依次相连

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = SLTBuyNode(x);newnode->next = pos;prev->next = newnode;
}

 特殊情况： 当 pos 节点为首节点时，prev 节点是找不到的，导致在循环中遍历到结束后跳出该链表造成空指针的解引用，程序报错。所以该情况要特别讨论，即头插

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}

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

先看函数的定义：

void SLTInsertAfter(SLTNode* pos, SLTDataType x)；

这个函数只需要两个参数而不需要头节点的地址。原因是我们是在指定位置之后插入数据，而关于链表的查找节点是单向的，只能从前一个节点往后一个节点遍历，不可回溯。

我们思考一个问题，将 pos 节点 newnode 节点 pos->next 节点连接起来的顺序是什么样的？

显然，如果我们先将 pos 节点和 newnode 节点相连，则 pos->next == newnode ，再将 newnode 和 pos->next相连,即 newnode->next == pos->next ，很容易发现问题，pos->next 节点已经被换了所以这样的顺序并不成立。正确的做法是 newnode 节点先和 pos->next 节点相连，再将 pos 节点和 newnode 节点相连。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

删除pos节点

思路如下：

1. 找到 pos 节点的前一个节点 prev
2. 将前一个节点与 pos 节点的后一个节点相连
3. 释放 pos 节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead && pphead);assert(pos);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

 同样的问题，假设链表要释放的是头节点的时候，此时 prev 节点无法找到导致出现对空指针解引用的错误报错。所以要分情况讨论

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead && pphead);assert(pos);if (pos == *pphead){//与头删代码一致SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

删除pos之后的节点

思路很简单：

1. 找到 pos 的下一个节点 pos->next 和下一个节点的下一个节点 pos->next->next
2. 将pos 节点和下下个节点相连
3. 释放掉下一个节点 pos->next

我们先上代码：

void SLTErase(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

为什么这里我们定义了临时变量 del 去储存 pos->next 呢？

看回之前的思路，我们如果将 pos 节点和下下个节点相连，即 pos->next = pos->next->next 后，再释放 pos->next 节点，我们释放的不再是 pos 节点的下一个节点而是下下个节点了，顺序乱了。所以创建临时变量去储存 pos->next 隔离开关系即可

链表的销毁

因为我们的链表是动态生成的，所以用完了要及时销毁

链表是一个一个生成的，所以销毁也是一个一个销毁

我i们不能一上来就把头节点销毁了，这样如何找到下一个节点呢？所以，我们先储存后一个节点，在删除前一个节点，这样依次往后走，直到所有节点都被销毁

void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

至此，单链表的实现就全部结束了 ！