C语言详解：实现双向带头循环链表（含完整代码）

花开有时

发布时间：2026-10-15| 3人浏览过

原创

双向带头循环链表是C语言数据结构中的核心组件之一。相比普通链表，它通过哨兵位（Head Node）消除了对空指针和头尾特殊情况的处理开销，使得插入和删除操作的时间复杂度稳定在O(1)。本文将基于C语言，详细讲解其底层结构设计与各功能接口的实现逻辑。

一、结构与基础对比

在深入代码之前，需明确双向带头循环链表（以下简称双循链）与传统顺序表及单向链表的差异。双循链虽然内存地址不一定连续，但凭借其灵活的指针指向，能完美解决单链表无法直接获取前驱节点以及需要频繁进行头尾操作的场景问题。

特性维度	顺序表 (Static Array)	双向带头循环链表
内存存储	连续空间，缓存命中率极高	离散分配，三缓命中率较低
随机访问	支持O(1)索引访问	不支持，必须遍历查找
任意位置插入/删除	非尾部操作均需挪动元素，O(N)	仅修改指针即可，时间复杂度O(1)
适用场景	读多写少、频繁按索引访问	频繁进行头部或中部数据的增删

由于寄存器读取数据时会预判相邻地址的数据，顺序表因其连续的物理存储特性，具有极高的三级缓存命中率，适合大量读取的场景。而链表虽然在内存上存在跳跃，但在高频变动数据的业务场景中更具优势。

所谓的“带头”与“双向”，是指链表中存在一个不存储实际业务数据（哨兵位）的头结点（Guard Head），且每个节点均包含指向前驱的 prev 指针和指向后继的 next 指针。“循环”则意味着尾节点的 next 指向头结点，头结点的 prev 指向尾节点，形成闭环。

二、接口声明 (List.h)

为了封装良好的模块化设计，我们将类型定义与函数声明置于头文件中。使用哨兵位的链表在进行判空时非常方便，当 phead->next == phead 时，即代表有效节点个数为0。

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int ListDateType;

// 节点定义
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    ListDateType date;
}ListNode;

// 基础管理
ListNode* ListInit();        // 初始化：返回带哨兵位的头结点指针
void ListDestroy(ListNode* phead); // 销毁链表资源
void PrintList(ListNode* phead);   // 打印链表所有数据
bool ListEmpty(ListNode* phead);   // 判断链表是否为空（仅含哨兵位）
 
// 头部操作
void ListPushFront(ListNode* phead, ListDateType x); // 头插
void ListPopFront(ListNode* phead);                  // 头删

// 尾部操作
void ListPushBack(ListNode* phead, ListDateType x);  // 尾插
void ListPopback(ListNode* phead);                   // 尾删

size_t ListSize(ListNode* phead); // 统计有效节点数

// 定位与修改
ListNode* ListFind(ListNode* phead, ListDateType x); // 查找指定数据
void ListInsert(ListNode* pos, ListDateType x);      // 在pos节点前插入
void ListErase(ListNode* pos);                       // 删除pos节点

三、核心实现原理 (List.c)

第1步：初始化哨兵位

初始化是链表构建的第一步。我们需要动态开辟一块内存作为哨兵位，并将其前后指针都指向自己，形成一个初始的最小闭环。

ListNode* ListInit()
{
    ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
    if (guard == NULL)
    {
        perror("ListInit fail:\n");
        exit(-1);
    }
    // 哨兵位本身不存数据，但必须有next和prev以便后续挂接节点
    guard->next = guard;
    guard->prev = guard;
    return guard;
}

第2步：辅助函数——购买节点

在所有插入操作（头插、尾插、任意插）中，都需要临时创建一个新节点。将这部分逻辑抽离为 BuyNode 可大幅减少重复代码。

ListNode* BuyNode(ListDateType x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("BuyNode:");
        exit(-1);
    }
    newnode->date = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

第3步：基础操作——打印、判空与销毁

打印需要从头结点的下一个开始遍历直到回到头结点；判空只需检查首尾是否相连；销毁则需要注意先释放有效数据节点，最后释放哨兵位，并提醒调用者将头指针置空以避免悬垂指针。

// 打印
void PrintList(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d <=> ", cur->date);
        cur = cur->next;
    }
    printf("\n");
}

// 判空
bool ListEmpty(ListNode* phead)
{
    assert(phead);
    // 如果头结点的next还是指向自己，说明中间没有节点
    return phead->next == phead;
}

// 销毁
void ListDestroy(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead); // 最后释放哨兵位
    phead = NULL; // 注意：C语言传值调用，外部需手动置空传入的指针
}

第4步：核心机制——任意位置的插入与删除

双向链表的精髓在于 ListInsert 和 ListErase。一旦这两个接口正确实现了四个指针（新节点的前后、目标节点的前后）的重定向，头插、尾插等操作都可复用此逻辑。

// 查找节点，常用于配合后续的删除或修改操作
ListNode* ListFind(ListNode* phead, ListDateType x)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->date == x)
            return cur;
        cur = cur->next;
    }
    return NULL; // 未找到
}

// 在pos节点前面插入一个新节点x
void ListInsert(ListNode* pos, ListDateType x)
{
    assert(pos);
    ListNode* newnode = BuyNode(x);
    ListNode* prev = pos->prev; // 获取pos的前一个节点

    // 1. 调整 prev 与新节点的关系
    prev->next = newnode;
    newnode->prev = prev;

    // 2. 调整 newnode 与 pos 的关系
    newnode->next = pos;
    pos->prev = newnode;
}

// 删除pos位置的节点
void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;

    // 跳过pos，将其前后节点连接
    prev->next = next;
    next->prev = prev;

    free(pos); // 释放被删除节点的内存
}

第5步：封装特定操作——头插、尾插、头删、尾删

有了通用的插入删除接口，以下函数的实现变得非常简单，同时体现了带头循环链表消除边界判断的优势：

// 头插：等价于在 phead->next 处插入
void ListPushFront(ListNode* phead, ListDateType x)
{
    ListInsert(phead->next, x);
}

// 尾插：等价于在 phead 处插入（因为 phead 循环链接着尾部）
void ListPushBack(ListNode* phead, ListDateType x)
{
    ListInsert(phead, x);
}

// 头删：等价于删除 phead->next
void ListPopFront(ListNode* phead)
{
    assert(!ListEmpty(phead));
    ListErase(phead->next);
}

// 尾删：等价于删除 phead->prev
void ListPopback(ListNode* phead)
{
    assert(!ListEmpty(phead));
    ListErase(phead->prev);
}

以上就是实现C语言双向带头循环链表的详细内容。通过掌握指针的四次重定向操作，您可以应对绝大多数链表类面试题。更多关于数据结构的知识资料请关注本站其它相关文章！