跳到主要内容单链表核心操作实现与详解 | 极客日志C算法
单链表核心操作实现与详解
单链表作为基础线性表，详细讲解其查找、指定位置前后插入及删除等核心操作的实现原理。通过遍历指针移动完成节点定位，分析头插尾插的特殊情况处理。代码部分提供完整的 SList.h 和 SList.c 接口定义与实现，包含内存申请释放逻辑。对比顺序表与链表在存储结构、访问效率及空间利用率上的区别，帮助读者深入理解指针操作与链表结构，夯实数据结构基础。
MongoKing1 浏览 
前言
单链表是数据结构中最基础也最核心的线性表之一，熟练掌握其查找、指定位置插入与删除等操作，是深入学习算法与数据结构的关键一步。本文将从零实现单链表的常用接口，详细拆解每一步思路与代码细节，帮助大家真正理解指针操作与链表结构，夯实编程基础。
一、查找
思路： 遍历：pcur 指向头结点，循环，当 pcur 不为空进入循环，pcur 里面指向的数据为要查找的值的时候就返回 pcur，否则将 pcur 下一个结点的地址赋值给 pcur 然后继续判断，直到找到值。如果为空直接返回。
代码：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
SLTNode* pcur = phead;
while (pcur) {
if (pcur->data == x)
return pcur;
pcur = pcur->next;
}
return NULL;
}
测试：
void test1() {
SLTNode* head = NULL;
SLTPushFront(&head, 1);
SLTPushFront(&head, 2);
SLTPushFront(&head, 3);
SLTNode* find = SLTFind(head, 1);
if (find)
printf("找到了！\n");
else
printf("未找到\n");
}
运行结果：
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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
二、指定位置之前或之后插入元素
2.1 在指定位置之前
思路： 头文件不能为空，也不能在空之前插入结点，首先要找到 pos 位置的前一个结点让它的 next 指针指向 newnode，然后让 newnode 的 next 指针指向 pos。如何找到 pos 的前一个结点？那就是遍历，从头结点开始，向后遍历，直到 prev 的 next 指针指向 pos 则就是 pos 的前一个结点。这里要注意，当 pos 为头结点的时候，执行的操作就变为了头插。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead && pos);
if (pos == *pphead)
SLTPushFront(pphead, x);
else {
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
prev = prev->next;
newnode->next = pos;
prev->next = newnode;
}
}
void test1() {
SLTNode* head = NULL;
SLTPushBack(&head, 1);
SLTPushBack(&head, 2);
SLTPushBack(&head, 3);
SLTNode* find = SLTFind(head, 2);
if (find)
SLTInsert(&head, find, 7);
SLTPrint(head);
}
2.2 在指定位置之后
思路： 当 pos->next = newnode 后，newnode->next = pos->next 就变成了 newnode->next = newnode，因为仅仅根据 pos 就能够找到下一个结点，不需要遍历，所以只用传两个数据就可，而且当 pos 为尾结点时插入数据，这个代码也没问题，不需要像 pos 在头结点前插入时一样重新调用一下头插函数。
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead && pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void test1() {
SLTNode* head = NULL;
SLTPushBack(&head, 1);
SLTPushBack(&head, 2);
SLTPushBack(&head, 3);
SLTNode* find = SLTFind(head, 2);
if (find)
SLTInsertAfter(&head, find, 7);
SLTPrint(head);
}
三、指定位置删除或指定位置之后删除
3.1 在指定位置
思路： 这里还是通过遍历找到 prev 就是 pos 的前一个结点，然后让 prev->next = pos->next，然后释放掉需要删除的那个结点。当 pos 为头结点的时候，通过遍历 prev->next 并不能找不到 pos，所以此时需要进行头删操作的引用。
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead && 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 test1() {
SLTNode* head = NULL;
SLTPushBack(&head, 1);
SLTPushBack(&head, 2);
SLTPushBack(&head, 3);
SLTNode* find = SLTFind(head, 2);
if (find)
SLTErase(&head, find);
SLTPrint(head);
}
3.2 指定位置之后
思路： 但是当 pos 为尾结点的时候，pos->next 为 NULL，所以 del->next 是对空指针解引用就会报错，所以在 assert 里面再加入一个条件 assert(pos && pos->next)。
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos) {
assert(pphead && pos);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void test1() {
SLTNode* head = NULL;
SLTPushBack(&head, 1);
SLTPushBack(&head, 2);
SLTPushBack(&head, 3);
SLTNode* find = SLTFind(head, 2);
if (find)
SLTEraseAfter(&head, find);
SLTPrint(head);
}
四、代码展现
4.1 SList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SLTNode {
SLTDataType data;
struct SLTNode* next;
} SLTNode;
void SLTPrint(SLTNode* phead);
void SLTDestory(SLTNode** pphead);
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);
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
4.2 SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur) {
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x) {
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL) {
printf("开辟失败！\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTDestory(SLTNode** pphead) {
SLTNode* pcur = *pphead;
while (pcur) {
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
*pphead = newnode;
else {
SLTNode* pcur = *pphead;
while (pcur->next != NULL)
pcur = pcur->next;
pcur->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead) {
assert(pphead && *pphead);
if ((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
} else {
SLTNode* prev = NULL;
SLTNode* pcur = *pphead;
while (pcur->next != NULL) {
prev = pcur;
pcur = pcur->next;
}
free(pcur);
pcur = NULL;
prev->next = NULL;
}
}
void SLTPopFront(SLTNode** pphead) {
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
SLTNode* pcur = phead;
while (pcur) {
if (pcur->data == x)
return pcur;
pcur = pcur->next;
}
return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead && pos);
if (pos == *pphead)
SLTPushFront(pphead, x);
else {
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
prev = prev->next;
newnode->next = pos;
prev->next = newnode;
}
}
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead && pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead && 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** pphead, SLTNode* pos) {
assert(pphead && pos);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
4.3 test.c
#include "SList.h"
void test1() {
SLTNode* head = NULL;
SLTPushBack(&head, 1);
SLTPushBack(&head, 2);
SLTPushBack(&head, 3);
SLTNode* find = SLTFind(head, 2);
if (find)
SLTEraseAfter(&head, find);
SLTPrint(head);
}
int main() {
test1();
return 0;
}
五、顺序表和链表的区别
