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

C语言数据结构之双向链表

ds 2025/9/2 8:02:04

目录

一、双向链表的核心结构：带头双向循环链表

1.1 什么是 “哨兵位”？

1.2 带头双向循环链表的完整结构

二、双向链表的完整实现（C 语言）

2.1 辅助函数：创建新节点（LTBuyNode）

2.2 初始化链表（LTInit）

2.3 销毁链表（LTDestroy）

2.4 打印链表（LTPrint）

2.5 判断链表是否为空（LTEmpty）

2.6 尾部插入（LTPushBack）

2.7 头部插入（LTPushFront）

2.8 头部删除（LTPopFront）

2.9 尾部删除（LTPopBack）

2.10 查找节点（LTFind）

2.11 指定位置插入（LTInsert）

2.12 指定位置删除（LTErase）

三、双向链表的测试实例（test.c）

四、顺序表与双向链表的深度对比

4.1 核心差异对比表

4.2 应用场景选择建议

五、扩展：链表与数组的 “移除元素” 实现对比

5.1 数组移除元素（removeElement）

5.2 双向链表移除元素

5.3 两种结构移除元素的核心差异

六、总结

在数据结构的学习中，链表是与顺序表并列的重要线性表结构，而双向链表作为链表的进阶形式，凭借其前后双向访问的特性，在诸多场景中展现出比单链表更灵活的优势。本文将从双向链表的核心结构入手，完整讲解其实现细节，对比顺序表与双向链表的差异，并通过实例代码演示双向链表的实际应用，帮助读者全面掌握这一数据结构。

一、双向链表的核心结构：带头双向循环链表

双向链表的结构有多种形式，其中带头双向循环链表是实现最便捷、实用性最高的版本。在深入结构细节前，需先明确一个关键概念 ——“哨兵位”。

1.1 什么是 “哨兵位”？

在单链表中，我们常将第一个存储有效数据的节点称为 “头节点”，但这种称呼并不严谨。而在带头双向循环链表中，“头节点” 的真正身份是哨兵位节点：

  • 哨兵位节点不存储任何有效数据，仅作为链表的 “标志位” 存在。
  • 其核心作用是避免遍历循环链表时出现死循环，同时统一链表的插入、删除操作逻辑（无需单独处理表头、表尾的特殊情况）。

1.2 带头双向循环链表的完整结构

该结构的核心特征可概括为 “双向” 与 “循环”：

  • 双向：每个节点包含两个指针，prev指向前驱节点，next指向后继节点，实现前后双向访问。
  • 循环：链表的尾节点的next指针指向哨兵位，哨兵位的prev指针指向尾节点，形成闭合循环。

结构示意图如下（head为哨兵位节点）：

head（哨兵位）↓    ↑
prev  next↓    ↑
节点1 ←→ 节点2 ←→ 节点3 ←→ ... ←→ 尾节点

节点的结构体定义（C 语言）：

// 定义双向链表节点的数据类型
typedef int LTDataType;// 双向链表节点结构体
typedef struct ListNode
{struct ListNode* prev;  // 指向前驱节点的指针struct ListNode* next;  // 指向后继节点的指针LTDataType data;        // 存储节点的有效数据
} LTNode;

二、双向链表的完整实现（C 语言）

双向链表的实现围绕 “初始化、销毁、增删查改、判空、打印” 等核心操作展开。以下基于带头双向循环链表结构，逐一讲解实现细节，并附上完整代码。

2.1 辅助函数：创建新节点（LTBuyNode）

所有插入操作都需要先创建新节点，因此封装一个通用的 “创建节点” 函数，避免代码冗余：

// 创建一个新的双向链表节点，数据为x，初始时prev和next均指向自身
LTNode* LTBuyNode(LTDataType x)
{// 为新节点分配内存LTNode* node = (LTNode*)malloc(sizeof(LTNode));// 检查内存分配是否成功if (node == NULL){perror("malloc failed");  // 打印错误信息exit(-1);                 // 终止程序（内存分配失败属于严重错误）}// 初始化节点数据和指针node->data = x;node->prev = node;  // 初始时自环（便于后续插入逻辑统一）node->next = node;return node;
}

2.2 初始化链表（LTInit）

初始化的核心是创建哨兵位节点，此时链表仅包含哨兵位，且哨兵位的prev和next均指向自身：

// 初始化双向链表，返回哨兵位节点的地址
LTNode* LTInit()
{// 创建哨兵位节点，数据设为-1（无实际意义，仅占位）LTNode* phead = LTBuyNode(-1);return phead;
}

2.3 销毁链表（LTDestroy）

链表的销毁需要释放所有节点（包括哨兵位），避免内存泄漏。由于是循环结构，需从哨兵位的下一个节点开始遍历，逐个释放：

