【C语言数据结构】单链表详解_c语言单链表

作者：热爱编程的小y
专栏：C语言数据结构
格言：能打败你的只能是明天的你

一、导言

上一篇关于顺序表的文章提到过，链表和顺序表都属于线性表，是一对孪生兄弟，他们之间是相辅相成，相互互补的，现实中很多情况下顺序表和链表会一同使用。既然他们俩之间是相互成就的，那么就说明他们都不是完美的，都有各自的优缺点。顺序表的缺点是什么呢？

有关顺序表的详细内容在这

顺序表的缺点：

1.中间/头部的插入删除，时间复杂度为O(N)
2.增容需要申请新的空间，拷贝数据，释放旧空间。会有不小的消耗。
3.增容一般是呈2倍地增长，势必会有一定地空间浪费，例如当前容量为100，满了以后增容到200，我们再继续插入5个数据，后面就没有数据插入了，那么就浪费了95个数据。

要想解决上述问题，就要用到链表。下面我们来了解一下链表的结构，并且本章会就单链表进行一个具体讲解。

二、概念及结构

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

在逻辑上可以把他想象成一辆火车。

火车可以向前行驶，也可以向后行驶，也可以转个圈，理论上火车足够长，轨道闭合的话，它还可以头为相接。

链表也是一样，既可以单向，也可以双向，也可以首尾相接。

而单链表呢就是一辆不能倒车也不能转圈的火车，它的轨道一路向前。

火车由一节一节的车厢组成，同样，链表由一个个的节点构成。它的每一个节点都是一个单独的结构体，结构体中包含两个参数，分别是具体存放的数据，以及指向下一个节点的地址的指针，这个存放地址的参数用于链接下一个节点，就像每一节火车车厢后面的挂钩一样。

区别于顺序表中用于表示当前位置的参数1和表示总容量的参数2，链表不需要参数来表示内存大小，因为它不需要考虑内存，每一个节点间并不连续，需要新的节点就重新开辟空间。

下面用画图来进一步了解。

在逻辑上我们可以画出这样一幅图，phead是第一个节点的地址，也就是火车头，后面通过指针链接一节节的车厢，直到最后一个指针为空，链表结束。这样看起来貌似链表之中临近节点是相连的，但事实上它们之间并没有像火车挂钩一样的东西来连结，而是各自独立。

现实中数据在内存中的变化长这样，不够图中的的箭头也仅仅用于方便理解，现实中并没有这样的箭头指向。实际应是这样：

清楚了链表的结构之后，我们来具体实现一下单链表。

三、单链表的接口实现

（一）准备工作

1. 创立文件

我们需要创立三个文件，分别是SList.c，SList.h，Test.c 。

SeqList.h 内包含引用的头文件，函数的声明，结构体的声明。

SeqList.c 内包含函数的定义，功能具体这里实现。

Test.c 负责各项功能的测试与具体运用。

1. 函数与结构体的定义

和当时实现顺序表一样，我们还是把链表中要存放的参数类型在头文件中重命名，之后定义变量的时候就用这个新名称。指针的类型也是一个结构体，指向下一个完整且独立的节点。

 
typedef int SLTDateType;/*对存放的数据类型进行重命名，想修改类型只需修改一处*/
typedef struct SListNode
{
    SLTDateType data;/*存放的数据*/
    struct SListNode* next;/*结构体类型的指针，指向存放下一个数据的空间，可以为NULL*/
}SListNode;/*声明节点*/

链表的功能与顺序表差不多，无非就是各种增删查改，我们来在头文件中声明一下实现各个功能的函数。

 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
 
// 单链表打印
void SListPrint(SListNode* phead);
 
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x);
 
// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x);
 
// 单链表的尾删
void SListPopBack(SListNode** pphead);
 
// 单链表头删
void SListPopFront(SListNode** pphead);
 
// 单链表查找
SListNode* SListFind(SListNode* phead, SLTDateType x);
 
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
 
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
 
