当前位置： 首页 > news >正文

双向链表：从结构到增删改查

news 2026/3/26 18:14:50

一、双向链表：比单向链表更灵活的线性结构

1.1 双向链表的核心结构

双向链表的每个节点包含三个部分：

  • data：数据域，存储业务数据；
  • next：后继指针，指向下一个节点；
  • prev：前驱指针，指向上一个节点。

用 C 语言结构体定义：

typedef int data_t; // 数据类型别名，方便修改 // 双向链表节点结构 typedef struct node { data_t data; // 数据域 struct node *next; // 后继指针（向后） struct node *prev; // 前驱指针（向前） } node_t;

核心优势：

  • 支持正向遍历（head → ... → tail）和逆向遍历（tail → ... → head）；
  • 删除节点时无需知道前驱节点（prev直接指向它），操作更高效。

二、双向链表的基础操作：创建 + 增删改查

2.1 1. 创建空双向链表

空链表仅包含一个头节点，prev和next都设为NULL：

// 创建空双向链表（返回头节点） node_t *creat_doublist(void) { node_t *phead = (node_t *)malloc(sizeof(node_t)); if (phead == NULL) { printf("内存分配失败！\n"); return NULL; } phead->prev = NULL; // 头节点前驱为NULL phead->next = NULL; // 头节点后继为NULL return phead; }

2.2 2. 头插法：在链表头部插入节点

头插法是双向链表最基础的插入方式，新节点直接插在头节点后：

// 头插法：在链表头部插入数据 void doublist_insert_head(node_t *phead, data_t data) { // step1: 创建新节点并赋值 node_t *p_new = (node_t *)malloc(sizeof(node_t)); p_new->data = data; p_new->prev = NULL; p_new->next = NULL; // step2: 链接指针（核心步骤） p_new->next = phead->next; // 新节点后继指向原首节点 p_new->prev = phead; // 新节点前驱指向头节点 phead->next = p_new; // 头节点后继指向新节点（新节点成为首节点） // 如果原链表非空，原首节点的前驱要指向新节点 if (p_new->next != NULL) { p_new->next->prev = p_new; } }

指针变化图解：

原链表：head ↔ 2 ↔ 1 ↔ 3 → NULL 插入后：head ↔ 4 ↔ 2 ↔ 1 ↔ 3 → NULL

2.3 3. 尾插法：在链表尾部插入节点

尾插法需要先找到尾节点，再将新节点链接到尾部：

// 尾插法：在链表尾部插入数据 void doublist_insert_tail(node_t *phead, data_t data) { // step1: 创建新节点并赋值 node_t *p_new = (node_t *)malloc(sizeof(node_t)); p_new->data = data; p_new->prev = NULL; p_new->next = NULL; // step2: 找到尾节点 node_t *p = phead; while (p->next != NULL) { p = p->next; } // step3: 链接指针 p_new->next = p->next; // 新节点后继为NULL（尾节点特征） p_new->prev = p; // 新节点前驱指向尾节点 p->next = p_new; // 原尾节点后继指向新节点 }

2.4 4. 遍历打印：正向 + 逆向

双向链表支持两种遍历方式：

// 正向遍历打印（从首节点到尾节点） void print_doublist(node_t *phead) { if (phead->next == NULL) { printf("链表为空！\n"); return; } node_t *p = phead->next; printf("正向遍历："); while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } // 逆向遍历打印（从尾节点到头节点） void print_doublist_reverse(node_t *phead) { if (phead->next == NULL) { printf("链表为空！\n"); return; } // step1: 先找到尾节点 node_t *p = phead; while (p->next != NULL) { p = p->next; } // step2: 从尾节点逆向打印到头节点 printf("逆向遍历："); while (p->prev != NULL) { // 直到遇到头节点 printf("%d ", p->data); p = p->prev; } printf("\n"); }

2.5 5. 查找节点：根据数据找节点

// 查找节点：根据data值查找，返回节点地址，未找到返回NULL node_t *doublist_find_key(node_t *phead, data_t data) { node_t *p = phead->next; while (p != NULL) { if (p->data == data) { return p; // 找到目标节点 } p = p->next; } return NULL; // 未找到 }

2.6 6. 修改节点：根据旧值修改为新值