// 销毁双向链表，释放所有节点内存
void LTDestroy(LTNode* phead)
{assert(phead);  // 断言：确保phead不为空（避免传入无效指针）LTNode* pcur = phead->next;  // 从哨兵位的下一个节点开始遍历while (pcur != phead)        // 循环终止条件：回到哨兵位（所有节点已遍历）{LTNode* next = pcur->next;  // 先保存下一个节点的地址（避免释放后找不到）free(pcur);                 // 释放当前节点pcur = next;                // 移动到下一个节点}free(phead);  // 最后释放哨兵位节点phead = NULL; // 将指针置空（避免野指针）
}

2.4 打印链表（LTPrint）

打印链表时，从哨兵位的下一个节点开始，遍历到哨兵位结束（避免打印哨兵位的无效数据）：

// 打印双向链表的所有有效数据
void LTPrint(LTNode* phead)
{assert(phead);  // 确保phead不为空LTNode* pcur = phead->next;printf("哨兵位 -> ");while (pcur != phead){printf("%d -> ", pcur->data);  // 打印当前节点数据pcur = pcur->next;             // 移动到下一个节点}printf("哨兵位\n");  // 打印结尾，体现循环结构
}

2.5 判断链表是否为空（LTEmpty）

链表为空的标志是：哨兵位的next指针指向自身（无任何有效节点）：

// 判断双向链表是否为空（无有效节点），空则返回true，否则返回false
bool LTEmpty(LTNode* phead)
{assert(phead);// 哨兵位的next指向自身 → 无有效节点return phead->next == phead;
}

2.6 尾部插入（LTPushBack）

尾部插入的核心是找到尾节点（哨兵位的prev指向尾节点），然后将新节点插入到尾节点与哨兵位之间：

// 在双向链表尾部插入数据x
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);  // 确保phead不为空（哨兵位存在）LTNode* newnode = LTBuyNode(x);  // 创建新节点LTNode* tail = phead->prev;      // 找到尾节点（哨兵位的前驱）// 调整指针，插入新节点tail->next = newnode;      // 尾节点的next指向新节点newnode->prev = tail;      // 新节点的prev指向尾节点newnode->next = phead;     // 新节点的next指向哨兵位phead->prev = newnode;     // 哨兵位的prev指向新节点（新节点成为新尾）
}

2.7 头部插入（LTPushFront）

头部插入是在哨兵位与第一个有效节点之间插入新节点，直接利用哨兵位的next指针即可定位插入位置：

// 在双向链表头部（哨兵位之后）插入数据x
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);LTNode* first = phead->next;  // 找到第一个有效节点（哨兵位的后继）// 调整指针，插入新节点phead->next = newnode;      // 哨兵位的next指向新节点newnode->prev = phead;      // 新节点的prev指向哨兵位newnode->next = first;      // 新节点的next指向原第一个节点first->prev = newnode;      // 原第一个节点的prev指向新节点
}

2.8 头部删除（LTPopFront）

头部删除需先判断链表是否为空，然后删除哨兵位后的第一个有效节点：

// 删除双向链表头部（哨兵位之后）的第一个有效节点
void LTPopFront(LTNode* phead)
{// 断言：链表不为空（哨兵位存在且有有效节点）assert(phead && !LTEmpty(phead));LTNode* del = phead->next;      // 找到要删除的节点（第一个有效节点）LTNode* second = del->next;     // 保存删除节点的下一个节点// 调整指针，跳过删除节点phead->next = second;      // 哨兵位的next指向原第二个节点second->prev = phead;      // 原第二个节点的prev指向哨兵位free(del);  // 释放删除节点的内存del = NULL; // 避免野指针
}

2.9 尾部删除（LTPopBack）

尾部删除与头部删除逻辑对称，删除哨兵位的前驱节点（尾节点）：

// 删除双向链表尾部的节点
void LTPopBack(LTNode* phead)
{assert(phead && !LTEmpty(phead));LTNode* del = phead->prev;      // 找到要删除的尾节点LTNode* prevTail = del->prev;   // 保存尾节点的前驱节点// 调整指针，跳过删除节点prevTail->next = phead;      // 原尾节点的前驱指向哨兵位phead->prev = prevTail;      // 哨兵位的prev指向原尾节点的前驱free(del);del = NULL;
}

2.10 查找节点（LTFind）

遍历链表，查找数据等于x的节点，找到则返回节点地址，未找到则返回NULL：

// 在双向链表中查找数据x，找到返回节点地址，未找到返回NULL
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;  // 找到目标节点，返回地址}pcur = pcur->next;}return NULL;  // 遍历结束未找到
}

2.11 指定位置插入（LTInsert）

在指定节点pos的后面插入新节点，利用双向链表的前后指针，无需遍历即可完成插入：

