数据结构（C语言篇）：（四）链表

前言 链表是数据结构中最基础且重要的线性结构之一，它以动态内存分配的方式实现元素的逻辑顺序存储，克服了数组静态内存分配的局限性。链表通过节点间的指针链接形成灵活的数据组织形式，在插入、删除等操作上具有显著的时间效率优势。本文将从链表的实现原理、核心操作算法到实际应用场景展开分析，帮助读者深入理解这一基础数据结构的设计思想与技术实现，下面就让我们正式开始吧！

一、单链表1.1 概念与结构 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。这样的结构就好像一节节火车一样，如下图所示：

在淡季的时候，火车的车厢会相应减少，旺季时火车的车厢则会额外增加几节。只需要将火车里的某节车厢去掉或者加上，是不会影响其他车厢的，每节车厢都是独立存在的。

在链表里，每节“车厢”是什么样的呢？如下图所示：

1.1.1 结点 与顺序表不同的是，链表里的每一节“车厢”都是独立申请下来的空间，我们将其称之为：结点/节点。

结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。

图中的plist指针变量保存的是第一个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望plist“指向”第二个结点，则只需要修改plist保存的内容为0x0012FFA0即可。

链表中的每一个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点的位置才能从当前结点找到下一个结点。

1.1.2 链表的性质 链表有如下的性质：

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

2、结点一般是从堆上申请的。

3、从堆上申请来的空间，是按照一定的策略分配出来的，每次申请的空间可能连续，

也有可能不连续。

结合我们之前所介绍的结构体知识，我们可以给每个结点对应的结构体代码：

假设当前保存的节点为整型：

代码语言：javascript复制struct SListNode

{

int data; //结点数据

struct SLitNode* next; //指针变量⽤保存下⼀个结点的地址

}; 当我们想要保存一个整型数据的时候，实际上是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个结点的地址（当下一个结点为空时保存的地址也为空）。

当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿上下一个结点的地址就可以了。

1.1.3 链表的打印 在给定的链表结构中，如何实现结点从头到尾的打印？如下所示：

1.2 单链表的实现1.2.1 头文件的准备 我们将链表结点的定义和函数声明等放在头文件中：

代码语言：javascript复制//SList.h

typedef int SLTDataType;

typedef struct SListNode

{

SLTDataType data; //结点数据

struct SListNode* next; //指针保存下⼀个结点的地址

}SLTNode;

void SLTPrint(SLTNode* phead);

//头部插⼊删除/尾部插⼊删除

void SLTPushBack(SLTNode** pphead, SLTDataType x);

void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);

void SLTPopFront(SLTNode** pphead);

//查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在指定位置之前插⼊数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//删除pos结点

void SLTErase(SLTNode** pphead, SLTNode* pos);

//在指定位置之后插⼊数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos之后的结点

void SLTEraseAfter(SLTNode* pos);

//销毁链表

void SListDestroy(SLTNode** pphead);1.2.2 函数的实现（1）SLTPushBack( )函数（尾插） 在实现尾插函数之前，我们要先来实现一个结点申请函数，即SLTBuyNode( )。

由于我们需要让SLTBuyNode最后的返回值是一个链表的结点，所以我们要把它的返回类型定义为 SLTNode* 。又因为我们需要在申请到的结点中存储数据，因此还需要向函数传递一个类型为 SLDataType 的参数。

为了实现内存的分配，我们需要使用malloc函数动态分配内存，其大小为SLNode结构体的大小，然后还需要将malloc函数返回的void*指针强制转换为SLTNode*类型。如下所示：

代码语言：javascript复制SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); 随后，为了保证内存分配成功，我们还需要设计一个错误检查的判断语句，如下所示：

代码语言：javascript复制if (newnode == NULL)

{

perror("malloc fail!");

exit(1);

} 如果malloc返回了NULL（分配失败），perror函数将会输出"malloc fail!"的信息并终止程序。exit(1)则表示程序将以退出码1异常退出。

接下来就是结点的初始化了，如下所示：

代码语言：javascript复制newnode->data = x; // 设置节点的数据域

