欢迎光临
我们一直在努力

从顺序表到链表:手撕无头单向不循环链表

从顺序表到链表:手撕无头单向不循环链表

上一篇文章我们实现了一个泛型顺序表,支持动态扩容、任意类型存储,看起来已经相当能打。但实际使用中,顺序表有一个无法回避的痛点:插入和删除需要大量搬移数据。

在头部插入一个元素,要把所有已有元素整体往后挪一位——数据量上万时,这个开销非常可观。

于是有了链表:元素在内存中不必连续存放,每个节点只记住下一个节点在哪,插入删除只需改几个指针,不用挪动任何数据。

核心对比:顺序表 vs 链表

特性顺序表链表
内存布局 连续 分散
随机访问 O(1) O(n)
插入/删除 O(n)(需挪动) O(1)(改指针即可)
扩容 需要重新分配 不需要,随用随取

本文手撕一个最基础的链表形式——无头单向不循环链表。没有哑结点,没有循环,一个头指针直通整个链表。理解了它,后面双向链表、循环链表就是加几根指针的事。


2. 结构定义:一个节点长什么样

2.1 节点结构体

链表由一个个“节点”串联而成,每个节点包含两样东西:自己的数据和指向下一个节点的指针。

typedef struct SingleListNode {
DataType data; // 数据域:存放节点的值
struct SingleListNode* next; // 指针域:指向下一个节点(NULL 表示末尾)
} SingleListNode;

next 的类型是 struct SingleListNode*——指向和自己同类型的结构体。这种“自己指向自己”的设计,就是链表能在内存中串联起来的核心。

2.2 链表管理结构体

光有节点不够,还需要一个结构体来管理整条链表。这个结构体记录三个关键信息:

typedef struct SingleList {
SingleListNode* head; // 指向第一个节点(头节点)
SingleListNode* tail; // 指向最后一个节点(尾节点)
size_t count; // 当前节点总数
} SingleList;

为什么要同时维护 head 和 tail?

成员作用如果没有它…
head 头节点指针,遍历链表的起点 根本找不到链表在哪
tail 尾节点指针,直接定位最后一个节点 尾插时要遍历整条链表,O(n)
count 节点计数器 想知道有几个元素又得遍历一遍,O(n)

设计决策:tail 是设计上的关键决策:它让尾插操作从 O(n) 降到 O(1)。代价只是每次插入和删除时多维护一个指针,但这个代价很小,收益巨大。

