现在位置: 首页 / C语言进阶 / c语言 / 正文

C语言进阶：双向循环链表与哨兵头节点

C语言进阶：双向循环链表与哨兵头节点

双向循环链表与哨兵节点是嵌入式 C 语言开发中最实用的链表组合。链表通过指针串联离散内存节点，弥补了数组在插入/删除上的不足。本文重点讲解双向循环链表与哨兵头节点设计——这是嵌入式系统中最常用的链表形态。

一、数组 vs 链表

特性 数组 链表
内存布局 连续，随机访问 O(1) 离散，需遍历 O(n)
插入/删除 需移动数据 O(n) 只改指针 O(1)
大小 固定 动态按需增减
ℹ️ 为什么嵌入式偏爱链表？：任务切换、事件队列、缓冲区管理……这些场景需要频繁插入/删除，O(1) 的链表操作是刚需。

二、链表的演进路径

单向链表  →  带头节点的单向链表  →  双向链表  →  双向循环链表  →  双向循环链表 + 哨兵头节点

每往后演进一步，都是在解决前一种的典型缺点：

  • 带头节点的单向链表：解决空表、首节点插入/删除时边界判断多的问题。
  • 双向链表：解决删除节点时必须先找前驱节点、且不能反向遍历的问题。
  • 双向循环链表：解决头尾节点处理不统一、NULL 判断较多的问题，让首尾逻辑连成一个环。
  • 双向循环链表 + 哨兵头节点：进一步消除空链表、首元素、尾元素场景下的特判，让插入/删除代码完全统一。

三、双向循环链表核心概念

双向循环链表

双向：每个节点有前驱 prev 和后继 next 两个指针。

循环：尾节点的 next 指向头节点，头节点的 prev 指向尾节点，形成环。

单向链表：    A → B → C → NULL（有终点）
双向链表：    A ⇄ B ⇄ C（有头有尾）
双向循环：    A ⇄ B ⇄ C ⇄ A（首尾相连成环）
特性 说明
双向遍历 可向前或向后遍历，无需重新从头扫描
O(1) 删除 已知节点指针，直接修改前驱/后继，无需从头寻找前驱
尾部插入 O(1) 通过 head.prev 直接定位末尾节点，不需要遍历
首尾统一 循环结构消除了 NULL 终止判断，头尾与中间节点处理逻辑一致
空链表安全 配合哨兵后，空/非空链表的遍历/插入/删除代码路径完全相同

哨兵头节点

哨兵（Sentinel） 是一个永远存在于链表中、不存储业务数据的特殊节点，也叫哑节点（Dummy Node）。初始化时其 next 与 prev 均指向自身，形成只含哨兵的空环。

问题 哨兵的解法
空链表判断 head.next == &head 即为空，统一且高效
首节点特判 首节点的前驱就是哨兵，插入/删除代码与中间节点完全一致
尾节点特判 尾节点的后继就是哨兵，遍历终止条件统一为 node != &head
边界条件 任何位置的插入/删除只需修改固定数量的指针，无需 if 分支

四、节点设计：数据与链表分离

传统方式（数据耦合在节点里）

// ❌ 传统方式：数据域和指针域混在一起
typedef struct Node {
    int data;              // 数据
    struct Node *next;
    struct Node *prev;
} Node;

问题：数据类型改变，节点结构也要改，无法复用。

分离方式（节点不含数据）

💡 核心设计哲学：让节点「寄居」在数据里
ListNode_t 只负责穿针引线（维护 prev/next 链接关系），不存储任何业务数据。
业务结构体只负责存储数据，不关心链表实现细节。
使用时将 ListNode_t 作为成员嵌入业务结构体，节点就「挂载」到了数据上。
这样同一套链表代码可以无缝管理任意类型的数据，真正实现链表与业务解耦。 
// ✅ 分离方式：节点只负责链接，数据由外部持有
typedef struct ListNode {
    struct ListNode *next;
    struct ListNode *prev;
    void            *owner;   // 反向指针：指回持有此节点的业务结构体
} ListNode_t;

用代码看更直观：

// 1. 业务结构体里嵌入节点
typedef struct Student {
    int         id;
    char        name[32];
    ListNode_t  node;      // ← 节点嵌在这里，不单独分配
} Student_t;

// 2. 创建学生时，节点也随之存在（一次 malloc 搞定）
Student_t *stu = malloc(sizeof(Student_t));
stu->id = 1001;
stu->node.owner = stu;   // ← owner 指回自己

// 3. 链表操作的是节点指针，不关心业务数据
ListNode_t *p = &stu->node;

// 4. 需要业务数据时，通过 owner 反查
Student_t *found = (Student_t *)p->owner;
printf("id=%d, name=%s\n", found->id, found->name);

五、结构体定义

链表节点（ListNode_t）

