让单链表不再云里雾里

一日不见，如三月兮！接下来与我一起创建单链表吧！

单链表的结构：

创建单链表：

增加结点：

插入结点：

删除结点：

打印单链表：

单链表查找：

单链表指定位置插入：

单链表指定位置删除：

答疑解惑：

结语：

单链表的结构：

单链表有不带头单向不循环，和带头单向非循环两种类型，我们将探索的是不带头单向不循环的链表；它有两种结构：逻辑结构和物理结构，如下图：

因为物理结构便于理解，所以我们参照它来进行代码书写，物理结构中我们访问的都是地址，所以我们会使用指针，且蓝色所指表示它们两的地址相同！

创建单链表：

首先我们要定义一个结构体，然后我们要访问数值，所以会定义一个整型变量，为了找下一个数值的地址，我们还需创建一个指针

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;//方便查找下一个结点
}SLTNode;

增加结点：

因为每次插入，都需要书写一个代码，为了节省空间，我们将它包装成一个函数，方便我们进行调用

SLTNode* Buynewnode(SLDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//开辟空间
    if(newnode == NULL)//判断是否开辟成功
    {
        perror("malloc fail");
        return;
    }
    newnode->data = x;//将数据赋值
    newnode->next = NULL;
    
    return newnode;//返回地址
}

插入结点：

头插：

首先将一开始头的数据地址赋给新的结点的下一个(newnode->next)地址，再将头指针变为新结点

void SLTPushFront(SLTNode** pphead，SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = Buynewnode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

尾插：

首先判断链表是否为空的情况，若为空，则将新结点赋给头结点即可，如果不是，再进行找尾，当找到尾时，将新结点的地址赋给tail的下一个。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = Buynewnode(x);
    //判断是否为空
    if(*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        //找尾
        while(tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;//链接新结点
     }
}

删除结点：

头删：

先判断链表是否为空，若不为空，将第二个的数据地址赋给头指针即可，但我们怎么找到第二个的数据地址呢？我们可以先将头指针赋给一个指针进行保存，再将创建的指针找到其下一个的地址(即第二个数据的地址)赋给头指针，在释放第一个结点的地址即可。

void SLTPopFront(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead);
    SLTNode* begin = *pphead;//保存头指针
    *pphead = begin->next;
    free(begin)//释放第一个结点的空间
    begin = NULL;
}

尾删：

首先判断单链表是否为空，其次判断一下是否只有一个结点，若只有一个，直接将头指针释放置空即可，剩下的情况我们只要找到尾将它删除即可，有人想偷懒，将上面的找尾代码拷贝，然后将其置空，果真这么简单吗？会导致什么结果呢？又该怎么处理呢？

如果将tail置空，会使前一个结点的下一个指针变为野指针，tail置空是将局部变量置空，而非将结构体变量置空，若要改变这个情况，我们再定义一个结构体指针，找到tail的前面一个头结点，再将其下一个置空就行了

void SLTPopBack(SLTNode** pphead)
{
    //为空
    assert(pphead);
    assert(*pphead);
    //只有一个结点
    if((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* prev = NULL;
        SLTNode* tail = *pphead;
        //找尾
        while(tail->next != NULL)
        {
            prev = tail;//找到tail前一个结点
            tail = tail->next;
        }
        //释放掉尾结点
        free(tail)
        tail = NULL;
        prev->next = NULL；
    }
}

打印单链表：

将头指针赋值给一个指针变量，这样可以防止头指针被覆盖(这个作用这里体现不明显)，然后循环遍历就OK了

void SLTPrint(SLTNode* phead)
{
    SLTNode* begin = phead;
    //循环遍历
    while(begin)
    {
        printf("%d->", begin->data);
        begin = begin->next;
    }
    printf("NULL\n");
}

单链表查找：

将头指针赋值给一个指针变量，然后遍历，用if语句判断

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    SLTNode* cur = phead;
    while(cur)
    {
        if(cur->data == x)
        {
            //找到返回
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

单链表指定位置插入：

我们先定义一个指针变量，用来找我们指定插入的位置地址，找到这个指针变量的前一个位置的地址，再将新结点的地址赋给前一个的下一个地址(next)，再将指针变量赋给新节结点的下一个地址

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pos);//判断pos是否为空
    assert(pphead);
    SLTNode* newnode = Buynewnode(x);
    if(*pphead == pos)
    {
        newnode->next = pos;
        *pphead = newnode//将新结点赋给头指针
    }
    else
    {
        SLTNode* prev = *pphead;
        //找到pos前面一个地址
        while(prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = newnode;
        newnode->next = pos;
     }
}

单链表指定位置删除：

我们先定义一个指针变量，用来找我们指定插入的位置地址，找到这个指针变量的前一个位置的地址，再将指定位置的下一个，赋给前一个位置的下一个，再将指定位置释放置空

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pos);//判断pos是否为空
    assert(pphead);
    //只有一个结点
    if(*pphead == pos)
    {
        *pphead = pos->next;
         free(pos);
         pos = NULL;
    }
    else
    {
        SLTNode* prev = *pphead;
        //找pos前一个位置
        while(prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);//释放指定位置空间
        pos = NULL;
     }
}