[C语言]双向循环链表的增删改查功能

[C语言]双向循环链表的增删改查功能

1. 前言

本例提供一个可复用的双向循环链表模板，含完整接口与菜单式示例主程序，便于快速集成或学习链表操作。

2. 功能/亮点概览

• 双向循环 + 哨兵节点，边界处理简单。
• 增删改查全覆盖，含头/尾/指定位置插入。
• 自定义数据释放，降低内存泄漏风险。
• UTF-8 友好，Windows 终端中文不乱码。
• 交互式菜单示例，可直接运行体验。

3. 核心内容解析

3.1 原理与流程

• 采用哨兵节点，空表时sentinel.prev/next指向自身。
• 插入/删除通过局部链接/断链完成，时间复杂度 O(1)（定位节点后）。

核心代码：哨兵节点初始化

哨兵节点的初始化是双向循环链表的基础，通过将prev和next都指向自身，形成一个自循环结构：

void list_init(list *lst) { if (lst == NULL) { return; } lst->sentinel.next = &lst->sentinel; lst->sentinel.prev = &lst->sentinel; lst->sentinel.data = NULL; lst->size = 0; }

关键点解析：

• sentinel.next = &sentinel和sentinel.prev = &sentinel形成自循环，表示空表状态
• sentinel.data = NULL明确哨兵节点不存储数据
• size = 0记录当前链表节点数量（不含哨兵）

【双向循环链表结构示意图】

空表时：

┌───────────────┐ │ sentinel │ │ prev ─────┐ │ │ next ──┐ │ │ └────┬───┴──┘ │ │ └───┘ └───────────(指向自身)

含 2 个节点时：

┌─────────────────┐ ┌─────────────┐ ┌─────────────┐ │ sentinel │ ◀────▶ │ node1 │ ◀───▶ │ node2 │ └─────┬────┬──────┘ └─────┬───────┘ └─────┬───────┘ │ │ │ │ │ │ │ │ prev ◀────┘ └──── next prev ◀┘ next └────┐ ▲ ▲ ▲ │ │ │ │ │ └───────────┴────────────┴────────────────────────────────┘ (循环，最后一个节点的 next 回到哨兵，哨兵 prev回到最后节点)

• 插入/删除实际只需设置对应指针，无论头尾均不需特殊处理。
• 每个 node 都有 prev/next，两端永远指向合法节点（哨兵或数据节点），实现循环。

⭐ 核心要点：如何判断循环链表已到末尾并开始下一个循环

这是双向循环链表与普通链表的根本区别！

在双向循环链表中，没有真正的"末尾"，因为最后一个节点的next指向哨兵，哨兵的next又指向第一个节点，形成闭环。遍历时，通过检查当前节点是否等于哨兵节点来判断是否完成一圈。

判断方法：

// 遍历循环链表的标准模式list_node*cur=lst->sentinel.next;// 从第一个数据节点开始while(cur!=&lst->sentinel){// 关键：当 cur 等于哨兵时，说明已遍历完一圈// 处理当前节点 curcur=cur->next;// 移动到下一个节点}

关键代码示例：清空链表时的遍历

