C语言-数据结构之链表（附详细代码）
在我的前一期的文章里，我讲到了顺序表。顺序表相比于数组，它有很多优点，比如可以扩容，可以随意增删等等。但我们也可以发现它的不足：首先是realloc在异地扩容时会造成极大地性能损耗，效率太低；其次每次扩容是将总空间扩大到原来的两倍（或三倍），这样难免会造成内存上的浪费。针对这两个问题，就迎来了我们今天要讲的链表。
目录
单链表
头插和尾插
头删和尾删
在指定位置插入 / 删除
链表的分类
双链表
首先链表是一种线性表，与顺序表不同，链表像是地铁，链表由一个个节点连接而成，这些节点就像是地铁站，我们从一个地铁站出发，就可以找到下一个地铁站，我们的数据，也就存在这些地铁站里，找到地铁站，我们就可以拿到存储的数据。当我们想要对链表进行“扩容”时，只需要新建一个地铁站，再用地铁连接起来，这样就可以避免顺序表那样一次“开辟一片”的浪费了。
那我们要怎么实现呢？链表最关键的地方就是，我可以从一个节点找到下一个节点，那我们就要知道下一个节点在哪？怎么知道呢 就像是一个地铁站明确知道下一个地铁站的地址——我们只需要从一个节点里存入下一个节点的地址，就可以找到它了。所以每个节点需要存储两类数据，一类是我们实际需要的数据，另一类就是下一个节点的地址。这样的链表也叫作单链表。
单链表
就像这样。每个节点都存储着下一个节点的地址，这样无论各个节点在内存当中是不是连续存储的，我们都可以通过地址直接找到下一个节点。这里我们把最后一个节点（也叫作“尾节点”）里存储的地址置为空，当我们想要“扩容”的时候，只需要用malloc新建一个节点，然后把这个新节点的地址赋值给原尾节点里的next就可以了。
那我们就开始代码实现吧。
首先我们要定义一个结构体表示节点。我们知道，这个结构体里面应该有下一个节点的地址，还要有实际需要的数据。那这个数据是什么类型呢？不知道，我们可以重命名一个类型。
typedef int SLTDataType;这里我们让SLTDataType表示我们要存储的数据类型，这里我们以整型为例。当我们想要存储其他类型数据时，只需要更改这条语句就可以了（把这里的 int 改成我们想要的类型）。
知道了这些，我们就可以定义节点这个结构体了。(这里我们为了方便使用结构体，又给了重命名)
//节点类型
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;接下来我们讲一下怎么创建功能函数来实现链表的一些功能。通过链表的特性我们知道，只需要知道链表的第一个节点（也就是“头节点”），就能够找到后面的所有节点。所以当我们定义功能函数传参时，只需要传头结点的地址，就可以获取整个节点的信息。
头插和尾插
首先是插入新节点，分为头插和尾插。先讲尾插，我们在前面就提到了，尾插就是用malloc新建一个节点，然后把新节点的地址赋值给原尾结点的next。但是还有个特殊情况，就是当我们的头结点为空时，此时链表的空的，我们要让这个新节点成为头节点，只需要让头节点的指针指向新节点，这个新节点就成了头节点，后面就可以正常添加新节点了。但这里要强调一下，我们让头节点指针指向新节点，其实是改变了原头节点指针的值，而我们如果只传头节点的指针，那我们改变的只是形参。所以这里我们想要改变实参（即头节点指针的值），需要传头节点的二级指针。然后对于新建节点，我们后面在写头插的时候也要用到，所以我们干脆把这一步写成一个函数，便于使用。同时我们给这个函数传我们想要存储的实际数据，返回新节点的地址。
//新建节点
SLTNode* BuyNode(SLTDataType x) //x为需要存储的实际数值
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode)
{
newnode->data = x;
newnode->next = NULL;
return newnode; //返回新节点的地址
}
else //考虑malloc开辟空间失败的情况
{
perror("malloc fail!
");
exit(1);
}
}接下来我们再写尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead); //pphead不能为空
SLTNode* newnode = BuyNode(x); //创建新节点
if (*pphead) //头节点不为空
{
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next; //循环结束后找到尾节点
}
ptail->next = newnode; //原尾节点的next存入新节点的地址
}
else //头节点为空
{
*pphead = newnode; //头节点指针指向新节点，新节点成为头节点
}
}这样我们既不会造成空间浪费，同时又提高了效率（malloc无需数据拷贝和旧内存释放操作）。
接着，头插就是让新节点插到原头节点的前面，让新节点成为新的头节点。头节点指针指向新节点，所以我们仍然要传二级指针。
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead); //ppehead不能为空
SLTNode* newnode = BuyNode(x);
newnode->next = *pphead; //新节点插到原头节点的前面
*pphead = newnode; //新节点成为新的头节点
}头删和尾删
有插入就要有删除，同样的，删除也分为头删和尾删。需要注意的是，既然我们要删除节点，那么链表就不能为空。由于每个节点都是由 malloc 开辟的，所以我们找到对应节点直接用 free 释放掉就好啦。这里再强调一下，当链表只有一个节点（即只有一个头节点）时，我们释放掉头节点之后还要将头节点的指针置为空，否则头节点指针会变成野指针。所以我们仍然要传头节点二级指针。对于尾删，还要注意的是，删除尾节点后，原本倒数第二个节点会成为新的尾节点，它的 next 应该置为空。
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead); //pphead 和 *pphead 都不能为空
if ((*pphead)->next == NULL) //链表只有一个节点
{
free(*pphead);
*pphead = NULL; //头节点指针置为空
}
else
{
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
while (ptail->next)
{ //循环结束后
prev = ptail; //prev找到倒数第二个节点
ptail = ptail->next; //ptail找到尾节点
}
free(ptail);
prev->next = NULL; //释放掉原尾节点后，prev指向新的尾节点
}
}接下来就是头删。注意头删就是删掉头节点，则原头节点的下一个节点成为新的头节点。
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* newhead = (*pphead)->next; //提前找到头节点的下一个节点
free(*pphead);
*pphead = newhead; //找到新的头节点
}在指定位置插入 / 删除
当然，除了头插 / 尾插和头删 / 尾删，我们还可以在指定位置进行插入删除，前提是我们要知道这个指定位置的地址。这里我们以通过数据获取地址的方式为例（当多个节点存有相同数据时，获取第一个存有该数据的节点地址）。无非就是从头节点开始对链表进行遍历比较。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;//找到了
}
pcur = pcur->next;
}
return NULL;//没找到
}获取到指定位置后，我们就可以对指定位置进行插入删除。先看插入，我们可以选择在指定位置之前或之后插入数据。我们先看在指定位置之后插入数据。指定位置的节点应该指向新节点，而新节点指向原先指定位置之后的数据。
比如我们要在存有“2”数据的节点后面出入新节点：
//在指定位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos); //指定位置不能为空
SLTNode* newnode = BuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}接下来看在指定位置之前插入数据，我们需要让指定位置的前一个节点指向新节点，新节点指向指定位置的节点。所以我们需要用头节点指针找到指定位置的前一个节点。注意这里还有特殊情况，就是当指定位置是头节点时，就相当于头插，所以跟头插函数一样，需要传头节点的二级指针，可以直接调用之前写过的头插函数。
//在指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(*pphead && pphead && pos); //都不能为空
SLTNode* newnode = BuyNode(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 SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead && pos);
if (pos == *pphead)
{
SLTPopFront(pphead); //调用前面的头删
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}另外还有删除指定位置之后的节点，此时没有头删的情况，而且我们只需要让指定位置节点与其下下个节点相连，而下下的节点可以通过指定位置节点找到，所以我们就不用传头节点地址了。
//删除指定位置之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* newnext = pos->next->next; //提前把下下个节点地址存起来
free(pos->next);
pos->next = newnext;
}最后就是链表的销毁，我们用malloc申请的内存不用时需要释放掉。
这里最后需要把头节点指针置为空，所以我们还是传头节点的二级指针。
//链表的销毁
void SLTDesTroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode * last = *pphead;
while (last)
{
SLTNode* newnext = last->next;
free(last);
last = newnext;
}
*pphead = NULL; 头节点指针置为空
}链表的分类
以上我们讲的都是单链表，其实链表有很多种。可以根据有头或无头，单向或双向，循环或非循环把链表分为八种。我们所说的单链表其实就是无头单向非循环链表。
那这里的“头”是什么呢？我们称之为“哨兵位”。我们前文提到的头节点只是为了方便表达，哨兵位其实才是真正意义上的头节点。哨兵位不存储有效数据，哨兵位的下一个节点是第一个有效节点。哨兵位自被创建起就是雷打不动的，所有节点都只能插在哨兵位的后面。此时的头插则是插在哨兵位的后面一个节点的位置。
那什么是单向和双向呢。单向就是从一个节点可以找到下一个节点，而双向则是从一个节点可以找到上下两个节点
无非就是在定义节点结构体时，我们需要多存入上一个节点的地址。就像是地铁站里不只有一个方向的地铁，还有与其相反的方向的地铁。
那什么是循环呢？其实就是当尾节点指向第一个节点时，链表呈环状。
双链表
单链表是无头单向不循环链表，双链表则恰好相对，是带头双向循环链表。其实学后了单链表之后，双链表的实现也就不在话下了。大家感兴趣的话可以参考我发布在Gitee上的代码 双链表学习 。
链表和顺序表的比较
学到这里你可能会觉得链表相比于顺序表是完美的上位替代。实则不然，尽管链表确实在内存空间利用率和运行效率上优于顺序表，但它也有不足之处。由于链表的各个节点在内存中的位置是不确定的，不像顺序表的数组那样在内存中紧密排列，导致链表不可以向顺序表那样通过下标直接访问到数据；也正因如此，又导致了链表的高速缓存利用率低的问题。所以，尽管链表的优点很多，应用场景也比顺序表广泛，但顺序表在某些场景下，仍然有着独特的作用......
