【数据结构】链表核心解密：动态内存的艺术与高效增删的终极指南

链表核心解密：动态内存的艺术与高效增删的终极指南

✨前言：在顺序表的探索中，我们领略了连续内存空间的高效访问之美。然而当顺序表在内存中整齐列队时，一种以动态链接为灵魂的结构正悄然绽放光芒——链表，链表作为基础且重要的线性结构，以其动态内存管理和灵活插入删除的特性脱颖而出。本文将深入剖析链表的核心概念，手把手实现单链表的各种操作（增删查改），并对比链表与顺序表结构的区别。无论你是算法初学者还是需要巩固基础的开发者，本文都能助你彻底攻克链表这一重要数据结构！
📖专栏：【数据结构】

目录

• 链表核心解密：动态内存的艺术与高效增删的终极指南
  • 一、链表的概念及结构
  • 二、实现单链表（Singly Linked List）
    • 1. 类型定义
    • 2. 节点结构定义
    • 3. 打印链表
    • 4. 创建新节点
    • 5. 头部插入
    • 6. 头部删除
    • 7. 尾部插入
    • 8. 头部删除
    • 9. 尾部删除
    • 10. 查找节点
    • 11. 在指定位置前插入
    • 12. 删除指定节点
    • 13. 在指定位置后插入
    • 14. 删除指定位置后的节点
    • 15. 销毁链表
  • 三、链表的分类
  • 四、链表与顺序表对比
  • 五、总结：

一、链表的概念及结构

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

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。且每节车厢都有车门。
车厢是独立存在的。且每节车厢都有车门。想象⼀下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从车头走到车尾？
最简单的做法：每节车厢里都放⼀把下一节车厢的钥匙。
在链表里，每节“车厢”是什么样的呢？

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”。
节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。
图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。
那为什么还需要指针变量来保存下⼀个节点的位置？
链表中每个节点都是独立申请的（即需要插入数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

此时，我们就可以结合的结构体知识，给出每个节点对应的结构体代码：
假设当前保存的节点为整型：

structSListNode{int data;//节点数据 structSListNode* next;//指针变量用来保存下⼀个节点的地址 };

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当下一个节点为空时保存的地址为空）。
当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上下一个节点的地址（下一个节点的钥匙）就可以了。

在基于上面的想法，如何在给定的链表结构中，如何实现节点从头到尾的打印？

如果当我们想保存的数据类型为字符型、浮点型或者其他自定义的类型时，该如何修改？
此时我们只需要：

typedefint SLTDataType;//

方便未来修改——如果以后想改用其他类型（如 float 或 long等等），只需修改这一行代码即可，而不需要到处改。
在这里还要补充说明几点：

1、链式机构在逻辑上是连续的，在物理结构上不一定连续；
2、节点一般是从堆上申请的；
3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。

二、实现单链表（Singly Linked List）

这段代码实现了一个完整的单链表数据结构，包含了各种基本操作。下面我将逐块解释每个函数的功能和实现细节。

1. 类型定义

typedefint SLTDataType;// 定义链表节点存储的数据类型为int

这里使用typedef定义了链表存储的数据类型，方便以后修改数据类型时只需改动这一处。

2. 节点结构定义

typedefstructSLListNode{ SLTDataType data;// 节点存储的数据structSLListNode* next;// 指向下一个节点的指针} SLTNode;

定义链表节点的结构，包含数据域和指向下一个节点的指针。

3. 打印链表

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

功能：遍历并打印整个链表的内容，最后输出NULL表示链表结束。

4. 创建新节点

SLTNode*SLTBuyNode(SLTDataType x){ SLTNode* pret =(SLTNode*)malloc(sizeof(SLTNode));if(!pret){perror("malloc fail");exit(1);} pret->data = x; pret->next =NULL;return pret;}

功能：动态分配内存创建一个新节点，初始化数据并返回节点指针。

5. 头部插入

voidSLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead); SLTNode* pret =SLTBuyNode(x); pret->next =*pphead;*pphead = pret;}

功能：在链表头部插入一个新节点。需要注意参数是二级指针，因为需要修改头指针本身。

6. 头部删除

voidSLTPopFront(SLTNode** pphead){assert(pphead &&*pphead); SLTNode* pcur =*pphead;*pphead =(*pphead)->next;free(pcur); pcur =NULL;}