newnode->next = NULL; // 设置节点的指针域为NULL 最后我们需要返回一个结点指针：

代码语言：javascript复制return newnode; 完整代码如下所示：

代码语言：javascript复制SLTNode* SLTBuyNode(SLTDataType x)

{

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

if (newnode == NULL)

{

perror("malloc fail!");

exit(1);

}

newnode->data = x;

newnode->next = NULL;

return newnode;

} 接下来我们就要正式开始实现尾插函数了。

首先我们需要思考一下，在给SLTPushBack函数传参时，我们需要传递的结点指针是一级指针还是二级指针呢？

我们需要明确：链表结点结构体所包含的其中一个成员是指向下一个结点的指针，即一级指针，我们在尾插时需要改变这一指针指向的地址，因此需要给尾插函数传递一个实参而不能传递形参。所以我们所以我们需要传递的是一个指向指针的指针，即二级指针。

事实上，如果我们传递的是一级指针，会出现如下的错误：

首先，为了保证传递给函数的pphead指针不为NULL，我们需要使用assert函数进行断言：

代码语言：javascript复制assert(pphead); 然后我们就需要调用之前介绍的SLTBuyNode函数来创建新结点：

代码语言：javascript复制SLTNode* newnode = SLTBuyNode(x); 我们还需要写一个判断语句，对链表为空的情况进行判断（如果链表为空就直接将新节点设置为头结点）：

代码语言：javascript复制if (*pphead == NULL)

{

*pphead = newnode;

} 当链表不为空时，处理如下：

代码语言：javascript复制else {

SLTNode* ptail = *pphead;

while (ptail->next != NULL)

{

ptail = ptail->next;

}

//找到了尾结点 ptail newnode

ptail->next = newnode;

} 在这里我们使用ptail指针从头结点开始遍历，通过while循环找到最后一个结点，并将尾结点的next指针指向新的结点。完整代码如下：

代码语言：javascript复制//尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)

{

assert(pphead);

//申请新节点

SLTNode* newnode = SLTBuyNode(x);

//链表为空

if (*pphead == NULL)

{

*pphead = newnode;

}

else {

SLTNode* ptail = *pphead;

while (ptail->next != NULL)

{

ptail = ptail->next;

}

//找到了尾结点 ptail newnode

ptail->next = newnode;

}

} 由于我们传递的是二级指针，所以在使用尾插函数传参时，还需要对链表的头结点取地址：

代码语言：javascript复制SLTNode* head = NULL; // 空链表

// 在尾部插入节点

SLTPushBack(&head, 10); // 链表: 10

SLTPushBack(&head, 20); // 链表: 10 → 20

SLTPushBack(&head, 30); // 链表: 10 → 20 → 30 当链表为空时，尾插函数的时间复杂度最好，为

O(1)；

当需要遍历整个链表找到尾结点时，时间复杂度最坏，为

O(n)；

平均情况的时间复杂度为

O(n)。

（2）SLTPushFront( )函数（头插） 画图分析如下：

头插的实现相比起尾插就简单得多了，最主要的一步是将新结点的next指针指向当前的头结点，并对头指针进行更新：

代码语言：javascript复制newnode->next = *pphead;

*pphead = newnode; 完整代码如下：

代码语言：javascript复制//头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)

{

assert(pphead);

SLTNode* newnode = SLTBuyNode(x);

//newnode *pphead

newnode->next = *pphead;

*pphead = newnode;

} 使用示例如下：

代码语言：javascript复制SLTNode* head = NULL; // 空链表

// 在头部插入节点

SLTPushFront(&head, 10); // 链表: 10

SLTPushFront(&head, 20); // 链表: 20 → 10

SLTPushFront(&head, 30); // 链表: 30 → 20 → 10 所有情况下，头插函数的时间复杂度都为

O(1)。

（3）SLTPopBack( )函数（尾删） 画图分析如下：

首先我们依旧需要利用assert断言对参数进行验证和对空链表进行检查：

代码语言：javascript复制assert(pphead && *pphead); 这是为了确保 pphead 不为 NULL，以及*pphead不为空，因为空链表无法删除节点。

