数据结构：双向循环链表实现 | 极客日志

C算法

数据结构：双向循环链表实现

本文介绍了双向循环链表的数据结构概念及其在 C 语言中的具体实现。通过引入哨兵位头节点简化了边界处理逻辑，详细阐述了初始化、销毁、头尾插入删除、元素查找及打印等核心功能的代码编写方法。文中提供了完整的头文件与源文件示例，展示了如何利用 prev 和 next 指针构建双向循环结构，并包含测试用例验证功能正确性。适合需要掌握基础数据结构实现的开发者参考。

无尘发布于 2026/3/160 浏览

循环与双向

1、循环链表

单向链表的最后一个节点 next 指针通常指向 NULL，而循环链表的尾节点 next 指针重新指向头节点，形成闭环。

2、双向链表

双向链表的每个节点包含两个指针，一个指向前驱节点 (prev)，另一个指向后继节点 (next)。

实现

了解了基本概念后，下面进行具体实现。采用哨兵位头节点的方式可以简化边界处理逻辑。

头文件

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

typedef int ListType;

typedef struct Node {
    ListType data;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct List {
    Node* _head;
} List;

void InitList(List* p);
void DestroyList(List* p);
void PrintList(List* p);
Node* BuyNewNode(ListType x);
void HeadInsert(List* p, ListType x);
void TailInsert(List* p, ListType x);
void ;
 ;
Node* ;
 ;
 ;

相关免费在线工具

加密/解密文本
使用加密算法（如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

Node* BuyNewNode(ListType x) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (newnode == NULL) {
        perror("malloc newnode failed!");
        return NULL;
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

void InitList(List* p) {
    assert(p);
    p->_head = BuyNewNode(0); // 哨兵位头节点
    p->_head->next = p->_head;
    p->_head->prev = p->_head; // 双向循环初始化
}

void DestroyList(List* p) {
    assert(p);
    Node* cur = p->_head->next;
    while (cur != p->_head) {
        Node* next = cur->next;
        free(cur);
        cur = next;
    }
    free(p->_head);
    p->_head = NULL;
}

void HeadInsert(List* p, ListType x) {
    assert(p);
    Node* newnode = BuyNewNode(x);
    newnode->next = p->_head->next;
    newnode->prev = p->_head;
    p->_head->next->prev = newnode;
    p->_head->next = newnode;
}

void HeadDelete(List* p) {
    assert(p);
    if (p->_head->next == p->_head) return;
    Node* tmp = p->_head->next;
    p->_head->next = tmp->next;
    tmp->next->prev = p->_head;
    free(tmp);
}

void TailInsert(List* p, ListType x) {
    assert(p);
    Node* tail = p->_head->prev;
    Node* newnode = BuyNewNode(x);
    newnode->next = p->_head;
    newnode->prev = tail;
    tail->next = newnode;
    p->_head->prev = newnode;
}

void TailDelete(List* p) {
    assert(p);
    if (p->_head->next == p->_head) return;
    Node* tail = p->_head->prev;
    Node* prev = tail->prev;
    prev->next = p->_head;
    p->_head->prev = prev;
    free(tail);
}

Node* FindElem(List* p, ListType x) {
    assert(p);
    if (p->_head->next == p->_head) {
        printf("链表为空！\n");
        return NULL;
    }
    Node* cur = p->_head->next;
    while (cur != p->_head) {
        if (cur->data == x) {
            printf("成功找到值为 %d 的元素。\n", cur->data);
            return cur;
        }
        cur = cur->next;
    }
    printf("未找到对应值的元素！\n");
    return NULL;
}

void ElemDelete(List* p, ListType x) {
    assert(p);
    if (p->_head->next == p->_head) {
        perror("the list is empty!");
        return;
    }
    Node* cur = p->_head->next;
    while (cur != p->_head) {
        if (cur->data == x) {
            Node* next = cur->next;
            Node* prev = cur->prev;
            prev->next = next;
            next->prev = prev;
            free(cur);
            printf("找到值为 %d 的元素，已执行删除操作。\n", x);
            return;
        }
        cur = cur->next;
    }
    printf("未找到对应值的元素！删除失败！\n");
}

void ElemDeleteAll(List* p, ListType x) {
    assert(p);
    if (p->_head->next == p->_head) {
        perror("the list is empty!");
        return;
    }
    Node* cur = p->_head->next;
    int tmp = 0;
    while (cur != p->_head) {
        if (cur->data == x) {
            Node* next = cur->next;
            Node* prev = cur->prev;
            prev->next = next;
            next->prev = prev;
            free(cur);
            tmp++;
            cur = next;
        } else {
            cur = cur->next;
        }
    }
    if (tmp == 0) {
        printf("未找到对应值的元素！删除失败！\n");
    } else {
        printf("已成功删除了 %d 个值为 %d 的元素。\n", tmp, x);
    }
}

void PrintList(List* p) {
    assert(p);
    Node* cur = p->_head->next;
    while (cur != p->_head) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

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

typedef int ListType;

typedef struct Node {
    ListType data;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct List {
    Node* _head;
} List;

void InitList(List* p);
void DestroyList(List* p);
void PrintList(List* p);
Node* BuyNewNode(ListType x);
void HeadInsert(List* p, ListType x);
void TailInsert(List* p, ListType x);
void HeadDelete(List* p);
void TailDelete(List* p);
Node* FindElem(List* p, ListType x);
void ElemDelete(List* p, ListType x);
void ElemDeleteAll(List* p, ListType x);

#include "List.h"

void PrintList(List* p) {
    assert(p);
    Node* cur = p->_head->next;
    while (cur != p->_head) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

Node* BuyNewNode(ListType x) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (newnode == NULL) {
        perror("malloc newnode failed!");
        return NULL;
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

void InitList(List* p) {
    assert(p);
    p->_head = BuyNewNode(0);
    p->_head->next = p->_head;
    p->_head->prev = p->_head;
}

void DestroyList(List* p) {
    assert(p);
    Node* cur = p->_head->next;
    while (cur != p->_head) {
        Node* next = cur->next;
        free(cur);
        cur = next;
    }
    free(p->_head);
    p->_head = NULL;
}

void HeadInsert(List* p, ListType x) {
    assert(p);
    Node* newnode = BuyNewNode(x);
    newnode->next = p->_head->next;
    newnode->prev = p->_head;
    p->_head->next->prev = newnode;
    p->_head->next = newnode;
}

void HeadDelete(List* p) {
    assert(p);
    if (p->_head->next == p->_head) return;
    Node* tmp = p->_head->next;
    p->_head->next = tmp->next;
    tmp->next->prev = p->_head;
    free(tmp);
}

void TailInsert(List* p, ListType x) {
    assert(p);
    Node* tail = p->_head->prev;
    Node* newnode = BuyNewNode(x);
    newnode->next = p->_head;
    newnode->prev = tail;
    tail->next = newnode;
    p->_head->prev = newnode;
}

void TailDelete(List* p) {
    assert(p);
    if (p->_head->next == p->_head) return;
    Node* tail = p->_head->prev;
    Node* prev = tail->prev;
    prev->next = p->_head;
    p->_head->prev = prev;
    free(tail);
}

Node* FindElem(List* p, ListType x) {
    assert(p);
    if (p->_head->next == p->_head) {
        printf("链表为空！\n");
        return NULL;
    }
    Node* cur = p->_head->next;
    while (cur != p->_head) {
        if (cur->data == x) {
            printf("成功找到值为 %d 的元素。\n", cur->data);
            return cur;
        }
        cur = cur->next;
    }
    printf("未找到对应值的元素！\n");
    return NULL;
}

void ElemDelete(List* p, ListType x) {
    assert(p);
    if (p->_head->next == p->_head) {
        perror("the list is empty!");
        return;
    }
    Node* cur = p->_head->next;
    while (cur != p->_head) {
        if (cur->data == x) {
            Node* next = cur->next;
            Node* prev = cur->prev;
            prev->next = next;
            next->prev = prev;
            free(cur);
            printf("找到值为 %d 的元素，已执行删除操作。\n", x);
            return;
        }
        cur = cur->next;
    }
    printf("未找到对应值的元素！删除失败！\n");
}

void ElemDeleteAll(List* p, ListType x) {
    assert(p);
    if (p->_head->next == p->_head) {
        perror("the list is empty!");
        return;
    }
    Node* cur = p->_head->next;
    int tmp = 0;
    while (cur != p->_head) {
        if (cur->data == x) {
            Node* next = cur->next;
            Node* prev = cur->prev;
            prev->next = next;
            next->prev = prev;
            free(cur);
            tmp++;
            cur = next;
        } else {
            cur = cur->next;
        }
    }
    if (tmp == 0) {
        printf("未找到对应值的元素！删除失败！\n");
    } else {
        printf("已成功删除了 %d 个值为 %d 的元素。\n", tmp, x);
    }
}

#include "List.h"

void Test() {
    List lt;
    InitList(&lt);
    HeadInsert(&lt, 1);
    HeadInsert(&lt, 2);
    HeadInsert(&lt, 3);
    HeadInsert(&lt, 4);
    TailInsert(&lt, 1);
    TailInsert(&lt, 2);
    TailInsert(&lt, 3);
    TailInsert(&lt, 4);
    PrintList(&lt);
    TailDelete(&lt);
    TailDelete(&lt);
    PrintList(&lt);
    Node* Four = FindElem(&lt, 4);
    ElemDeleteAll(&lt, 2);
    PrintList(&lt);
    DestroyList(&lt);
}

int main() {
    Test();
    return 0;
}

数据结构：双向循环链表实现

循环与双向

1、循环链表

2、双向链表

实现

头文件

更多推荐文章

相关免费在线工具

源文件

1、创建新节点

2、初始化

3、销毁

4、头插

5、头删

6、尾插

7、尾删

8、查找与删除

9、打印链表

完整项目代码

List.h

List.c

测试函数

数据结构：双向循环链表实现

循环与双向

1、循环链表

2、双向链表

实现

头文件

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

源文件

1、创建新节点

2、初始化

3、销毁

4、头插

5、头删

6、尾插

7、尾删

8、查找与删除

9、打印链表

完整项目代码

List.h

List.c

测试函数