// 修改节点：将old_data修改为new_data，返回修改后的节点 node_t *doublist_update_key(node_t *phead, data_t old_data, data_t new_data) { node_t *p = doublist_find_key(phead, old_data); if (p == NULL) { printf("未找到要修改的节点！\n"); return NULL; } p->data = new_data; return p; }

2.7 7. 删除节点：根据数据删除节点

双向链表删除节点的核心是修改前后节点的指针：

// 删除节点：根据data值删除节点 int doublist_delete_key(node_t *phead, data_t data) { node_t *p = doublist_find_key(phead, data); if (p == NULL) { printf("未找到要删除的节点！\n"); return -1; } // step1: 前驱节点指向后继节点 p->prev->next = p->next; // step2: 如果不是尾节点，后继节点的前驱要指向当前节点的前驱 if (p->next != NULL) { p->next->prev = p->prev; } // step3: 释放节点内存 free(p); return 0; }

2.8 8. 统计链表长度

// 统计链表有效节点个数 int length(node_t *phead) { int count = 0; node_t *p = phead->next; while (p != NULL) { count++; p = p->next; } return count; }

三、完整测试代码

#include <stdio.h> #include <stdlib.h> typedef int data_t; typedef struct node { data_t data; struct node *next; struct node *prev; } node_t; // 1. 创建空链表 node_t *creat_doublist(void) { node_t *phead = (node_t *)malloc(sizeof(node_t)); phead->prev = NULL; phead->next = NULL; return phead; } // 2. 头插法 void doublist_insert_head(node_t *phead, data_t data) { node_t *p_new = (node_t *)malloc(sizeof(node_t)); p_new->data = data; p_new->prev = NULL; p_new->next = NULL; p_new->next = phead->next; p_new->prev = phead; phead->next = p_new; if (p_new->next != NULL) { p_new->next->prev = p_new; } } // 3. 尾插法 void doublist_insert_tail(node_t *phead, data_t data) { node_t *p_new = (node_t *)malloc(sizeof(node_t)); p_new->data = data; p_new->prev = NULL; p_new->next = NULL; node_t *p = phead; while (p->next != NULL) { p = p->next; } p_new->next = p->next; p_new->prev = p; p->next = p_new; } // 4. 正向打印 void print_doublist(node_t *phead) { if (phead->next == NULL) { printf("链表为空！\n"); return; } node_t *p = phead->next; printf("正向遍历："); while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } // 5. 逆向打印 void print_doublist_reverse(node_t *phead) { if (phead->next == NULL) { printf("链表为空！\n"); return; } node_t *p = phead; while (p->next != NULL) { p = p->next; } printf("逆向遍历："); while (p->prev != NULL) { printf("%d ", p->data); p = p->prev; } printf("\n"); } // 6. 查找节点 node_t *doublist_find_key(node_t *phead, data_t data) { node_t *p = phead->next; while (p != NULL) { if (p->data == data) { return p; } p = p->next; } return NULL; } // 7. 修改节点 node_t *doublist_update_key(node_t *phead, data_t old_data, data_t new_data) { node_t *p = doublist_find_key(phead, old_data); if (p == NULL) { return NULL; } p->data = new_data; return p; } // 8. 删除节点 int doublist_delete_key(node_t *phead, data_t data) { node_t *p = doublist_find_key(phead, data); if (p == NULL) { return -1; } p->prev->next = p->next; if (p->next != NULL) { p->next->prev = p->prev; } free(p); return 0; } // 9. 统计长度 int length(node_t *phead) { int count = 0; node_t *p = phead->next; while (p != NULL) { count++; p = p->next; } return count; } // 10. 销毁链表 void doublist_destroy(node_t *phead) { node_t *p = phead; while (p != NULL) { node_t *temp = p; p = p->next; free(temp); } } // 测试主函数 int main() { node_t *phead = creat_doublist(); // 头插法插入数据 doublist_insert_head(phead, 3); doublist_insert_head(phead, 1); doublist_insert_head(phead, 2); printf("链表长度：%d\n", length(phead)); // 输出3 print_doublist(phead); // 正向：2 1 3 print_doublist_reverse(phead); // 逆向：3 1 2 // 尾插法插入数据 doublist_insert_tail(phead, 4); print_doublist(phead); // 正向：2 1 3 4 // 修改数据 doublist_update_key(phead, 1, 10); print_doublist(phead); // 正向：2 10 3 4 // 删除数据 doublist_delete_key(phead, 10); print_doublist(phead); // 正向：2 3 4 doublist_destroy(phead); return 0; }