2.3 完整头文件

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define LOG(fmt, ...) \\
printf("[%s:%d] " fmt "\\n", __FILE__, __LINE__, ##__VA_ARGS__)

typedef int DataType;

typedef enum ErrorCode {
SUCCESS = 0,
ERR_MALLOC = 1,
ERR_INVALID_PARAM = 2,
ERR_INVALID_OPERATOR,
ERR_DATA_NOT_EXISTS
} ErrorCode;

typedef void (*ShowListElementType)(void* val);

typedef struct SingleListNode {
DataType data;
struct SingleListNode* next;
} SingleListNode;

typedef struct SingleList {
SingleListNode* head;
SingleListNode* tail;
size_t count;
} SingleList;

// 接口声明
extern ErrorCode SingleLinkListInit(SingleList* plist);
extern ErrorCode SingleLinkListPushFront(SingleList* plist, DataType val);
extern ErrorCode SingleLinkListPushBack(SingleList* plist, DataType val);
extern void SingleLinkListPrint(SingleList* plist, ShowListElementType show);
extern SingleListNode* SingleLinkListFind(SingleList* plist, DataType val);
extern SingleListNode* SingleLinkListFindBefore(SingleList* plist, DataType val);
extern ErrorCode SingleLinkListInsertAfter(SingleList* plist, SingleListNode* pos, DataType val);
extern ErrorCode SingleLinkListInsertBefore(SingleList* plist, SingleListNode* pos, DataType val);
extern ErrorCode SingleLinkListRemove(SingleList* plist, DataType val);
extern ErrorCode SingleLinkListRemoveAll(SingleList* plist, DataType val);
extern ErrorCode SingleLinkListFront(SingleList* plist, DataType* val);
extern ErrorCode SingleLinkListBack(SingleList* plist, DataType* val);
extern void SingleLinkListDestroy(SingleList* plist);

#endif

头文件设计要点:

  • LOG 宏:__FILE__ + __LINE__ 自动带文件名和行号,调试时不用猜位置。
  • ErrorCode 枚举:不用魔法数字,返回值语义明确。
  • ShowListElementType 函数指针:打印回调,换类型只换回调,延续泛型设计思路。
  • 操作分层:InsertAfter / InsertBefore 是基础操作,头插尾插可以直接基于它们实现(本文用独立函数实现,两种设计各有优劣)。

3. 地基:初始化、创建节点与销毁

3.1 初始化

ErrorCode SingleLinkListInit(SingleList* plist) {
if (plist == NULL) {
LOG("初始化链表为空");
return ERR_INVALID_PARAM;
}
plist->head = plist->tail = NULL;
plist->count = 0;
return SUCCESS;
}

初始状态:链表为空,头尾指针都指向 NULL,计数器归零。plist->head = plist->tail = NULL 一行代码同时初始化两个指针,简洁且不会出现只置空一个的低级错误。

3.2 创建新节点(内部函数)

static SingleListNode* NewNode(DataType val) {
SingleListNode* Node = (SingleListNode*)malloc(sizeof(SingleListNode));
if (Node == NULL) {
return NULL;
}
Node->data = val;
Node->next = NULL;
return Node;
}

static 关键字将函数作用域限制在当前 .c 文件,外部调用者不需要知道节点是怎么创建的——封装思想在 C 语言中的体现。

3.3 销毁链表

void SingleLinkListDestroy(SingleList* plist) {
if (plist == NULL) {
LOG("链表指针为空");
return;
}
while (plist->head) {
SingleListNode* node = plist->head->next; // 先保存下一站地址
free(plist->head); // 再释放当前节点
plist->head = node; // 最后让 head 指向下一站
}
plist->head = NULL;
plist->tail = NULL;
plist->count = 0;
}

销毁前为什么要先保存 head->next?
free(plist->head) 之后,plist->head 指向的内存已被回收,此时再通过 plist->head->next 访问下一个节点就是悬空指针——未定义行为。所以必须先用临时变量 node 保存下一站的地址,再释放当前节点,最后让 head 指向 node 继续循环。


4. 插入操作:链表的灵魂

4.1 头插

ErrorCode SingleLinkListPushFront(SingleList* plist, DataType val) {
if (plist == NULL) {
LOG("头插链表为空");
return ERR_INVALID_PARAM;
}
SingleListNode* node = NewNode(val);
if (node == NULL) {
LOG("申请节点失败");
return ERR_MALLOC;
}
// 空链表:新节点既是头也是尾
if (plist->head == NULL) {
assert(plist->tail == NULL);
plist->count++;
plist->head = node;
plist->tail = node;
return SUCCESS;
}
// 非空链表:新节点插在头部
node->next = plist->head;
plist->head = node;
plist->count++;
return SUCCESS;
}

为什么用 assert 检查 tail?
当 head == NULL(链表为空)时,tail 必然也是 NULL。assert(plist->tail == NULL) 不是给用户看的,而是给自己的——如果程序跑到这里 tail 不为空,说明链表的一致性被破坏,assert 会立刻终止程序并报出错误位置,帮你快速定位 bug。这是一种“早崩溃、早发现”的防御性编程策略。

4.2 尾插

ErrorCode SingleLinkListPushBack(SingleList* plist, DataType val) {
if (plist == NULL) {
LOG("尾插链表为空");
return ERR_INVALID_PARAM;
}
SingleListNode* node = NewNode(val);
if (node == NULL) {
LOG("申请节点失败");
return ERR_MALLOC;
}
if (plist->head == NULL) {
assert(plist->tail == NULL);
plist->count++;
plist->head = node;
plist->tail = node;
return SUCCESS;
}
// 非空链表:挂在尾节点后面,更新 tail
plist->tail->next = node;
plist->tail = node;
plist->count++;
return SUCCESS;
}

尾插和头插的代码结构几乎一样,区别在于:头插修改 head,尾插修改 tail。因为维护了 tail 指针,尾插不用从头遍历,时间复杂度 O(1)。

4.3 指定位置后面插入

ErrorCode SingleLinkListInsertAfter(SingleList* plist, SingleListNode* pos, DataType val) {
if (plist == NULL || pos == NULL) {
LOG("链表查找为空");
return ERR_INVALID_PARAM;
}
SingleListNode* node = NewNode(val);
if (node == NULL) {
LOG("申请节点失败");
return ERR_MALLOC;
}
node->next = pos->next;
pos->next = node;
plist->count++;
// 如果 pos 恰好是尾节点,更新 tail
if (pos == plist->tail) {
plist->tail = node;
}
return SUCCESS;
}

为什么还需要更新 tail?
如果 pos 刚好是尾节点,在其后面插入新节点后,新节点就成了新的尾节点,tail 必须跟着更新。这个判断很容易漏,漏了之后后续的尾插操作会出错。

4.4 指定位置前面插入

指定位置前面插入是单向链表里最麻烦的操作——因为单向链表只能往后找,不能往前找。要找到 pos 的前一个节点,必须从 head 开始遍历。

ErrorCode SingleLinkListInsertBefore(SingleList* plist, SingleListNode* pos, DataType val) {
if (plist == NULL || pos == NULL) {
LOG("链表查找为空或者插入位置无效");
return ERR_INVALID_PARAM;
}
SingleListNode* node = NewNode(val);
if (node == NULL) {
LOG("申请节点失败");
return ERR_MALLOC;
}
// 情况一:pos 是头节点 → 等同于头插
if (plist->head == pos) {
node->next = plist->head;
plist->head = node;
plist->count++;
return SUCCESS;
}
// 情况二:pos 不是头节点 → 找到 pos 的前驱
SingleListNode* before = plist->head;
while (before != NULL && before->next != pos) {
before = before->next;
}
if (before == NULL) {
LOG("指定节点不在链表内");
free(node);
return ERR_INVALID_PARAM;
}
node->next = pos;
before->next = node;
plist->count++;
return SUCCESS;
}

  • 为什么分了两种情况? pos 是头节点时,pos 没有前驱节点,无法走“找到前驱再插入”的通用逻辑,需要单独处理——这种情况直接降级为头插。
  • 为什么 before == NULL 要释放 node? 走到这一步意味着 pos 不在当前链表里——before 遍历完所有节点都没找到 pos。此时 node 已经通过 malloc 分配好了,如果不释放,这个 node 就永远丢失了。所以在返回错误之前必须 free(node),防止内存泄漏。

5. 删除操作:链表的真正优势

5.1 按值删除(双指针法)

删除指定值的节点,用双指针法——prev 是前驱指针,cur 是当前指针,两个指针同步后移。

ErrorCode SingleLinkListRemove(SingleList* plist, DataType val) {
if (plist == NULL) {
LOG("链表指针为空");
return ERR_INVALID_PARAM;
}
if (plist->head == NULL) {
LOG("链表为空,没有数据可以删除");
return ERR_DATA_NOT_EXISTS;
}
SingleListNode* prev = NULL;
SingleListNode* cur = plist->head;
// 遍历:找值为 val 的节点
while (cur != NULL && cur->data != val) {
prev = cur;
cur = cur->next;
}
if (cur == NULL) {
LOG("未找到指定数据");
return ERR_DATA_NOT_EXISTS;
}
// 情况一:cur 是头节点
if (prev == NULL) {
plist->head = cur->next;
if (plist->head == NULL) {
plist->tail = NULL;
}
}
// 情况二:cur 是中间或尾节点
else {
prev->next = cur->next;
if (plist->tail == cur) {
plist->tail = prev;
}
}
free(cur);
plist->count—;
return SUCCESS;
}

  • 双指针法的本质:prev 始终指向 cur 的前一个节点。cur 找到目标时,prev 已经指向它的前驱,删除时只需让 prev->next 跳过 cur 直接指向 cur->next。
  • 为什么又要更新 tail? 如果 cur 刚好是尾节点,删除它之后链表少了一个节点,tail 必须指向前一个节点。如果删除的是头节点且链表只剩一个节点,删除后链表为空,head 和 tail 都要置 NULL。

5.2 删除所有指定值

ErrorCode SingleLinkListRemoveAll(SingleList* plist, DataType val) {
if (plist == NULL) {
LOG("链表指针为空");
return ERR_INVALID_PARAM;
}
if (plist->head == NULL) {
LOG("链表为空,没有数据可以删除");
return ERR_DATA_NOT_EXISTS;
}
SingleListNode* prev = NULL;
SingleListNode* cur = plist->head;
while (cur != NULL) {
if (cur->data == val) {
SingleListNode* toDelete = cur;
if (prev == NULL) {
plist->head = cur->next;
} else {
prev->next = cur->next;
}
cur = cur->next;
free(toDelete);
plist->count—;
continue; // ★ 跳过 prev 更新,因为 cur 已被删
}
prev = cur;
cur = cur->next;
}
plist->tail = prev; // 重置 tail 为最后一个不被删除的节点
return SUCCESS;
}

  • 和顺序表 RemoveAll 的对比:顺序表用双指针法保留了不被删除的元素,链表则是直接修改前驱节点的 next 指针绕过被删节点。两者核心思想相同——一趟遍历完成所有删除,时间复杂度 O(n)。
  • 这里的 continue 不能省:cur 指向的节点已经被释放,此时 cur 已经通过 cur = cur->next 指向了下一个节点。如果执行 prev = cur,prev 会指向当前 cur 的位置,但实际上前驱节点没变,所以跳过 prev 更新。
  • 最后为什么要重置 tail? 循环结束后,prev 指向最后一个没有被删除的节点,它可能就是新的尾节点(如果原尾节点被删除了)。直接赋给 tail 保证尾指针的正确性,即使尾节点没被删,prev 本来就指向它,赋值也没副作用。

6. 查找与获取

6.1 查找指定数据的节点

SingleListNode* SingleLinkListFind(SingleList* plist, DataType val) {
if (plist == NULL) {
LOG("链表为空");
return NULL;
}
SingleListNode* cur = plist->head;
while (cur != NULL) {
if (cur->data == val) {
return cur; // 找到,返回节点指针
}
cur = cur->next;
}
return NULL; // 没找到
}

返回的是节点指针而不是下标——因为链表不支持 O(1) 的下标访问。拿到节点指针后,可以直接用它做插入或删除操作,不需要再从头找一遍。

6.2 获取头部和尾部数据

ErrorCode SingleLinkListFront(SingleList* plist, DataType* val) {
if (plist == NULL || val == NULL) {
LOG("获取头部数据的参数错误");
return ERR_INVALID_PARAM;
}
if (plist->head == NULL) {
LOG("链表为空,没有数据");
return ERR_DATA_NOT_EXISTS;
}
memmove(val, &(plist->head->data), sizeof(DataType));
return SUCCESS;
}

ErrorCode SingleLinkListBack(SingleList* plist, DataType* val) {
if (plist == NULL || val == NULL) {
LOG("获取尾部数据的参数错误");
return ERR_INVALID_PARAM;
}
if (plist->head == NULL) {
LOG("链表为空,没有数据");
return ERR_DATA_NOT_EXISTS;
}
memmove(val, &(plist->tail->data), sizeof(DataType));
return SUCCESS;
}

获取头部和尾部分别用 head 和 tail 指针直接定位,时间复杂度都是 O(1)。用 memmove 而不是直接赋值,是为了兼容任意类型的 DataType(泛型化的预留接口)。


7. 打印链表

void SingleLinkListPrint(SingleList* plist, ShowListElementType show) {
if (plist == NULL) {
return;
}
SingleListNode* cur = plist->head;
while (cur != NULL) {
show(&cur->data);
cur = cur->next;
}
printf("\\n");
}

打印是链表的“遍历”操作——从 head 出发,沿着 next 一直走到 NULL。这和顺序表的 for (i = 0; i < size; i++) 遍历思路相同,但底层实现完全不同——顺序表靠偏移量跳跃,链表靠指针串联。


8. 设计决策速查

设计决策原因
维护 tail 指针 尾插不用遍历,O(n) → O(1)
维护 count 计数器 获取元素个数不用遍历,O(n) → O(1)
InsertAfter 更新 tail 在尾节点后插入时,新节点成为尾节点
删除时更新 tail 删除尾节点时,需要找到新尾节点
InsertBefore 分两种情况 头节点没有前驱,需特殊处理
NewNode 用 static 封装节点创建逻辑,外部不可见
销毁前保存 next free 后不能访问已释放内存
RemoveAll 中 continue 删除节点后 prev 不用更新,因为前驱没变
RemoveAll 后重置 tail 尾节点可能被删,需更新为最后一个保留节点
获取数据用 memmove 预留泛型兼容性,不依赖具体类型赋值

9. 学习体会

写链表和写顺序表的体验完全不同。顺序表难在扩容和内存管理,链表难在指针操作和边界条件。

链表最让我印象深刻的是尾指针的维护——InsertAfter、InsertBefore、Remove、RemoveAll,四个操作都要时刻关注 tail 是否正确。一个地方漏了,后续的尾插就会出错,而且这种 bug 往往不是当场暴露的,而是在不知多少次操作之后才出现。

另一个收获是双指针法在两种结构中的不同形态。顺序表里双指针是“读写指针”(一个读、一个写),链表里双指针是“前驱-当前指针”(一个指向前一个节点、一个指向当前节点)。叫法不同,核心思想一样:用两个变量的配合替代单个变量的反复回退,把重复扫描变成一趟遍历。

链表是数据结构里第一个大量依赖指针操作的结构,它逼着你把“指针指向谁、什么时候改、改之前要不要先保存”这些细节想清楚。这种对指针的敏感度,是学数据结构最重要的基本功。

赞(0)
未经允许不得转载:171主机测评 » 从顺序表到链表:手撕无头单向不循环链表
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址