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

#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节点

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;
}

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;
}

// 打印
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语言传值调用，外部需手动置空传入的指针
}

// 查找节点，常用于配合后续的删除或修改操作
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); // 释放被删除节点的内存
}

// 头插：等价于在 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);
}