数据结构：带头双向循环链表的定义与实现 | 极客日志

C算法

数据结构：带头双向循环链表的定义与实现

详细讲解了带头双向循环链表的定义、结构特点及核心接口实现。内容包括头插、头删、尾插、尾删及任意位置插入删除操作。通过与无头单向非循环链表对比，阐述了带头双向循环链表在简化操作方面的优势。提供了完整的 C 语言代码示例，涵盖节点结构体定义、内存分配及指针维护逻辑。

莫名其妙发布于 2026/3/28更新于 2026/4/164 浏览

数据结构：带头双向循环链表的定义与实现

文章配图

1. 链表的分类

链表有多种分类，单链表是结构最简单的链表之一，但使用较为繁琐。根据是否带头、单向或双向、循环或非循环，链表可分为多种结构。我们重点讲解两种极端情况：无头单向非循环链表（结构最简单，使用最麻烦）和带头双向循环链表（结构最复杂，使用最简单）。掌握这两种链表后，其他链表的使用将游刃有余。

无头单向非循环链表（单链表）：

文章配图

带头双向循环链表：

文章配图

2. 带头双向循环链表

下面对带头双向循环链表的相关接口进行实现。

接口声明

首先定义头文件，包含结构体声明和各种接口：

typedef int LTDataType;

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

// 创建返回链表的头结点
ListNode* ListCreate();
// 创建一个新节点
ListNode* BuyListNode();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);

 ;

 ;

 ;

 ;

ListNode* ;

 ;

 ;

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

// 创建一个头节点
ListNode* ListCreate() {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL) {
        printf("开辟节点失败");
        return NULL;
    }
    head->next = head;
    head->prev = head;
    return head;
}

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x) {
    assert(plist);
    ListNode* next = plist->next;
    ListNode* NewNext = BuyListNode();
    NewNext->data = x;
    NewNext->next = plist->next;
    NewNext->prev = plist;
    plist->next = NewNext;
    next->prev = NewNext;
}

// 双向链表头删
void ListPopFront(ListNode* plist) {
    assert(plist);
    assert(plist->next != plist);
    ListNode* next = plist->next;
    ListNode* NewNext = next->next;
    NewNext->prev = plist;
    plist->next = NewNext;
    free(next);
    next = NULL;
}

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x) {
    assert(plist);
    ListNode* tail = plist->prev;
    ListNode* NewTail = BuyListNode();
    NewTail->data = x;
    NewTail->prev = plist->prev;
    tail->next = NewTail;
    NewTail->next = plist;
    plist->prev = NewTail;
}

// 双向链表尾删
void ListPopBack(ListNode* plist) {
    assert(plist);
    assert(plist->next != plist);
    ListNode* tail = plist->prev;
    ListNode* NewTail = tail->prev;
    plist->prev = NewTail;
    NewTail->next = plist;
    free(tail);
    tail = NULL;
}

// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* NewPrev = BuyListNode();
    NewPrev->data = x;
    NewPrev->next = pos;
    NewPrev->prev = prev;
    prev->next = NewPrev;
    pos->prev = NewPrev;
}

// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos, ListNode* phead) {
    assert(pos);
    assert(pos != phead);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;
    prev->next = next;
    next->prev = prev;
    free(pos);
    pos = NULL;
}