文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >数据结构（C语言篇）：（四）链表

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

作者头像
_OP_CHEN
发布于 2026-01-14 09:30:15
发布于 2026-01-14 09:30:15
1300
举报
文章被收录于专栏：C++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(1)

；

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

O(n)
O(n)

；

平均情况的时间复杂度为

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)
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(1)

；

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

O(n)
O(n)

；

平均情况为

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)
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(1)

；

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

O(n)
O(n)

；

平均情况为

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(1)

- 在头节点前插入

最坏情况：

O(n)
O(n)

- 需要遍历找到前驱节点

平均情况：

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(1)

- 在头节点前插入

最坏情况：

O(n)
O(n)

- 需要遍历找到前驱节点

平均情况：

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)
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)
O(n)

- 需要遍历链表中的每个节点。

二、链表的分类

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

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

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

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

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

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

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

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

总结

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

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除
链表
数据
指针
数据结构
函数

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

链表
数据
指针
数据结构
函数
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 前言
  • 一、单链表
    • 1.1 概念与结构
      • 1.1.1 结点
      • 1.1.2 链表的性质
      • 1.1.3 链表的打印
    • 1.2 单链表的实现
      • 1.2.1 头文件的准备
      • 1.2.2 函数的实现
  • 二、链表的分类
  • 总结
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论