前言单链表只能单向走删除一个结点要先找到它的前驱循环链表让尾结点指回头结点适合环形语义静态链表则用数组下标代替指针在没有动态内存分配的环境里模拟链表。这三种结构都是单链表的变体但各自解决不同的问题。常见的误解有三个。第一以为双链表删除一定 O(1)——只有已经拿到待删结点的指针时才成立按值查找仍要 O(n)。第二用while (p ! NULL)遍历循环链表结果永远走不到空指针直接死循环。第三把静态链表当成数组忽略了它的核心是用next下标串起逻辑顺序物理顺序与逻辑顺序可以完全不同。本文用 C11 分别实现三种结构重点讲指针/下标的修改顺序、遍历的终止条件、以及各自的适用场景。所有示例只用标准库。一、双链表多一个prev换来双向能力双链表每个结点保存prev与next。好处是给定结点指针后插入与删除都是 O(1)不需要从头找前驱代价是每个结点多一个指针且每次修改要同时维护两个方向。用一个哨兵结点sentinel可以消掉空表删头插到末尾这些特判哨兵的next指向第一个元素prev指向最后一个元素空表时两者都指向自己。/* 适用于 C11 */#include stdio.h#include stdlib.htypedef struct DNode {int data;struct DNode* prev;struct DNode* next;} DNode;typedef struct {DNode* head; /* 哨兵不存业务数据 */} DList;int dlist_init(DList* l) {l-head (DNode*)malloc(sizeof(DNode));if (l-head NULL) return 0;l-head-data 0;l-head-prev l-head;l-head-next l-head;return 1;}void dlist_destroy(DList* l) {DNode* p l-head-next;while (p ! l-head) {DNode* next p-next;free(p);p next;}free(l-head);l-head NULL;}DNode* dlist_insert_after(DNode* pos, int value) {DNode* node (DNode*)malloc(sizeof(DNode));if (node NULL) return NULL;node-data value;node-next pos-next; /* 先接后继 */node-prev pos; /* 再接前驱 */pos-next-prev node; /* 后继回头指向新结点 */pos-next node; /* 前驱指向新结点 */return node;}void dlist_erase(DNode* node) {node-prev-next node-next;node-next-prev node-prev;free(node);}dlist_insert_after的四步顺序有讲究。前两步给新结点填好两个指针此时新结点还没接入链表第三步让原来的后继回头指向新结点第四步才让前驱指向新结点。如果先做第四步pos-next就被改成了新结点第三步再访问pos-next-prev时操作的是新结点自己原来的后继就丢了。删除同样要改两个方向让前驱跳过自己让后继回指前驱最后释放。只改一个方向会留下悬垂指针之后从另一侧遍历就会踩到已释放的内存。二、循环链表尾指回头循环单链表把尾结点的next指向头结点于是从任意结点出发都能走遍整个环。它的遍历不能用空指针作为终止条件要用回到起点/* 适用于 C11 */typedef struct CNode {int data;struct CNode* next;} CNode;void clist_print(const CNode* head) {if (head NULL) return;const CNode* p head;do {printf(%d , p-data);p p-next;} while (p ! head);}do-while是必须的如果写成while (p ! head)且先判断循环体一次都不会执行。空表要单独判断头指针是否为空。循环链表适合有轮转语义的场景约瑟夫环、轮询调度、播放列表循环。约瑟夫环的经典解法就是用循环链表模拟报数每数到第 m 个就删除该结点/* 适用于 C11 *//* 返回最后剩下的结点编号n 个人围成一圈每数到 m 出列 */int josephus(int n, int m) {if (n 0 || m 0) return -1;CNode* head NULL;CNode* tail NULL;for (int i 1; i n; i) {CNode* node (CNode*)malloc(sizeof(CNode));if (node NULL) return -1;node-data i;node-next NULL;if (head NULL) {head node;tail node;} else {tail-next node;tail node;}}tail-next head; /* 首尾相连 */CNode* prev tail;CNode* cur head;while (cur-next ! cur) { /* 只剩一个结点时结束 */for (int i 1; i m; i) { /* 报数 m-1 次 */prev cur;cur cur-next;}prev-next cur-next; /* 删除 cur */CNode* victim cur;cur cur-next;free(victim);}int result cur-data;free(cur);return result;}这里用cur-next ! cur判断只剩一个而不是判断是否为空——循环链表里永远没有空指针这是与单链表最大的不同。三、静态链表用下标代替指针静态链表用两个数组或一个结构体数组模拟链表data存值next存下一个结点的下标-1表示结束。它不需要malloc适合嵌入式环境也适合需要把链表序列化到文件或共享内存的场景——下标在不同进程、不同次运行之间都是稳定的指针不是。一个常见的做法是把数组分成两部分已用结点组成数据链表未用结点组成空闲链表free_head指向第一个空闲位置。/* 适用于 C11 */#define MAXN 100typedef struct {int data;int next;} SNode;typedef struct {SNode node[MAXN];int head; /* 数据链表头下标-1 表示空 */int free_head; /* 空闲链表头下标 */} SList;void slist_init(SList* l) {l-head -1;l-free_head 0;for (int i 0; i MAXN - 1; i) {l-node[i].next i 1;}l-node[MAXN - 1].next -1;}int slist_alloc(SList* l) {if (l-free_head -1) return -1;int idx l-free_head;l-free_head l-node[idx].next;return idx;}void slist_release(SList* l, int idx) {l-node[idx].next l-free_head;l-free_head idx;}int slist_push_front(SList* l, int value) {int idx slist_alloc(l);if (idx -1) return 0;l-node[idx].data value;l-node[idx].next l-head;l-head idx;return 1;}int slist_remove(SList* l, int value) {int prev -1;int cur l-head;while (cur ! -1) {if (l-node[cur].data value) {if (prev -1) l-head l-node[cur].next;else l-node[prev].next l-node[cur].next;slist_release(l, cur);return 1;}prev cur;cur l-node[cur].next;}return 0;}插入与删除的代码和指针版几乎一样只是p p-next变成了cur l-node[cur].nextNULL变成了-1。理解这一点静态链表就不需要单独记忆。四、三种结构对比维度双链表循环链表静态链表每结点指针/下标2 个1 个1 个下标反向遍历支持不支持单循环不支持遍历终止p ! headp ! headdo-whileidx ! -1内存来源动态分配动态分配预分配数组插入删除O(1)已知结点O(1)已知前驱O(1)已知前驱典型场景LRU、双端队列约瑟夫环、轮询嵌入式、序列化常见坑点1. 双链表插入时先改前驱指针/* ❌ 原来的后继丢失 */pos-next node;node-next pos-next;/* ✅ 先接好新结点的两个指针再改前驱与后继 */node-next pos-next;node-prev pos;pos-next-prev node;pos-next node;2. 删除只改一个方向/* ❌ 后继的 prev 仍指向已释放结点 */node-prev-next node-next;free(node);/* ✅ 两个方向都要改 */node-prev-next node-next;node-next-prev node-prev;free(node);3. 循环链表用空指针判断结束/* ❌ 永远不为空死循环 */while (p ! NULL) { p p-next; }/* ✅ 回到起点即结束 */do { p p-next; } while (p ! head);4. 循环链表空表未判断/* ❌ head 为空时解引用 */do { printf(%d, head-data); } while (...);/* ✅ 先判空 */if (head NULL) return;5. 静态链表忘记初始化next/* ❌ 空闲链表里全是未初始化的下标 */l-free_head 0;/* ✅ 把整条空闲链串起来 */for (int i 0; i MAXN - 1; i) l-node[i].next i 1;l-node[MAXN - 1].next -1;6. 静态链表删除后不回收结点/* ❌ 数组越用越少最终分配失败 *//* ✅ 把结点挂回空闲链表 */l-node[idx].next l-free_head;l-free_head idx;7. 释放后继续访问prev/next/* ❌ 已释放内存的读取是未定义行为 */free(node);node-prev-next NULL;/* ✅ 先把指针关系处理好再释放 */8. 把哨兵当成数据结点遍历/* ❌ 哨兵里没有业务数据却被打印或统计 */for (DNode* p l-head; p ! NULL; p p-next)/* ✅ 从 head-next 开始到 head 结束 */for (DNode* p l-head-next; p ! l-head; p p-next)总结结构核心改动必须记住的终止条件双链表每结点多一个prevp ! head哨兵循环链表尾结点指回头p ! head用 do-while静态链表指针换成数组下标idx ! -1三种变体都围绕同一件事如何表示下一个以及到哪里停。双链表用两个方向的链接换取反向遍历与 O(1) 删除循环链表把终止条件从空改成回到起点静态链表把地址换成下标换来可序列化与零动态分配。把这两点想清楚三种结构的代码几乎是同一套模板。
