前言
单链表是数据结构中最基础也最核心的线性表之一，熟练掌握其查找、指定位置插入与删除等操作，是深入学习算法与数据结构的关键一步。本文将从零实现单链表的常用接口，详细拆解每一步思路与代码细节，帮助大家真正理解指针操作与链表结构，夯实编程基础。
一、查找
思路
遍历：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)
二、指定位置之前或之后插入元素
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;
}
}
时间复杂度
O(n)（需遍历寻找前驱）
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;
}
时间复杂度
O(1)
三、指定位置删除或指定位置之后删除
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;
}
}
时间复杂度
O(n)
3.2 指定位置之后
思路
但是当 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)
四、代码展现
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 && pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
4.3 test.c
#include "SList.h"
int main() {
test1();
return 0;
}
五、顺序表和链表的区别
| 特性 | 顺序表 | 链表 |
|---|---|---|
| 内存分配 | 静态/连续 | 动态/离散 |
| 访问效率 | O(1) 随机访问 | O(n) 顺序访问 |
| 插入删除 | 需移动元素 O(n) | 修改指针 O(1) |
| 空间利用率 | 可能浪费 | 按需分配 |
注：缓存利用率参考存储体系结构以及局部性原理。
总结
数据结构的学习没有捷径，每一个指针、每一次遍历、每一段接口实现，都是夯实功底的必经之路。保持耐心，多写多练多思考，把基础打牢，复杂的算法与项目自然水到渠成。