typedef struct ListNode {
    struct ListNode *next;    // 后继指针
    struct ListNode *prev;    // 前驱指针
    void            *owner;   // 反向指针，指回持有此节点的业务结构体
} ListNode_t;

链表根（List_t）

typedef struct List {
    unsigned int   count;        // 有效节点数
    ListNode_t    *index;        // 遍历游标（可选）
    ListNode_t     head;         // 哨兵头节点
} List_t;
ℹ️ List_t 是传统裸指针的工程化升级
传统做法用 ListNode_t *head 管理链表入口，但它不知道节点数，也无法记住遍历位置。
List_t 将其升级为管理结构：head 是哨兵实体节点（永远存在），count 是 O(1) 节点计数，index 是遍历游标。

六、内存结构图解

空链表

初始化后，哨兵的 next 和 prev 都指向自己：

      List_t
┌───────────────────┐
│ count = 0         │
│ head（哨兵）:     │
│   next ──┐        │
│   prev ──┘ ←─自指 │
└───────────────────┘

含两个节点时

head ⇄ A ⇄ B ⇄ head

[head]  next → A    prev → B
[A]     next → B    prev → head    owner → &DataA
[B]     next → head prev → A       owner → &DataB

七、双向循环链表核心操作实现

⚠️ 核心思想：双向循环链表插入/删除只改指针，不移动数据，O(1) 完成。

初始化

void list_init(List_t *list)
{
    list->head.next  = &list->head;
    list->head.prev  = &list->head;
    list->head.owner = NULL;
    list->count      = 0;
    list->index      = &list->head;
}

末尾插入

在哨兵之前插入，即插到链表末尾，修改 4 根指针：

void list_insert_tail(List_t *list, ListNode_t *new_node)
{
    ListNode_t *head = &list->head;

    new_node->next   = head;          /* ① 新节点后继 = 哨兵 */
    new_node->prev   = head->prev;    /* ② 新节点前驱 = 原末尾 */
    head->prev->next = new_node;      /* ③ 原末尾后继 = 新节点 */
    head->prev       = new_node;      /* ④ 哨兵前驱   = 新节点 */

    list->count++;
}
⚠️ 指针赋值顺序很关键！
先改新节点自己的指针（① ②），再改旧节点的指针（③ ④）。顺序颠倒会导致原指针丢失，产生断链。

头部插入

在哨兵之后插入，即插到链表头部：

void list_insert_head(List_t *list, ListNode_t *new_node)
{
    ListNode_t *head = &list->head;

    new_node->next   = head->next;    /* ① 新节点后继 = 原第一个节点 */
    new_node->prev   = head;          /* ② 新节点前驱 = 哨兵 */
    head->next->prev = new_node;      /* ③ 原第一个节点前驱 = 新节点 */
    head->next       = new_node;      /* ④ 哨兵后继 = 新节点 */

    list->count++;
}

删除节点

双向链表删除无需遍历找前驱，直接用 prev 访问，只改 2 根指针：

void list_remove(List_t *list, ListNode_t *node)
{
    node->next->prev = node->prev;    /* ① 后继的前驱 = 被删节点的前驱 */
    node->prev->next = node->next;    /* ② 前驱的后继 = 被删节点的后继 */

    if (list->index == node) {
        list->index = node->prev;     /* 游标避开被删节点 */
    }

    node->next = NULL;
    node->prev = NULL;
    list->count--;
}

遍历链表

ListNode_t *node = list->head.next;
while (node != &list->head) {
    // 通过 owner 访问业务数据
    Student_t *stu = (Student_t *)node->owner;
    printf("%s\n", stu->name);
    node = node->next;
}

八、完整示例

int main(void)
{
    List_t    class_list;
    Student_t alice = {1001, "Alice"};
    Student_t bob   = {1002, "Bob"};
    Student_t carol = {1003, "Carol"};

    list_init(&class_list);

    alice.node.owner = &alice;
    bob.node.owner   = &bob;
    carol.node.owner = &carol;

    list_insert_tail(&class_list, &alice.node);
    list_insert_tail(&class_list, &bob.node);
    list_insert_tail(&class_list, &carol.node);

    // 遍历打印
    ListNode_t *node = class_list.head.next;
    while (node != &class_list.head) {
        Student_t *stu = (Student_t *)node->owner;
        printf("ID: %d, Name: %s\n", stu->id, stu->name);
        node = node->next;
    }

    // 删除 bob
    list_remove(&bob.node);

    return 0;
}

总结

双向循环链表 + 哨兵节点是嵌入式 C 语言中最实用的链表组合。核心优势：

  • O(1) 插入/删除：已知节点指针，直接操作前驱/后继指针
  • 哨兵消除特判：空链表、首尾节点与中间节点代码路径完全一致
  • 数据与链表分离：owner 指针让链表节点可嵌入任意结构体，实现零耦合复用
  • 循环结构统一遍历终止条件：node != &head 覆盖所有情况