接着来利用判断语句处理只有一个结点的情况：

代码语言：javascript复制if ((*pphead)->next == NULL)

{

free(*pphead); //直接释放头结点内存

*pphead = NULL; //将头指针置为NULL，表示链表为空

} 处理多个结点时，我们需要使用两个指针：prev（前驱指针）和 ptail（当前结点）。接着我们需要遍历链表直到找到尾结点，之后将前驱结点的next设置为NULL，并断开与尾结点的连接，最后释放尾结点内存并将指针置为NULL。如下所示：

代码语言：javascript复制else {

SLTNode* prev = NULL;

SLTNode* ptail = *pphead;

while (ptail->next)

{

prev = ptail;

ptail = ptail->next;

}

//prev ptail

prev->next = NULL;

free(ptail);

ptail = NULL;

} 完整代码如下：

代码语言：javascript复制//尾删

void SLTPopBack(SLTNode** pphead)

{

//链表为空不能删除

assert(pphead && *pphead);

//链表只有一个节点的情况

if ((*pphead)->next == NULL)

{

free(*pphead);

*pphead = NULL;

}

else {

SLTNode* prev = NULL;

SLTNode* ptail = *pphead;

while (ptail->next)

{

prev = ptail;

ptail = ptail->next;

}

//prev ptail

prev->next = NULL;

free(ptail);

ptail = NULL;

}

} 使用示例如下：

代码语言：javascript复制SLTNode* head = NULL;

SLTPushBack(&head, 10);

SLTPushBack(&head, 20);

SLTPushBack(&head, 30);

// 链表: 10 → 20 → 30

SLTPopBack(&head); // 删除30，链表: 10 → 20

SLTPopBack(&head); // 删除20，链表: 10

SLTPopBack(&head); // 删除10，链表: 空 当链表只有一个结点时，时间复杂度最好，为

O(1)；

当需要遍历整个链表找到尾结点时，时间复杂度最坏，为

O(n)；

平均情况为

O(n)。

（4）SLTPopFront( )函数（头删） 画图分析如下：

头删和头插一样，实现的逻辑相比尾删和尾插较为简单，其关键是保存下一个节点的指针、并释放头结点内存，如下所示：

代码语言：javascript复制SLTNode* next = (*pphead)->next;

free(*pphead); 完整代码如下：

代码语言：javascript复制//头删

void SLTPopFront(SLTNode** pphead)

{

assert(pphead && *pphead);

SLTNode* next = (*pphead)->next;

free(*pphead);

*pphead = next;

} 使用示例如下：

代码语言：javascript复制SLTNode* head = NULL;

SLTPushBack(&head, 10);

SLTPushBack(&head, 20);

SLTPushBack(&head, 30);

// 链表: 10 → 20 → 30

SLTPopFront(&head); // 删除10，链表: 20 → 30

SLTPopFront(&head); // 删除20，链表: 30

SLTPopFront(&head); // 删除30，链表: 空 时间复杂度在任何情况下同样都为

O(1)。

（5）SLTFind( )函数（查找） 首先我们需要初始化遍历指针，创建当前指针pcur并初始化为头指针，用于遍历链表中的每个结点，如下：

代码语言：javascript复制SLTNode* pcur = phead; 然后我们就来遍历链表了。先用while循环遍历链表，直到pcur为NULL为止；然后对每个结点检查其data是否等于目标值x，如果找到了匹配的结点，则立即返回该结点的指针：

代码语言：javascript复制while (pcur)

{

if (pcur->data == x)

{

return pcur;

}

pcur = pcur->next;

} 完整代码如下所示：

代码语言：javascript复制//查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)

{

SLTNode* pcur = phead;

while (pcur)

{

if (pcur->data == x)

{

return pcur;

}

pcur = pcur->next;

}

//未找到

return NULL;

} 使用示例：

代码语言：javascript复制SLTNode* head = NULL;

SLTPushBack(&head, 10);

SLTPushBack(&head, 20);

SLTPushBack(&head, 30);

// 查找节点

SLTNode* found = SLTFind(head, 20);

