数据结构-单链表

1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

从以上图片可以看出：

1.链式结构在逻辑上是连续的，但在物理上不一定是连续的。

2.现实中的节点一般是在堆上申请出来的。

3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，可能不连续。

2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

2.1单向或双向

2.2带头或者不带头

2.3循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3 单向无头链表的实现

在头文件中包含一些函数的声明。

因为每个节点都是一个结构体，所以每个节点都要存放一个结构体的指针，指向下一个节点。

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

SLTNode* BuyListBNode(SLTDataType x);

void PrintSList(SLTNode* phead);

void SLTPushBcak(SLTNode** pphead,SLTDataType x);//尾插

void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插

void SLTPopback(SLTNode** pphead);//尾删

void SLTPopFront(SLTNode** pphead,SLTDataType x);//头删

void SLTFind(SLTNode* pphead,SLTDataType x);//查找

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos之后插入x
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);

3.1打印链表

打印链表首先要遍历链表，那么循环的条件就是走到空。所以我们创建一个临时变量cur代替头节点用来遍历，这样就可以不用动头节点，打印就是将节点中的数据打印出来，所以先将各个节点的数据打印出来，再指向下一个节点，需要注意的是next就是下一个节点的地址，所以将cur->next赋给cur就可以拿到下一个节点的地址了，拿到地址就可以继续访问下一个节点了。

void PrintSList(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

3.2创建节点

这里malloc一个节点出来就行了，然后判断是否malloc成功，将需要的数据存进data中就行了，然后将next置为NULL，然后返回这个节点。

SLTNode* BuyListBNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*) malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;

    return newnode;
}

3.3尾插节点

这个函数的第一个参数是一个二级指针，目的是为了修改结构体，尾插节点首先需要创建一个节点，然后·判断一下当前链表是否为空，如果为空则将这个节点设置为头节点，所以解引用这个二级指针，拿到一级指针的地址，就可以修改了。如果不为空，则创建一个临时变量来保存头节点的地址，然后使用这个变量来遍历链表找到尾节点，循环的结束条件就是tail的next为空，因为尾节点的next是NULL，循环结束之后tail就走到了尾节点的位置，然后将新节点赋给tail的next即可。

void SLTPushBcak(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuyListBNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

3.4头插节点

尾插节点还是需要创建一个节点，然后将这个节点的next指向这个头节点，但是头插之后头节点就是新插入的这个节点，所以需要使用二级指针，最后将新节点newnode赋给*pphead，这样头节点就更新了。

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuyListBNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

3.4尾删节点

尾删需要分很多种情况：

1.没有节点，这种情况就直接暴力检查，没有节点是删除不了的，直接assert即可。

2.一个节点，如果是一个节点的话，这个节点的next一定是NULL，所以使用if判断*pphead->next是否为NULL，如果是的话直接free掉这个节点然后置为空就行了。

3.如果是多个节点的话创建一个临时变量来遍历链表找到尾，需要注意的是，这个循环的结束条件是tail->next->next为空。下面这段代码就是错误的，因为free（tail）的本质是将tail指向的节点free，再将tail置为空相当于给tail赋值0x00000000，局部变量出了作用域就销毁了，但是前一个节点还是野指针，next虽然还是指向这个节点，但是这个节点已经free了。所以解决的方法就是找到tail的前一个节点，然后free掉tail->next，再置空。

正确的方法：

void SLTPopback(SLTNode** pphead)
{
    assert(*pphead);
    //一个节点
    if ((*pphead)->next = NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else//多个节点
    {
        SLTNode* tail = *pphead;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

3.5头删节点

头删也需要用到二级指针，然后暴力检查链表是否为空，不为空则创建一个变量newnode来保存头节点的next，然后free掉头节点，再将newnode赋给*pphead。

void SLTPopFront(SLTNode** pphead)
{
    assert(pphead);
    SLTNode* newhead = (*pphead)->next;
    free(*pphead);
    *pphead = newhead;
}

3.6查找节点

这个函数很简单，找到data就行，然后返回节点。

SLTNode* SLTFind(SLTNode* pphead, SLTDataType x)
{
    SLTNode* cur = pphead;
    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

3.6在pos位置之前插入节点

pos的位置也需要分情况：

1.暴力检查

2.如果是头插，直接调用头插函数。

3.正常情况，创建一个结构体变量来遍历链表寻找pos节点，但是循环的结束条件设置成pre->next=pos最合适，因为我们需要保存pos的前一个节点，所以循环结束后pre就是pos的前一个节点，此时创建一个需要插入的节点newnode，将pre的next指向newnode，再将newnode的next指向pos，就完成链接了。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pos);
    if (*pphead == pos)
    {
        SLTPopFront(pphead,x);
    }
    else
    {
        SLTNode* pre = *pphead;
        while (pre->next != pos)
        {
            pre = pre->next;
        }
        SLTNode* newnode = BuyListBNode(x);
        pre->next = newnode;
        newnode->next = pos; 
    }
}

3.7在pos位置之后插入节点

首先暴力检查，再创建一个新节点newnode，插入需要注意的是以下这种写法是错误的，因为当我们将pos的next指向newnode的时候，就与后面的节点完全断开了，然后newnode的next又指向pos的next相当于形成了一个死循环。正确的方法应该是pos的next指向newnode的next，相当于先将newnode的next指向pos的后一个节点形成newnode的尾部链接，再将pos的next指向newnode完成newnode的头部链接。

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

3.8删除pos位置的节点

首先暴力检查，再判断pos是不是头删，正常删除就是创建一个变量遍历链表，pos的next为空作为循环的结束条件，循环结束之后pre就是pos的前一个节点，这个时候将pre的next指向pos的next也就是pos的下一个节点就行了，然后frre掉pos，这时候就不需要置空了。

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pos);
    if (pos == *pphead)
    {
        SLTPopFront(pphead);
    }
    else
    {
        SLTNode* pre = *pphead;
        while (pre->next != pos)
        {
            pre = pre->next;
        }
        pre->next = pos->next;
        free(pos);
    }
}

3.9删除pos位置之后的节点

首先暴力检查，然后再检查是否为尾节点。创建一个变量posNext保存pos的下一个节点，然后即将pos的下一个节点指向pos的下下个节点即可。然后free掉posNext。

void SLTEraseAfter(SLTNode* pos)
{
    assert(pos);
    assert(pos->next);//检查是否是尾节点
    SLTNode* posNext = pos->next;
    pos->next = posNext->next;
    free(posNext);
}

今天的分享到这里就结束啦！谢谢老铁们的阅读，让我们下期再见。