void list_clear(list *lst, void (*free_data)(void *)) { if (lst == NULL) { return; } list_node *cur = lst->sentinel.next; // 从第一个数据节点开始 while (cur != &lst->sentinel) { // ⭐ 关键判断：cur == &sentinel 表示已回到起点 list_node *next = cur->next; // 先保存下一个节点 if (free_data != NULL) { free_data(cur->data); } free(cur); cur = next; // 移动到下一个节点 } // 循环结束后，所有数据节点已释放，只剩哨兵节点 lst->sentinel.next = &lst->sentinel; lst->sentinel.prev = &lst->sentinel; lst->size = 0; }

关键代码示例：打印链表时的遍历

static void print_int_list(const list *lst) { if (lst == NULL || list_is_empty(lst)) { printf("列表为空。\n"); return; } const list_node *cur = lst->sentinel.next; // 从第一个数据节点开始 printf("列表内容: "); while (cur != &lst->sentinel) { // ⭐ 关键判断：遇到哨兵说明遍历完一圈 int *val = (int *)cur->data; printf("%d ", val != NULL ? *val : 0); cur = cur->next; // 移动到下一个节点 } printf("\n"); }

关键代码示例：查找节点时的遍历

list_node *list_find(list *lst, int (*predicate)(void *data, void *ctx), void *ctx) { if (lst == NULL || predicate == NULL) { return NULL; } list_node *cur = lst->sentinel.next; // 从第一个数据节点开始 while (cur != &lst->sentinel) { // ⭐ 关键判断：遍历完一圈后自动停止 if (predicate(cur->data, ctx)) { return cur; // 找到匹配节点，立即返回 } cur = cur->next; // 继续下一个节点 } return NULL; // 遍历完一圈未找到，返回 NULL }

重要理解：

1. 循环链表没有 NULL 指针作为结束标志，普通链表用cur != NULL判断结束
2. 哨兵节点作为循环的起点和终点，cur == &sentinel表示已回到起点，遍历完成
3. 遍历从sentinel.next开始，这是第一个数据节点
4. 遍历到sentinel时停止，此时已访问完所有数据节点，回到起点
5. 如果继续cur = cur->next，会再次进入数据节点区域，形成无限循环（除非有额外条件控制）

对比普通链表：

// 普通链表（有 NULL 结尾）while(cur!=NULL){// NULL 作为结束标志// 处理节点cur=cur->next;}// 循环链表（哨兵作为结束标志）while(cur!=&sentinel){// 哨兵作为结束标志// 处理节点cur=cur->next;}

3.2 核心实现讲解

• 结构体：list_node（prev/next/data），list（sentinel + size）。
• 接口：list_create/init/destroy/clear，list_push_front/back/insert_after，list_remove，list_get_at，list_find，list_replace_data，list_is_empty，list_length。

核心代码：数据结构定义

typedef struct list_node { struct list_node *prev; struct list_node *next; void *data; } list_node; typedef struct list { list_node sentinel; // 哨兵节点，prev/next 指向自身表示空表 size_t size; } list;

关键点解析：

• list_node包含双向指针prev/next和通用数据指针data（void *支持任意类型）
• list结构包含一个哨兵节点（非指针）和大小计数器，哨兵作为链表的一部分

核心代码：节点链接函数

插入操作的核心是link_between函数，它负责在prev和next之间插入新节点：

static void link_between(list_node *prev, list_node *next, list_node *node) { // prev <-> node <-> next node->prev = prev; node->next = next; prev->next = node; next->prev = node; }

关键点解析：

• 四步操作：设置新节点的prev/next，然后更新相邻节点的指针
• 无论插入位置（头/尾/中间），逻辑统一，无需特殊处理

核心代码：头插和尾插实现

list_node *list_push_front(list *lst, void *data) { if (lst == NULL) { return NULL; } list_node *node = alloc_node(data); if (node == NULL) { return NULL; } link_between(&lst->sentinel, lst->sentinel.next, node); lst->size++; return node; } list_node *list_push_back(list *lst, void *data) { if (lst == NULL) { return NULL; } list_node *node = alloc_node(data); if (node == NULL) { return NULL; } link_between(lst->sentinel.prev, &lst->sentinel, node); lst->size++; return node; }

关键点解析：

• 头插：在sentinel和sentinel.next之间插入
• 尾插：在sentinel.prev和sentinel之间插入
• 空表时sentinel.next == sentinel.prev == &sentinel，插入逻辑依然正确

核心代码：节点删除实现

static void unlink_node(list_node *node) { node->prev->next = node->next; node->next->prev = node->prev; node->prev = NULL; node->next = NULL; }

int list_remove(list *lst, list_node *node, void (*free_data)(void *)) { if (lst == NULL || node == NULL || node == &lst->sentinel) { return 0; } unlink_node(node); if (free_data != NULL) { free_data(node->data); } free(node); lst->size--; return 1; }

关键点解析：

• unlink_node先更新相邻节点指针，再清空被删节点的指针（防止误用）
• list_remove检查不能删除哨兵节点，支持自定义数据释放回调

3.3 输入/输出与验证

• 示例main使用scanf读取整数，下标从 0 开始。
• 删除/修改/查询前校验下标有效性。

核心代码：输入验证函数

static int read_int(const char *prompt, int *out) { if (prompt != NULL) { printf("%s", prompt); } if (scanf("%d", out) != 1) { // 清理残留输入 int ch; while ((ch = getchar()) != '\n' && ch != EOF) { } return 0; } return 1; }

关键点解析：

• scanf返回值检查：成功读取返回 1，失败返回 0
• 失败时清理输入缓冲区，避免残留字符影响后续输入

核心代码：按下标访问与边界检查

list_node *list_get_at(list *lst, size_t index) { if (lst == NULL || index >= lst->size) { return NULL; } list_node *cur = lst->sentinel.next; size_t i = 0; while (cur != &lst->sentinel && i < index) { cur = cur->next; i++; } return (cur == &lst->sentinel) ? NULL : cur; }

关键点解析：

• 先检查index >= size，避免无效访问
• 从sentinel.next开始遍历，循环条件同时检查是否到达哨兵和索引位置
• 返回NULL表示下标越界或链表为空

核心代码：删除操作中的验证示例

case 2: { // 删除 if (list_is_empty(lst)) { printf("列表为空，无可删除项。\n"); break; } int idx; if (!read_int("请输入要删除的下标(0 基): ", &idx) || idx < 0) { printf("输入无效，操作取消。\n"); break; } list_node *node = list_get_at(lst, (size_t)idx); if (node == NULL) { printf("未找到该下标的节点。\n"); break; } if (list_remove(lst, node, free)) { printf("删除成功。\n"); } else { printf("删除失败。\n"); } break; }

关键点解析：

• 先检查链表是否为空
• 验证输入是否为有效整数且非负
• 通过list_get_at获取节点，返回NULL表示下标无效
• 所有验证通过后才执行删除操作

3.4 优化与注意事项

• 使用自定义free_data释放存储数据，避免泄漏。
• UTF-8 控制台设置（Windows）防止中文提示乱码。
• 单线程示例，如需多线程需自行加锁。

核心代码：内存管理 - 清空链表

void list_clear(list *lst, void (*free_data)(void *)) { if (lst == NULL) { return; } list_node *cur = lst->sentinel.next; while (cur != &lst->sentinel) { list_node *next = cur->next; if (free_data != NULL) { free_data(cur->data); } free(cur); cur = next; } lst->sentinel.next = &lst->sentinel; lst->sentinel.prev = &lst->sentinel; lst->size = 0; }

关键点解析：

• 先保存next指针再释放节点，避免访问已释放内存
• 支持自定义free_data回调，灵活处理不同类型的数据释放
• 清空后重置哨兵指针和大小，恢复空表状态

核心代码：UTF-8 控制台设置

// 设置控制台为 UTF-8，避免中文输出乱码（主要针对 Windows 控制台） static void set_console_utf(void) { #ifdef _WIN32 SetConsoleOutputCP(65001); SetConsoleCP(65001); #endif }

关键点解析：

• 代码页 65001 对应 UTF-8 编码
• 使用条件编译#ifdef _WIN32，仅在 Windows 平台生效
• Linux/Mac 默认使用 UTF-8，无需额外设置

核心代码：程序退出时的资源清理

list_destroy(lst, free); return 0;

关键点解析：

• list_destroy内部调用list_clear清理所有节点
• 传入标准库的free函数释放整型数据（示例中每个整数单独分配）
• 最后释放链表结构本身，确保无内存泄漏

4. 关键技术点

• 哨兵循环链表的边界简化。
• 可插拔的内存释放回调。
• 菜单驱动主函数，集中演示 CRUD。

5. 复杂度/成本分析

• 查找/按下标访问：O(n)（线性遍历）。
• 插入/删除：O(1)（已定位节点后）。
• 额外空间：节点 O(1) 每元素，哨兵常数开销。

6. 运行示例

在link-list目录：

gcc list.c -o list_demo ./list_demo# Windows 运行 list_demo.exe

菜单项：1 添加、2 删除、3 修改、4 查询、5 打印、0 退出。

7. 完整代码/资源

7.1 list.h（头文件）

// 双向循环链表接口#ifndefLIST_H#defineLIST_H#include<stddef.h>typedefstructlist_node{structlist_node*prev;structlist_node*next;void*data;}list_node;typedefstructlist{list_node sentinel;// 哨兵节点，prev/next 指向自身表示空表size_tsize;}list;// 创建链表，返回堆上分配的链表指针；失败返回 NULLlist*list_create(void);// 初始化已分配的链表结构（使用栈或静态分配时调用）voidlist_init(list*lst);// 清空链表节点，free_data 用于释放 data，允许传入 NULL 表示不处理 datavoidlist_clear(list*lst,void(*free_data)(void*));// 销毁链表并释放节点，包含 data 的自定义释放voidlist_destroy(list*lst,void(*free_data)(void*));// 头插，返回新节点指针，失败返回 NULLlist_node*list_push_front(list*lst,void*data);// 尾插，返回新节点指针，失败返回 NULLlist_node*list_push_back(list*lst,void*data);// 在指定节点之后插入，pos 允许为 sentinel 表示头部前插，返回新节点或 NULLlist_node*list_insert_after(list*lst,list_node*pos,void*data);// 移除指定节点，free_data 用于释放 data，可为 NULL；成功返回 1，失败返回 0intlist_remove(list*lst,list_node*node,void(*free_data)(void*));// 判断是否为空intlist_is_empty(constlist*lst);// 获取节点数量size_tlist_length(constlist*lst);// 按下标获取节点（0 基），失败返回 NULLlist_node*list_get_at(list*lst,size_tindex);// 查找符合条件的首个节点，predicate 返回非 0 表示匹配；未找到返回 NULLlist_node*list_find(list*lst,int(*predicate)(void*data,void*ctx),void*ctx);// 替换指定节点的数据，free_old 用于释放旧 data（可为 NULL），成功返回 1，失败返回 0intlist_replace_data(list*lst,list_node*node,void*new_data,void(*free_old)(void*));#endif// LIST_H

7.2 list.c（实现文件）

// 双向循环链表实现#include"list.h"#include<stdlib.h>#include<stdio.h>#ifdef_WIN32#include<windows.h>#endifstaticlist_node*alloc_node(void*data){list_node*node=(list_node*)malloc(sizeof(list_node));if(node==NULL){returnNULL;}node->data=data;node->prev=NULL;node->next=NULL;returnnode;}staticvoidlink_between(list_node*prev,list_node*next,list_node*node){// prev <-> node <-> nextnode->prev=prev;node->next=next;prev->next=node;next->prev=node;}list*list_create(void){list*lst=(list*)malloc(sizeof(list));if(lst==NULL){returnNULL;}list_init(lst);returnlst;}voidlist_init(list*lst){if(lst==NULL){return;}lst->sentinel.next=&lst->sentinel;lst->sentinel.prev=&lst->sentinel;lst->sentinel.data=NULL;lst->size=0;}staticvoidunlink_node(list_node*node){node->prev->next=node->next;node->next->prev=node->prev;node->prev=NULL;node->next=NULL;}voidlist_clear(list*lst,void(*free_data)(void*)){if(lst==NULL){return;}list_node*cur=lst->sentinel.next;while(cur!=&lst->sentinel){list_node*next=cur->next;if(free_data!=NULL){free_data(cur->data);}free(cur);cur=next;}lst->sentinel.next=&lst->sentinel;lst->sentinel.prev=&lst->sentinel;lst->size=0;}voidlist_destroy(list*lst,void(*free_data)(void*)){if(lst==NULL){return;}list_clear(lst,free_data);free(lst);}list_node*list_push_front(list*lst,void*data){if(lst==NULL){returnNULL;}list_node*node=alloc_node(data);if(node==NULL){returnNULL;}link_between(&lst->sentinel,lst->sentinel.next,node);lst->size++;returnnode;}list_node*list_push_back(list*lst,void*data){if(lst==NULL){returnNULL;}list_node*node=alloc_node(data);if(node==NULL){returnNULL;}link_between(lst->sentinel.prev,&lst->sentinel,node);lst->size++;returnnode;}list_node*list_insert_after(list*lst,list_node*pos,void*data){if(lst==NULL||pos==NULL){returnNULL;}// 允许 pos 为 sentinel，实现头部插入等场景list_node*node=alloc_node(data);if(node==NULL){returnNULL;}link_between(pos,pos->next,node);lst->size++;returnnode;}intlist_remove(list*lst,list_node*node,void(*free_data)(void*)){if(lst==NULL||node==NULL||node==&lst->sentinel){return0;}unlink_node(node);if(free_data!=NULL){free_data(node->data);}free(node);lst->size--;return1;}intlist_is_empty(constlist*lst){returnlst==NULL||lst->size==0;}size_tlist_length(constlist*lst){returnlst==NULL?0:lst->size;}list_node*list_get_at(list*lst,size_tindex){if(lst==NULL||index>=lst->size){returnNULL;}list_node*cur=lst->sentinel.next;size_ti=0;while(cur!=&lst->sentinel&&i<index){cur=cur->next;i++;}return(cur==&lst->sentinel)?NULL:cur;}list_node*list_find(list*lst,int(*predicate)(void*data,void*ctx),void*ctx){if(lst==NULL||predicate==NULL){returnNULL;}list_node*cur=lst->sentinel.next;while(cur!=&lst->sentinel){if(predicate(cur->data,ctx)){returncur;}cur=cur->next;}returnNULL;}intlist_replace_data(list*lst,list_node*node,void*new_data,void(*free_old)(void*)){if(lst==NULL||node==NULL||node==&lst->sentinel){return0;}if(free_old!=NULL){free_old(node->data);}node->data=new_data;return1;}// 设置控制台为 UTF-8，避免中文输出乱码（主要针对 Windows 控制台）staticvoidset_console_utf(void){#ifdef_WIN32SetConsoleOutputCP(65001);SetConsoleCP(65001);#endif}// 以下为示例主函数，便于使用 GCC 直接编译运行演示// gcc list.c -o list_demo// 程序演示：读取用户输入的数据集，将其存入双向循环链表并打印staticvoidprint_int_list(constlist*lst){if(lst==NULL||list_is_empty(lst)){printf("列表为空。\n");return;}constlist_node*cur=lst->sentinel.next;printf("列表内容: ");while(cur!=&lst->sentinel){int*val=(int*)cur->data;printf("%d ",val!=NULL?*val:0);cur=cur->next;}printf("\n");}staticintread_int(constchar*prompt,int*out){if(prompt!=NULL){printf("%s",prompt);}if(scanf("%d",out)!=1){// 清理残留输入intch;while((ch=getchar())!='\n'&&ch!=EOF){}return0;}return1;}staticint*alloc_int_value(intv){int*p=(int*)malloc(sizeof(int));if(p!=NULL){*p=v;}returnp;}staticvoidprint_menu(void){printf("\n===== 双向循环链表演示 =====\n");printf("1. 添加（尾插）\n");printf("2. 删除（按下标）\n");printf("3. 修改（按下标）\n");printf("4. 查询（按下标）\n");printf("5. 打印全部\n");printf("0. 退出\n");}intmain(void){set_console_utf();list*lst=list_create();if(lst==NULL){fprintf(stderr,"创建链表失败。\n");return1;}intrunning=1;while(running){print_menu();intchoice=-1;if(!read_int("请选择操作: ",&choice)){printf("输入无效，请重试。\n");continue;}switch(choice){case1:{// 添加intvalue;if(!read_int("请输入要添加的整数: ",&value)){printf("输入无效，操作取消。\n");break;}int*p=alloc_int_value(value);if(p==NULL){printf("内存分配失败，添加中止。\n");break;}if(list_push_back(lst,p)==NULL){printf("插入节点失败，添加中止。\n");free(p);break;}printf("添加成功。\n");break;}case2:{// 删除if(list_is_empty(lst)){printf("列表为空，无可删除项。\n");break;}intidx;if(!read_int("请输入要删除的下标(0 基): ",&idx)||idx<0){printf("输入无效，操作取消。\n");break;}list_node*node=list_get_at(lst,(size_t)idx);if(node==NULL){printf("未找到该下标的节点。\n");break;}if(list_remove(lst,node,free)){printf("删除成功。\n");}else{printf("删除失败。\n");}break;}case3:{// 修改if(list_is_empty(lst)){printf("列表为空，无可修改项。\n");break;}intidx;if(!read_int("请输入要修改的下标(0 基): ",&idx)||idx<0){printf("输入无效，操作取消。\n");break;}list_node*node=list_get_at(lst,(size_t)idx);if(node==NULL){printf("未找到该下标的节点。\n");break;}intnew_val;if(!read_int("请输入新的整数值: ",&new_val)){printf("输入无效，操作取消。\n");break;}int*p=alloc_int_value(new_val);if(p==NULL){printf("内存分配失败，修改中止。\n");break;}if(list_replace_data(lst,node,p,free)){printf("修改成功。\n");}else{printf("修改失败。\n");free(p);}break;}case4:{// 查询if(list_is_empty(lst)){printf("列表为空。\n");break;}intidx;if(!read_int("请输入要查询的下标(0 基): ",&idx)||idx<0){printf("输入无效，操作取消。\n");break;}list_node*node=list_get_at(lst,(size_t)idx);if(node==NULL){printf("未找到该下标的节点。\n");break;}int*val=(int*)node->data;printf("下标 %d 的值为: %d\n",idx,val!=NULL?*val:0);break;}case5:{// 打印全部print_int_list(lst);break;}case0:running=0;break;default:printf("无效选项，请重试。\n");break;}}list_destroy(lst,free);return0;}

7.3 代码仓库

完整代码已上传至 GitHub/Gitee，可直接下载使用。项目地址：[项目链接]

编译命令：

gcc list.c -o list_demo

运行：

./list_demo# Linux/Maclist_demo.exe# Windows

8. 总结

该实现以哨兵双向循环链表为基础，提供完整 CRUD 接口与可运行示例，适合作为学习模板或嵌入小型项目。根据业务可替换数据类型与释放回调，并在多线程场景加锁。

9. 三连提示

如果对你有帮助，欢迎点赞、收藏、关注。***