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

发布时间：2021-11-30 10:55:49 作者：iii
来源：亿速云阅读：213

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

应用场景

进程调度：Linux内核的任务调度队列
内存管理：Buddy System中的空闲块管理
游戏开发：场景对象管理
音乐播放器：循环播放列表实现

性能分析

操作时间复杂度对比：

操作	时间复杂度	备注
插入/删除	O(1)	已知位置时
查找	O(n)	需要遍历
访问头尾	O(1)	直接通过head节点访问

内存占用公式：总内存 = n * (sizeof(data) + 2 * sizeof(pointer)) + sizeof(head)

总结

带头双向环形链表通过以下设计实现高效操作： 1. 哨兵节点消除特殊边界判断 2. 双向指针支持快速前后操作 3. 环形结构实现无缝循环遍历

实际开发中的优化建议： - 结合哈希表实现快速查找（如Linux内核的hlist） - 预分配节点内存池减少malloc调用 - 实现线程安全版本（加锁或使用无锁编程） “`