C算法
单链表核心操作实现与指针思维解析
单链表作为线性表的核心结构，其查找、插入与删除操作是算法基础。本文基于 C 语言从零实现单链表常用接口，涵盖指定位置前后插入、指定位置删除等关键功能。内容包含完整代码示例、执行流程图解及时间复杂度分析，并对比了顺序表与链表的存储特性，旨在帮助开发者深入理解指针操作与内存管理，巩固数据结构知识。
单链表作为线性表的核心结构，其查找、插入与删除操作是算法基础。本文基于 C 语言从零实现单链表常用接口，涵盖指定位置前后插入、指定位置删除等关键功能。内容包含完整代码示例、执行流程图解及时间复杂度分析，并对比了顺序表与链表的存储特性，旨在帮助开发者深入理解指针操作与内存管理，巩固数据结构知识。
单链表是数据结构中最基础也最核心的线性表之一，熟练掌握其查找、指定位置插入与删除等操作，是深入学习算法与数据结构的关键一步。本文将从零实现单链表的常用接口，详细拆解每一步思路与代码细节，帮助大家真正理解指针操作与链表结构，夯实编程基础。
遍历：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");
}
O(n)
头文件不能为空，也不能在空之前插入结点，首先要找到 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;
}
}
O(n)（需遍历寻找前驱）
当 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;
}
O(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;
}
}
O(n)
但是当 pos 为尾结点的时候，pos->next 为 NULL，所以 del->next 是对空指针解引用就会报错，所以在 assert 里面再加入一个条件 assert(pos && pos->next)。
// 在指定位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos) {
assert(pphead && pos && pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
O(1)
#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);
;
;
#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;
}
}
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
{
assert(pphead && *pphead);
((*pphead)->next == ) {
(*pphead);
*pphead = ;
} {
SLTNode* prev = ;
SLTNode* pcur = *pphead;
(pcur->next != ) {
prev = pcur;
pcur = pcur->next;
}
(pcur);
pcur = ;
prev->next = ;
}
}
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
(*pphead);
*pphead = next;
}
SLTNode* {
SLTNode* pcur = phead;
(pcur) {
(pcur->data == x)
pcur;
pcur = pcur->next;
}
;
}
{
assert(pphead && pos);
(pos == *pphead)
SLTPushFront(pphead, x);
{
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
(prev->next != pos)
prev = prev->next;
newnode->next = pos;
prev->next = newnode;
}
}
{
assert(pphead && pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
{
assert(pphead && pos);
(pos == *pphead)
SLTPopFront(pphead);
{
SLTNode* prev = *pphead;
(prev->next != pos)
prev = prev->next;
prev->next = pos->next;
(pos);
pos = ;
}
}
{
assert(pphead && pos && pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
(del);
del = ;
}
#include "SList.h"
int main() {
test1();
return 0;
}
| 特性 | 顺序表 | 链表 |
|---|---|---|
| 内存分配 | 静态/连续 | 动态/离散 |
| 访问效率 | O(1) 随机访问 | O(n) 顺序访问 |
| 插入删除 | 需移动元素 O(n) | 修改指针 O(1) |
| 空间利用率 | 可能浪费 | 按需分配 |
注：缓存利用率参考存储体系结构以及局部性原理。
数据结构的学习没有捷径，每一个指针、每一次遍历、每一段接口实现，都是夯实功底的必经之路。保持耐心，多写多练多思考，把基础打牢，复杂的算法与项目自然水到渠成。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online