跳到主要内容数据结构：链表基础与实现 | 极客日志C算法
数据结构：链表基础与实现
本文讲解链表的数据结构，涵盖概念、特点及分类。详细介绍单链表与双链表的定义、初始化及增删查改操作，提供 C 语言代码实现。对比顺序表与链表差异，适用于频繁插入删除场景。
人间失格1 浏览 链表基础知识
链表的概念
链表是一种常见的数据结构，用于线性方式存储数据。链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
基本特点
- 动态大小：链表的大小可以在运行时动态变化，不需要在创建时指定固定的大小。
- 元素连接：每个元素（通常称为节点）存储数据，并包含一个或多个指针指向列表中的其他节点。
- 无需连续内存：由于元素通过指针连接，它们不需要在内存中连续存放，这使得内存使用更加灵活。
- 插入和删除操作：在链表中插入或删除节点通常比数组更快，因为这些操作不需要移动其他元素。
分类
- 单向与非单向
- 带头与非带头（有没有哨兵节点）
哨兵节点就是一个存储非有效数据的虚拟节点，他不是数据结合的一部分，可以简化删除操作，避免空链表，统一处理逻辑。
- 循环与非循环
常见的链表就有不带头单向非循环链表和带头双向循环链表。
基本操作（接口）
- 插入：在链表的特定位置添加新节点。
- 删除：移除链表中的特定节点。
- 搜索：查找链表中的特定值。
- 遍历：按顺序访问链表的所有节点。
所以总的来说，链表适用于当数据结合频繁变化，需要快速插入和删除，内存空间分散的场景。
单链表的实现
单链表也就是不带头单向非循环链表。
定义
typedef int SLTDataType;
typedef struct {
SLTDataType data;
}SLTNode;
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
- HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
SListNode
struct SListNode* next;
创建新节点
SLTNode* SLTCreateNode(SLTDataType x) {
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL) {
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
增、删、查、改操作
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTCreateNode(x);
if (*pphead == NULL) {
*pphead = newnode;
} else {
SLTNode* ptail = *pphead;
while (ptail->next) {
ptail = ptail->next;
}
ptail->next = newnode;
}
}
细节：因为涉及到 phead 指针的修改，所以参数得传二级指针。（*pphead == phead）
找到尾节点需要判断当前节点的下一节点是否为空。（ptail->next）
- 不要忘记链表为空的情况。
- 传 phead 的二级指针。
- 找尾节点。
头插非常简单，创建新节点，然后链接在链表头部就行。
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTCreateNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
要注意判断只有一个节点的情况和判断链表为空的情况（assert(pphead && *pphead)）。
void SLTPopBack(SLTNode** pphead) {
assert(pphead && *pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
} else {
SLTNode* ptail = *pphead;
SLTNode* prev = *pphead;
while (ptail->next) {
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
删除头节点前要把下一个节点存储起来，还是要注意判断链表为空的情况。
void SLTPopFront(SLTNode** pphead) {
assert(pphead && *pphead);
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}
- 注意判断空链表，不能再空节点前插入。
- pos 不能为空。
- pos 是头节点的情况。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead && *pphead);
assert(pos);
if (*pphead == pos) {
SLTPushFront(pphead, x);
} else {
SLTNode* newnode = SLTCreateNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTCreateNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
SLTNode* SLTfind(SLTNode* phead, SLTDataType x) {
SLTNode* pcur = phead;
while (pcur) {
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
找到 pos 的下一个节点，pos 的前一个节点，更改指针，free 掉 pos 节点就行了。
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead && *pphead);
assert(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* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
遍历链表就行，把要删除的节点提前存起来就行，注意判断链表为空的情况。
void SLTDestroy(SLTNode** pphead) {
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur) {
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
双链表的实现
定义
typedef int LTDataType;
typedef struct ListNode {
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
初始化（创造哨兵节点）
LTNode* CreateNode(LTDataType x) {
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL) {
perror("malloc fail!");
exit(1);
}
node->data = x;
node->next = node->prev = node;
return node;
}
void LTinit(LTNode** pphead) {
*pphead = CreateNode(-1);
}
增、删、查、改操作
void LTPushBack(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = CreateNode(x);
LTNode* ptail = phead->prev;
newnode->prev = ptail;
newnode->next = phead;
ptail->next = newnode;
phead->prev = newnode;
}
细节：这里的 phead 不用传二级指针，因为不涉及 phead 的改变，包括接下来的头插也是。
头插指的是插入到第一个有效节点的前面，也就是哨兵位节点的后面。
void LTPushFront(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = CreateNode(x);
newnode->prev = phead;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
}
删除有效节点的最后一个节点，注意判断链表为空的情况（没有有效节点，只有哨兵位）。
void LTPopBack(LTNode* phead) {
assert(phead && phead->next != phead);
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
删除有效节点的第一个节点，注意判断链表为空的情况。
void LTPopFront(LTNode* phead) {
assert(phead && phead->next != phead);
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = NULL;
}
void LTInsert(LTNode* pos, LTDataType x) {
assert(pos);
LTNode* newnode = CreateNode(x);
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next = newnode;
}
LTNode* LTFind(LTNode* phead, LTDataType x) {
assert(phead && phead->next != phead);
LTNode* pcur = phead->next;
while (pcur != phead) {
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void LTErase(LTNode* pos) {
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
void LTDestroy(LTNode* phead) {
LTNode* pcur = phead->next;
while (pcur != phead) {
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
顺序表和链表的区别