四、双向链表 vs 单向链表：核心区别

特性单向链表双向链表
指针数量1 个（next）2 个（next+prev）
遍历方向仅正向正向 + 逆向
删除节点需要知道前驱节点直接通过prev找到前驱
内存开销小大（每个节点多一个指针）
适用场景简单遍历、栈实现需要双向操作、队列实现、缓存设计

五、总结与学习建议

  1. 核心抓住指针操作：双向链表的关键是prev和next的链接，插入 / 删除时一定要画图理解指针变化；
  2. 边界情况要注意：
    • 头插 / 尾插时，空链表和非空链表的处理逻辑不同；
    • 删除尾节点时，next为NULL，无需处理后继节点的prev；
  3. 实践建议：
    • 先手写插入 / 删除的步骤（画指针流向），再敲代码；
    • 测试边界情况：空链表、单节点链表、首尾节点操作；
    • 结合 LeetCode 刷题，比如「回文链表」「链表排序」等题目，双向链表能简化实现。
http://www.jsqmd.com/news/512008/

相关文章：

  • Vue3项目里用monaco-editor做个在线代码编辑器（带复制重置功能）
  • TIM+PWM输出+输入捕获测 频率+占空比（HAL库）
  • SEO_掌握这几个SEO技巧，让你的流量快速增长
  • Python信贷冷启动信用风险评估：WOE编码、IV筛选、代价敏感学习与逻辑回归稀疏样本建模 | 附代码数据
  • 别再手动复制了！用Vxe-Table的exportData方法，5分钟搞定Vue项目表格数据导出（含PDF/XLSX避坑指南）
  • 9.9元包月，告别Token焦虑，零配置，7×24 在线，火山引擎 ArkClaw “云端OpenClaw”龙虾私人助理，支持ClawHub技能插件
  • 【Rust面试问题】所有权机制
  • 黑丝空姐-造相Z-Turbo实战体验：输入文字秒出图片，效果惊艳
  • 解决PyTorch 2.6兼容性问题：YOLOv8部署避坑指南
  • ISO 9001认证到底有啥用？
  • Pixel Dimension Fissioner效果展示：技术博客标题的SEO友好型+传播力双强化裂变
  • 大模型提示词工程实战：从入门到高效应用
  • FastJson JSONPath 路径取值用法与场景总结
  • SEO_从零开始，手把手教你制定SEO执行方案（199 ）
  • 西门子伺服分拣机西门子S7-1200 PLC程序，，有自己录4平详细讲解项目程序，4平已保护 ...
  • 2026哈尔滨汽车维修性价比排名，哈尔滨连顺汽车维修钣金喷漆价格合理吗 - 工业品网
  • VideoAgentTrek Screen Filter 与物联网结合：智能终端屏幕状态监控系统
  • 2026年上海境易达出国靠谱吗，深入分析其移民服务实力 - myqiye
  • 使用 Dify 快速构建对话式工作流：从零打造会议室预约智能体
  • Dify Token用量失控？3步完成轻量级监控插件部署，含OpenTelemetry埋点配置与成本阈值告警模板
  • 搞TC397的AUTOSAR？来点真实力
  • 为什么我们的大脑是“推理机”而非“硬盘”：关于学习、记忆与智慧的认知科学深度解析.
  • 颠覆“全职带娃轻松”，核算时间精力，机会成本，颠覆偏见，输出家庭劳动价值量化表。
  • 2026年上海境易达出国推荐吗，参考其客户评价与行业口碑 - mypinpai
  • 在Windows上找回Mac触控板体验：开源驱动如何打破平台壁垒？
  • 通信行业某国企数据岗员工CDA数据分析师备考经验：多元策略助你高效通关
  • DigitalOcean 亮相 NVIDIA GTC 2026：为智能体时代打造 AI 工厂
  • Z-Image-Turbo_Sugar脸部Lora赋能内容创作：短视频博主头像批量生成方案
  • 2026功率预测生死局：MKAN多尺度网络如何将光伏预测误差斩落马下？
  • 如何为本地开发环境配置 HTTPS 以对接微信登录