// 单链表的销毁
void SListDestroy(SListNode* phead);

（二）具体实现

1. 节点的动态申请

因为在插入数据的时候，我们都需要动态申请一个新节点，因此可以把节点的申请分装成一个函数。

malloc函数申请开辟空间后要判断是否开辟失败。并且要记得把结构体内的指针初始化为空。

 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//申请一个新节点
    if (newnode == NULL)
    {
        perror("SListPushBack::malloc");
        return;
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
    return;
}

1. 头插与尾插

说明：头插是在头部插入数据，尾插则是在末尾插入数据。

在进行尾插操作时，因为不像顺序表有表示当前数据个数的参数，我们首先应该要自行找到最后一个节点所处的位置。这里我们采用遍历的方法。先判断第一个节点，如果它的next指针不为空，就找第二个节点，一直找到某个节点的next指针为空，说明这个节点就是尾巴。想实现上述操作，就必须找一个额外的指针变量tail来遍历，tail初始化为首节点地址，tail内部指针不为空就把这个指针赋值给tail，这样tail就指向了下一个节点。

 
SListNode* tail = *pphead;
        while (tail->next != NULL)//tail != NULL?? NO
        {
            tail = tail->next;
        }
        tail->next = newnode;//tail = newnode?? NO

注意看，这里的判断条件是tail中的next指针不为空，那为什么不是tail不为空呢？

如果判断条件变成tail不为空的话，当tail指向最后一个节点时，它并没有结束遍历，而是进一步变成了一个位置不明的空指针，这样就满足不了条件了。

再次注意，tail不能通过tail++或者++tail的方式实现遍历，原因是链表的各个节点之间并不一定连续，而指针++操作或者++指针操作是让指针指向与先前的地址连续的下一个地址。

尾插操作还需要考虑链表为空的情况，如果为空，就不存在尾巴了，上面在尾巴后面插入数据的方式就无效了。为空的话只需要直接赋值即可。

还要注意，无论是头插还是尾插，本质上都是对一个指针的内容进行改变。就像我们要通过函数改变一个整形变量的大小时，传给函数的参数应该是这个整形变量的地址。我们要对一个指针变量的内容进行修改，传参就得是一个二级指针。

由此可得代码如下：

 
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
    /*申请一个新节点*/
    SListNode* newnode = BuySListNode(x);
    /*链表为空*/
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    /*链表不为空*/
    else
    {
        /*找尾巴*/
        SListNode* tail = *pphead;
        while (tail->next != NULL)//tail != NULL?? NO
        {
            tail = tail->next;
        }
        tail->next = newnode;//tail = newnode?? NO
    }
    return;
}

相较于尾插，头插显得更为简单，它不需要找到首节点，因为传参传入的就是第一个节点的地址，直接拿来用即可，也不需要判断链表是否为空，因为它是新节点的后面接上首节点，而不像尾插在尾节点后面接上新节点时要考虑尾节点是否存在。

由此可得代码如下：

 
// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x)
{
    /*申请一个新节点*/
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
    return;
}

1. 头删与尾删

进行尾删操作时，同样也需要先找到尾巴，然后把倒数第二个节点内指向最后一个节点的指针赋值为空，就等同与火车的倒数第二节车厢后面的挂钩松开了，最后一节车厢自然就跑走了。但是也不能任由那节不要的车厢继续留在铁轨上，要把它挪开免得发生事故。同样地，要对最后一个节点地空间进行释放。

不同于尾插，我们要找的实际上是倒数第二个节点的位置，所以我们只需要在尾插tail->next遍历的基础上再加上一个->next，也就是tail->next->next的形式，这样找到的就是倒数第二个节点的位置了

但是因为tail往后跳了两个节点，就是说想实现上述遍历就至少得有两个节点，因此要考虑只有一个节点的情况，只有一个节点的话就可以直接释放空间赋值为空。

