C语言数据结构之双链表循环链表静态链表详解

前言

单链表只能单向走，删除一个结点要先找到它的前驱；循环链表让尾结点指回头结点，适合"环形"语义；静态链表则用数组下标代替指针，在没有动态内存分配的环境里模拟链表。这三种结构都是单链表的变体，但各自解决不同的问题。

常见的误解有三个。第一，以为双链表删除一定 O(1)——只有已经拿到待删结点的指针时才成立，按值查找仍要 O(n)。第二，用while (p != NULL)遍历循环链表，结果永远走不到空指针，直接死循环。第三，把静态链表当成"数组"，忽略了它的核心是用next下标串起逻辑顺序，物理顺序与逻辑顺序可以完全不同。

本文用 C11 分别实现三种结构，重点讲指针/下标的修改顺序、遍历的终止条件、以及各自的适用场景。所有示例只用标准库。

一、双链表：多一个prev换来双向能力

双链表每个结点保存prev与next。好处是给定结点指针后，插入与删除都是 O(1)，不需要从头找前驱；代价是每个结点多一个指针，且每次修改要同时维护两个方向。

用一个哨兵结点（sentinel）可以消掉"空表""删头""插到末尾"这些特判：哨兵的next指向第一个元素，prev指向最后一个元素；空表时两者都指向自己。

/* 适用于 C11 */
#include <stdio.h>
#include <stdlib.h>

typedef 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 100

typedef 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].next，NULL变成了-1。理解这一点，静态链表就不需要单独记忆。

四、三种结构对比

常见坑点

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)

总结

三种变体都围绕同一件事：如何表示"下一个"以及"到哪里停"。双链表用两个方向的链接换取反向遍历与 O(1) 删除；循环链表把终止条件从"空"改成"回到起点"；静态链表把地址换成下标，换来可序列化与零动态分配。把这两点想清楚，三种结构的代码几乎是同一套模板。