// 在指定节点pos的后面插入数据x
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);  // 确保pos是有效的节点地址LTNode* newnode = LTBuyNode(x);LTNode* posNext = pos->next;  // 保存pos的下一个节点// 调整指针，插入新节点pos->next = newnode;      // pos的next指向新节点newnode->prev = pos;      // 新节点的prev指向posnewnode->next = posNext;  // 新节点的next指向posNextposNext->prev = newnode;  // posNext的prev指向新节点
}

2.12 指定位置删除（LTErase）

删除指定节点pos，同样利用双向指针直接调整，无需遍历：

// 删除指定节点pos
void LTErase(LTNode* pos)
{assert(pos);  // 确保pos有效LTNode* posPrev = pos->prev;  // 保存pos的前驱节点LTNode* posNext = pos->next;  // 保存pos的后继节点// 调整指针，跳过pos节点posPrev->next = posNext;  // 前驱节点的next指向后继节点posNext->prev = posPrev;  // 后继节点的prev指向前驱节点free(pos);  // 释放pos节点内存pos = NULL; // 避免野指针
}

三、双向链表的测试实例（test.c）

为验证双向链表的所有操作是否正确，编写测试代码，涵盖初始化、插入、查找、删除、销毁等流程：

#include "List.h"  // 包含双向链表的头文件int main()
{// 1. 初始化链表LTNode* plist = LTInit();printf("初始化后链表（空）：");LTPrint(plist);// 2. 尾部插入4个元素：1、2、3、4LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);printf("尾部插入1、2、3、4后：");LTPrint(plist);  // 预期输出：哨兵位 -> 1 -> 2 -> 3 -> 4 -> 哨兵位// 3. 头部插入元素0LTPushFront(plist, 0);printf("头部插入0后：");LTPrint(plist);  // 预期输出：哨兵位 -> 0 -> 1 -> 2 -> 3 -> 4 -> 哨兵位// 4. 查找元素3，并在其后面插入30LTNode* find = LTFind(plist, 3);if (find != NULL){LTInsert(find, 30);printf("在3后面插入30后：");LTPrint(plist);  // 预期输出：... -> 3 -> 30 -> 4 -> ...}// 5. 删除元素30if (find != NULL){LTErase(find->next);  // find->next是30的节点printf("删除30后：");LTPrint(plist);  // 预期输出：... -> 3 -> 4 -> ...}// 6. 头部删除和尾部删除LTPopFront(plist);LTPopBack(plist);printf("头部删除和尾部删除后：");LTPrint(plist);  // 预期输出：哨兵位 -> 1 -> 2 -> 3 -> 哨兵位// 7. 销毁链表LTDestroy(plist);plist = NULL;  // 避免野指针return 0;
}

四、顺序表与双向链表的深度对比

顺序表（如动态数组）和双向链表是两种常用的线性表结构，二者在存储空间、访问效率、插入删除效率等方面差异显著，选择需结合具体应用场景。

4.1 核心差异对比表

对比维度顺序表（动态数组）双向链表（带头循环）
存储空间物理上连续（依赖数组）逻辑上连续，物理上不连续（节点分散）
随机访问支持 O (1)（通过下标直接访问）不支持，需遍历 O (N)
插入 / 删除效率任意位置插入 / 删除需搬移元素，O (N)已知位置时仅需调整指针，O (1)
容量管理动态扩容（可能存在内存浪费）无容量概念，按需分配节点
内存利用率扩容后可能有空闲内存（如 2 倍扩容）无空闲内存，每个节点仅存储必要数据
缓存友好性好（连续存储，命中缓存概率高）差（节点分散，缓存命中率低）

4.2 应用场景选择建议

  • 优先选顺序表：当需求以 “频繁访问”（如随机查询、遍历）为主，插入 / 删除仅在尾部进行时（如日志存储、数组排序），顺序表的 O (1) 访问和缓存优势更明显。
  • 优先选双向链表：当需求以 “频繁插入 / 删除” 为主（如链表中部插入、删除），且无需随机访问时（如链表式队列、栈、LRU 缓存），双向链表的 O (1) 插入 / 删除效率更优。

五、扩展：链表与数组的 “移除元素” 实现对比

为进一步理解链表与数组的差异，我们对比 “移除元素” 功能的实现（分别基于单链表和数组）。

5.1 数组移除元素（removeElement）

数组移除元素需通过 “双指针” 实现，本质是 “覆盖无效元素”，时间复杂度 O (N)：

// 移除数组nums中值为val的元素，返回剩余元素个数
int removeElement(int* nums, int numsSize, int val)
{int src = 0;  // 遍历指针：寻找非val的元素int dst = 0;  // 目标指针：指向待覆盖的位置while (src < numsSize){if (nums[src] != val){nums[dst] = nums[src];  // 用非val元素覆盖dst位置dst++;                  // 目标指针后移，准备下一次覆盖}src++;                      // 遍历指针后移，继续检查下一个元素}return dst;  // dst的值即为剩余有效元素的个数
}