与尾插一样，也要考虑没有尾巴，也就是链表为空的情况，若为空，直接返回。

由此可得代码如下：

 
// 单链表的尾删
void SListPopBack(SListNode** pphead)
{
    /*链表为空*/
    /*assert(*pphead);*/
    if (*pphead == NULL)
        return;
    /*只有一个节点*/
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        /**pphead = (*pphead)->next;*///内存泄漏
    }
    /*不止一个节点*/
    else
    {
        /*找尾巴*/
        SListNode* tail = *pphead;
        while ((tail->next)->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
    return;
}

头删也比尾删简单，可以让指向首节点的指针指向后一个节点，并释放掉首节点的内存，并赋值为空。但是有一个问题，首节点被赋值为空之后，其中指向下一个节点地址的指针也变成空，如此一来我们以为新的首节点地址是原来的第二个节点的地址，但是实际上被一同赋值成了空。

因此这当中需要一个媒介，一个指向首节点的地址的新指针first，这样能保证首节点空间被释放掉后，新的首节点地址不为空。

头删同样要考虑链表为空的情况。

由此可得代码如下：

 
// 单链表头删
void SListPopFront(SListNode** pphead)
{
    /*链表为空*/
/*assert(*pphead);*/
    if (*pphead == NULL)
        return;
    SListNode* first = *pphead;
    *pphead = (first)->next;//为什么不直接让 *pphead = (*pphead)->size??因为释放后*pphead会变成NULL
    free(first);
    first = NULL;
    return;
}

1. 打印与查找

单链表的打印同样通过遍历来实现，其原理与需要遍历的尾插尾删相类似，这里就不过多介绍。

代码如下：

 
// 单链表打印
void SListPrint(SListNode* phead)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
    return;
}

实现单链表查找时我们需要考虑一个问题，它的返回时应该是什么，如果查找结果的显示是通过printf来实现，那么返回值直接为空即可，但是链表往往用不到打印，而我们查找到的结果也是想着直接拿来使用，所以这里的返回值应该和节点的类型相同，是一个结构体类型的指针。

 
// 单链表查找
SListNode* SListFind(SListNode* phead, SLTDateType x)
{
    SListNode* findcode = phead;
    while (findcode != NULL)
    {
        if (findcode->data == x)
            return findcode;
        findcode = findcode->next;
    }
    return NULL;
}

1. 任意位置的插入与删除

实现了头删尾删，头插尾插之后，单链表还应该具备在任意位置改变数据的功能。

实现任意位置的插入我们只能实现在指定位置pos之后的插入，为什么不是在pos之前呢？先来看一张图：

如此一来就明白了，原来在pos前插入的时候，新节点中的值为NULL的dest赋值给了前一个节点，这样就明显不符合要求了。

由此可得代码如下：

 
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
    /*申请一个新节点*/
    SListNode* newnode = BuySListNode(x);
    SListNode* tmp = pos->next;
    pos->next = newnode;
    newnode->next = tmp;
    return;
}

删除的时候我们也只能实现对pos位置之后的节点的删除，为什么不删pos位置或者pos之前呢？原因是：要删 pos 位置的话就要找到存放pos地址的前一个节点的位置，让前一个节点与后一个节点对接，但事实上是找不到前一个节点的，pos位置之前节点的删除更不可能实现了。

由此可得代码如下：

 
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
    SListNode* delete = pos->next;
    pos->next = delete->next;
    free(delete);
    delete = NULL;
    return;
}

1. 单链表的销毁

我们想要销毁单链表的某一个节点时，应当先用free函数释放内存，再将其置空，因此我们传参传入的应该是一个二级指针，这样才能对一级指针进行改变。

由此可得代码如下：

 
// 单链表的销毁
void SListDestroy(SListNode** pphead)
{
    assert(pphead)
    SListNode* cur = *pphead;
    while(cur)
    {
        SListNode* tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    *pphead = NULL;
    return;
}