功能：删除链表头部的节点，并释放内存。

7. 尾部插入

voidSLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);if(*pphead ==NULL){SLTPushFront(pphead, x);}else{ SLTNode* pret =SLTBuyNode(x); SLTNode* pcur =*pphead;while(pcur->next){ pcur = pcur->next;} pcur->next = pret; pret =NULL;}}

功能：在链表尾部插入一个新节点。如果链表为空，直接调用头部插入函数。

8. 头部删除

void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);

SLTNode* pcur = *pphead; *pphead = (*pphead)->next; free(pcur); pcur = NULL; 

}

9. 尾部删除

voidSLTPopBack(SLTNode** pphead){assert(pphead &&*pphead);if((*pphead)->next ==NULL){free(*pphead);*pphead =NULL;}else{ SLTNode* pcur =*pphead; SLTNode* prev =*pphead;while(pcur->next){ prev = pcur; pcur = pcur->next;}free(pcur); pcur =NULL; prev->next =NULL;}}

功能：删除链表尾部的节点，需要考虑链表只有一个节点或多个节点的情况。

10. 查找节点

SLTNode*SLTFind(SLTNode* phead, SLTDataType x){assert(phead); SLTNode* pcur = phead;while(pcur){if(pcur->data == x)return pcur; pcur = pcur->next;}returnNULL;}

功能：查找链表中第一个数据等于x的节点，返回其指针，找不到则返回NULL。

11. 在指定位置前插入

voidSLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead &&*pphead);assert(pos);if(*pphead == pos){SLTPushFront(pphead, x);}else{ SLTNode* new =SLTBuyNode(x); SLTNode* pcur =*pphead; SLTNode* prev =*pphead;while(pcur != pos){ prev = pcur; pcur = pcur->next;} new->next = prev->next; prev->next = new;}}

功能：在指定节点pos之前插入一个新节点。如果pos是头节点，直接调用头部插入函数。

12. 删除指定节点

voidSLTErase(SLTNode** pphead, SLTNode* pos){assert(*pphead && pphead);assert(pos);if(*pphead == pos){SLTPopFront(pphead);}else{ SLTNode* pcur =*pphead; SLTNode* prev =*pphead;while(pcur != pos){ prev = pcur; pcur = pcur->next;}if(pcur->next){ prev->next = pcur->next;free(pcur); pcur =NULL;}else{SLTPopBack(pphead);}}}

功能：删除指定的节点pos。需要考虑pos是头节点、中间节点或尾节点的情况。

13. 在指定位置后插入

voidSLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos); SLTNode* new =SLTBuyNode(x); SLTNode* pret = pos->next; pos->next = new; new->next = pret;}

功能：在指定节点pos之后插入一个新节点。比在pos前插入更简单，因为不需要遍历找前驱节点。

14. 删除指定位置后的节点

voidSLTEraseAfter(SLTNode* pos){assert(pos && pos->next); SLTNode* del = pos->next; pos->next = del->next;free(del); del =NULL;}

功能：删除指定节点pos的下一个节点。比删除pos本身更简单。

15. 销毁链表

voidSListDesTroy(SLTNode** pphead){assert(pphead &&*pphead); SLTNode* pcur =*pphead; SLTNode* next = pcur;while(pcur){ next = next->next;free(pcur); pcur = next;} pcur =NULL;*pphead =NULL;}

功能：销毁整个链表，释放所有节点的内存，并将头指针置为NULL。

三、链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2x2x2）链表结构：
在这里插入图片描述

更详细的说明：

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表
1.不带头单向非循环链表（单链表）：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.双向带头循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。对于双向链表的代码实现较为简单，我们这里就不展开说明了。

四、链表与顺序表对比

五、总结：

“链表的本质是用空间换时间的艺术”

• 牺牲 随机访问速度 换取 动态扩展能力
• 牺牲 内存连续性 换取 操作灵活性
• 用 指针链接 替代 物理连续 实现逻辑有序
  当需求聚焦 高效增删 且 数据规模动态变化 时，链表是比顺序表更优的选择！

如果本文对您有启发：
✅ 点赞 -让更多人看到这篇硬核技术解析 ！
✅ 收藏 -实战代码随时复现
✅ 关注 -获取数据结构系列深度更新
您的每一个[三连]都是我们持续创作的动力！✨