单链表专题（中）

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

链表的头删

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

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 == NULL
    return NULL;
}

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

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

在指定位置之前插入数据

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

}

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

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

所以我们的思路是：

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节点

思路如下：

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之后的节点

思路很简单：

我们先上代码：

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;
}

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