C语言怎么实现带头双向环形链表

# C语言怎么实现带头双向环形链表

## 目录
1. [数据结构概述](#数据结构概述)
2. [节点结构设计](#节点结构设计)
3. [链表初始化](#链表初始化)
4. [基本操作实现](#基本操作实现)
   - [插入操作](#插入操作)
   - [删除操作](#删除操作)
   - [查找操作](#查找操作)
5. [遍历与打印](#遍历与打印)
6. [内存管理](#内存管理)
7. [完整代码示例](#完整代码示例)
8. [应用场景](#应用场景)
9. [性能分析](#性能分析)
10. [总结](#总结)

---

## 数据结构概述
带头双向环形链表是链表结构中最复杂的形态，具有以下特征：
- **带头节点**：固定存在的哨兵节点，简化边界条件处理
- **双向链接**：每个节点包含前驱(pre)和后继(next)指针
- **环形结构**：尾节点指向头节点，形成闭合环

优势对比：
| 链表类型        | 插入删除复杂度 | 空间开销 | 遍历方向 |
|----------------|---------------|----------|----------|
| 单向链表        | O(n)          | 小       | 单向     |
| 双向链表        | O(1)          | 中       | 双向     |
| 双向环形链表    | O(1)          | 中       | 双向循环 |

## 节点结构设计
```c
typedef int LTDataType;  // 数据类型可自定义

typedef struct ListNode {
    LTDataType data;
    struct ListNode* prev;  // 前驱指针
    struct ListNode* next;  // 后继指针
} ListNode;

+------+    +------+    +------+
| head |<-->| node1|<-->| node2|
+------+    +------+    +------+
  ^                      ^
  |______________________|

ListNode* ListCreate() {
    ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
    if (!guard) {
        perror("malloc fail");
        exit(EXIT_FLURE);
    }
    
    guard->prev = guard;
    guard->next = guard;
    return guard;
}

+------+
| head |<--+
+------+   |
  ^        |
  +--------+

void ListPushFront(ListNode* pHead, LTDataType x) {
    assert(pHead);
    ListNode* newNode = CreateNode(x);
    newNode->next = pHead->next;
    newNode->prev = pHead;
    pHead->next->prev = newNode;
    pHead->next = newNode;
}

Before:
+------+    +------+
| head |<-->| node1|
+------+    +------+

After:
+------+    +------+    +------+
| head |<-->| new  |<-->| node1|
+------+    +------+    +------+

void ListPushBack(ListNode* pHead, LTDataType x) {
    assert(pHead);
    ListNode* tail = pHead->prev;
    ListNode* newNode = CreateNode(x);
    
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = pHead;
    pHead->prev = newNode;
}

void ListErase(ListNode* pos) {
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
}

Before:
+------+    +------+    +------+
| node1|<-->| node2|<-->| node3|
+------+    +------+    +------+

After:
+------+    +------+
| node1|<-->| node3|
+------+    +------+

ListNode* ListFind(ListNode* pHead, LTDataType x) {
    assert(pHead);
    ListNode* cur = pHead->next;
    while (cur != pHead) {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

void ListPrint(ListNode* pHead) {
    assert(pHead);
    printf("HEAD<=>");
    ListNode* cur = pHead->next;
    while (cur != pHead) {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
    printf("HEAD\n");
}

void ListReversePrint(ListNode* pHead) {
    assert(pHead);
    printf("HEAD<=>");
    ListNode* cur = pHead->prev;
    while (cur != pHead) {
        printf("%d<=>", cur->data);
        cur = cur->prev;
    }
    printf("HEAD\n");
}

void ListDestroy(ListNode** ppHead) {
    assert(ppHead && *ppHead);
    ListNode* cur = (*ppHead)->next;
    while (cur != *ppHead) {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(*ppHead);
    *ppHead = NULL;
}

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;

typedef struct ListNode {
    LTDataType data;
    struct ListNode* prev;
    struct ListNode* next;
} ListNode;

// 创建新节点
ListNode* CreateNode(LTDataType x) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (!node) {
        perror("malloc fail");
        exit(EXIT_FLURE);
    }
    node->data = x;
    node->prev = node->next = NULL;
    return node;
}

// 初始化链表
ListNode* ListInit() {
    ListNode* pHead = CreateNode(-1); // 哨兵节点
    pHead->prev = pHead;
    pHead->next = pHead;
    return pHead;
}

// ...（完整实现所有上述函数）

int main() {
    ListNode* plist = ListInit();
    
    // 测试操作
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushFront(plist, 0);
    
    ListPrint(plist);  // 输出: HEAD<=>0<=>1<=>2<=>HEAD
    
    ListNode* pos = ListFind(plist, 1);
    if (pos) {
        ListErase(pos);
    }
    
    ListReversePrint(plist); // 输出: HEAD<=>2<=>0<=>HEAD
    
    ListDestroy(&plist);
    return 0;
}