跳到主要内容数据结构:链表基础与实现 | 极客日志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;
}
顺序表和链表的区别