if (found != NULL) {

printf("找到节点，值为: %d\n", found->data);

} else {

printf("未找到节点\n");

} 当目标结点是头结点时，时间复杂度最好，为

O(1)；

当目标结点是尾结点或不存在时，时间复杂度最坏，为

O(n)；

平均情况为

O(n)。

（6）SLTInsert( )函数（在指定位置之前插入节点） 画图分析如下：

本函数实现的关键是分在头结点前插入，和在中间结点前插入两种情况讨论。

在头结点之前插入时，就相当于头插，那就可以直接调用现有的SLTPushFront函数，如下：

代码语言：javascript复制if (pos == *pphead)

{

//头插

SLTPushFront(pphead, x);

} 当在中间结点前插入（一般情况）时，我们先遍历链表找到 pos 结点的前驱节点 prev，将prev 的 next 指针指向新结点，最后将新结点的 next 指针指向 pos 结点。如下：

代码语言：javascript复制else {

//找pos的前一个节点

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

//prev newnode pos

prev->next = newnode;

newnode->next = pos;

} 完整代码如下：

代码语言：javascript复制//在指定位置之前插⼊数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)

{

assert(pphead && pos);

SLTNode* newnode = SLTBuyNode(x);

//pos指向头结点

if (pos == *pphead)

{

//头插

SLTPushFront(pphead, x);

}

else {

//找pos的前一个节点

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

//prev newnode pos

prev->next = newnode;

newnode->next = pos;

}

} 使用示例如下：

代码语言：javascript复制SLTNode* head = NULL;

SLTPushBack(&head, 10);

SLTPushBack(&head, 20);

SLTPushBack(&head, 30);

// 链表: 10 → 20 → 30

// 找到值为20的节点

SLTNode* pos = SLTFind(head, 20);

// 在20前面插入15

SLTInsert(&head, pos, 15);

// 链表变为: 10 → 15 → 20 → 30 时间复杂度的最好情况：

O(1) - 在头节点前插入

最坏情况：

O(n) - 需要遍历找到前驱节点

平均情况：

O(n)（7）SLTInsertAfter( )函数（在指定位置之后插入数据） 画图分析如下：

在实现本函数时，关键点在于明确指针的操作顺序，如下所示：

代码语言：javascript复制// 正确的顺序：

newnode->next = pos->next; // 第一步

pos->next = newnode; // 第二步

// 如果顺序颠倒：

pos->next = newnode; // 错误：会丢失原来的链表

newnode->next = pos->next; // 错误：newnode指向自己 我们可以将前插法和后插法对比一下：

特性

后插法 (SLTInsertAfter)

前插法 (SLTInsert)

时间复杂度

O(1)

O(n)

参数需求

不需要头指针

需要头指针

查找需求

不需要找前驱节点

需要找前驱节点

效率

更高

较低

完整代码如下：

代码语言：javascript复制//在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x)

{

assert(pos);

SLTNode* newnode = SLTBuyNode(x);

//pos newnode pos->next

newnode->next = pos->next;

pos->next = newnode;

} 使用示例：

代码语言：javascript复制SLTNode* head = NULL;

SLTPushBack(&head, 10);

SLTPushBack(&head, 20);

SLTPushBack(&head, 30);

// 链表: 10 → 20 → 30

// 找到值为20的节点

SLTNode* pos = SLTFind(head, 20);

// 在20后面插入25

SLTInsertAfter(pos, 25);

// 链表变为: 10 → 20 → 25 → 30 这个函数是单链表操作中最高效的插入方式，因为它不需要遍历链表查找前驱节点。在实际应用中，如果需要在某个节点后插入数据，应优先使用后插法而不是前插法。

（8）SLTErase( )函数（删除pos位置的节点） 画图分析如下：

对于本函数，我们同样需要处理删除头结点、删除中间结点两种情况，如下所示：

代码语言：javascript复制if (pos == *pphead)

{

SLTPopFront(pphead);

}

else {

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

//prev pos pos->next

prev->next = pos->next;

free(pos);

pos = NULL;

} 完整代码如下：

代码语言：javascript复制//删除pos结点