数组移除元素的核心局限在于物理存储连续：即使找到需移除的元素，也需通过后续元素 “向前覆盖” 来实现 “移除” 效果，若数组长度较大，大量元素的搬移会导致效率降低，这与顺序表 “任意位置插入删除效率低” 的特性一致。

5.2 双向链表移除元素

基于本文讲解的带头双向循环链表，移除指定值元素的操作可结合LTFind与LTErase函数实现，时间复杂度取决于查找过程（遍历链表为 O (N)），移除操作本身仅需调整指针（O (1)）：

// 移除双向链表中所有值为val的元素
void LTRemoveVal(LTNode* phead, LTDataType val)
{assert(phead);  // 确保哨兵位节点有效LTNode* pcur = phead->next;  // 从第一个有效节点开始遍历while (pcur != phead)  // 遍历终止条件：回到哨兵位{LTNode* nextNode = pcur->next;  // 提前保存下一个节点地址（避免删除后丢失）if (pcur->data == val){LTErase(pcur);  // 调用已有删除函数，调整指针并释放节点}pcur = nextNode;  // 遍历到下一个节点}
}

双向链表移除元素的优势在于无需搬移元素：找到目标节点后，仅需通过prev和next指针连接其前驱与后继节点，再释放目标节点内存即可，完全规避了数组 “元素覆盖” 的效率问题，这也体现了链表 “任意位置插入删除灵活” 的核心特性。

5.3 两种结构移除元素的核心差异

对比维度数组（顺序表）双向链表
实现核心双指针覆盖无效元素调整节点指针 + 释放目标节点内存
时间复杂度O (N)（遍历 + 元素覆盖）O (N)（遍历查找）+ O (1)（移除操作）
空间复杂度O (1)（原地操作）O (1)（仅需指针临时存储）
关键局限元素搬移导致效率损耗需提前遍历查找目标节点（无随机访问）

六、总结

本文系统梳理了双向链表的核心知识：首先明确了带头双向循环链表的结构，重点区分了 “哨兵位” 与单链表 “头节点” 的差异，阐述了哨兵位避免死循环、统一操作逻辑的关键作用；其次围绕专题给出的函数声明，讲解了双向链表初始化、增删查改、销毁等操作的实现逻辑，突出其 “双向指针调整” 的核心优势；最后通过与顺序表的对比，明确了二者在存储空间、效率、应用场景上的差异。

双向链表的核心价值在于解决了单链表 “只能单向访问” 和顺序表 “插入删除效率低” 的问题，尤其适合频繁在任意位置进行插入删除的场景。掌握其结构设计与实现逻辑，不仅能提升数据结构的应用能力，也能为后续更复杂的链表或数据结构学习奠定基础。

http://www.xdnf.cn/news/19706.html

相关文章：

  • 详细介绍 JMeter 性能测试
  • Mac idea 格式化代码快捷键
  • 第 94 场周赛：叶子相似的树、模拟行走机器人、爱吃香蕉的珂珂、最长的斐波那契子序列的长度
  • 【C++】什么是智能指针及应用
  • 六大关键步骤：用MES系统重构生产计划管理闭环
  • 从能耗黑洞到精准智控：ASCB2智慧空开重构高校宿舍用电能效模型
  • 均值滤波和中值滤波的简介、C语言实现和实测
  • Adobe Photoshop 2025 最新下载安装教程，附PS2025下载
  • 【项目】多模态RAG必备神器—olmOCR重塑PDF文本提取格局
  • 智慧水利系统解决方案-水利信息化平台
  • linux连接服务器sftp无法输入中文
  • 直播预告 | Excelize 跨语言实战
  • 代码随想录二刷之“回溯”～GO
  • Linux系统中yum包管理器安装软件时遇到的网络连接问题
  • 线上API接口响应慢？一套高效排查与定位问题的心法
  • 【frontend】w3c的发展历史ToDo
  • 基于Springboot + vue3实现的时尚美妆电商网站
  • MySQL 之索引的结构、分类与语法
  • 四个典型框架对比
  • 在 Unity 中调用腾讯云机器翻译
  • 一个好的智能体框架应该是什么样子
  • Activiti流程引擎的用户体系与MIS系统的用户体系打通
  • 一、Git与Gitee常见问题解答
  • 深度学习跨领域应用探索：从技术落地到行业变革
  • pcl案例2 叶片与根茎的分离step2
  • MyBatis 性能优化最佳实践：从 SQL 到连接池的全面调优指南
  • Java网络编程基础 Socket通信入门指南
  • 机器视觉软件--VisionPro、Visual Master，Halcon 和 OpenCV 的学习路线
  • 从零开始学习n8n-定时器+HTTP+飞书多维表格（上)
  • UFUNCTION C++ 的再次理解