void SLTErase(SLTNode** pphead, SLTNode* pos)

{

assert(pphead && pos);

//pos刚好就是头结点——头删

if (pos == *pphead)

{

SLTPopFront(pphead);

}

else {

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

//prev pos pos->next

prev->next = pos->next;

free(pos);

pos = NULL;

}

} 使用示例如下：

代码语言：javascript复制SLTNode* head = NULL;

SLTPushBack(&head, 10);

SLTPushBack(&head, 20);

SLTPushBack(&head, 30);

// 链表: 10 → 20 → 30

// 找到值为20的节点

SLTNode* pos = SLTFind(head, 20);

// 删除20节点

SLTErase(&head, pos);

// 链表变为: 10 → 30 时间复杂度的最好情况：

O(1) - 在头节点前插入

最坏情况：

O(n) - 需要遍历找到前驱节点

平均情况：

O(n)（9）SLTEraseAfter( )函数（删除pos之后的结点） 画图分析如下：

对于本函数，我们首先要保存删除的结点，将pos的下一个结点保存到临时变量 del 中。这个结点就是要被我们删除的结点。

代码语言：javascript复制SLTNode* del = pos->next; 然后我们需要跳过要删除的结点，将pos的next指针指向del的下一个结点，并释放内存：

代码语言：javascript复制pos->next = del->next;

free(del);

del = NULL; 完整代码如下：

代码语言：javascript复制//删除pos之后的结点

void SLTEraseAfter(SLTNode* pos)

{

assert(pos && pos->next);

//pos del del->next

SLTNode* del = pos->next;

pos->next = del->next;

free(del);

del = NULL;

} 使用示例：

代码语言：javascript复制SLTNode* head = NULL;

SLTPushBack(&head, 10);

SLTPushBack(&head, 20);

SLTPushBack(&head, 30);

SLTPushBack(&head, 40);

// 链表: 10 → 20 → 30 → 40

// 找到值为20的节点

SLTNode* pos = SLTFind(head, 20);

// 删除20后面的节点（30）

SLTEraseAfter(pos);

// 链表变为: 10 → 20 → 40 时间复杂度为

O(1)。

（10）SListDestroy( )函数（销毁链表） 画图分析如下：

销毁链表函数的关键在于遍历并释放所有节点。在释放当前结点之前，需要先保存下一个结点的指针，然后再用free（）释放当前结点的内存。接着将pcur指向之前保存的下一个结点，循环继续直到pcur为NULL时停止，表示此时遍历到了链表末尾。如下所示：

代码语言：javascript复制while (pcur)

{

SLTNode* next = pcur->next;

free(pcur);

pcur = next;

} 完整代码如下：

代码语言：javascript复制//销毁链表

void SListDestroy(SLTNode** pphead)

{

assert(pphead);

SLTNode* pcur = *pphead;

while (pcur)

{

SLTNode* next = pcur->next;

free(pcur);

pcur = next;

}

*pphead = NULL;

} 使用示例如下：

代码语言：javascript复制SLTNode* head = NULL;

SLTPushBack(&head, 10);

SLTPushBack(&head, 20);

SLTPushBack(&head, 30);

// 链表: 10 → 20 → 30

// 销毁整个链表

SListDestroy(&head);

// head 现在为 NULL，所有内存已释放 时间复杂度为

O(n) - 需要遍历链表中的每个节点。

二、链表的分类 链表的结构其实不止单链表这一种，以下情况组合起来就有8种（2 * 2 * 2）链表结构：

下面给大家看看各种链表的示意图：

虽然有这么多的链表结构，但是我们在实际中最常用的其实只有两种结构：单链表和双向带头循环链表。

1. 无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多则是作为其他

数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用于单独存储数据。实际中使用的链表数据结构大

都是带头双向循环链表。另外这个结构虽然复杂，但是使用代码实现以后会发现这种结构具

有很多优势，实现反而会更简单，后面我们代码实现了大家就知道了。

总结 本期博客为大家介绍了单链表结构的实现，下期博客将给大家讲解一些单链表的算法题，请大家多多支持！