数据结构（C语言篇）：（七）双向链表

目录

前言

一、概念与结构

二、双向链表的实现

2.1  头文件的准备

2.2  函数的实现

2.2.1  LTPushBack( )函数（尾插）

（1）LTBuyNode( )

（2）LTInit( )

（3）LTPrint( )

（4）LTPushBack( )

2.2.2  LTPushFront( )函数（头插）

2.2.3  LTPopBack( )函数（尾删）

2.2.4  LTPopFront( )函数（头删）

2.2.5  LTInsert( )函数（在pos位置之后插入数据）

2.2.6  LTErase( )函数（删除pos位置的结点）

2.2.7  LTFind( )函数（查找结点）

2.2.8  LTDestroy( )函数（销毁）

三、顺序表与链表的分析

总结

前言

        数据结构作为计算机科学的核心基础之一，其高效性与灵活性直接影响程序性能。双向链表以其独特的双指针结构脱颖而出，既继承了单链表的动态内存管理优势，又通过前驱指针实现了逆向遍历与快速节点删除。这种结构在操作系统内核、数据库索引及LRU缓存淘汰算法等场景中展现关键价值。本文将深入剖析双向链表的实现原理、时间复杂度权衡及典型应用场景，下面就让我们正式开始吧！

一、概念与结构

        如上图所示，带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨”的。

        需要注意的是，这里的“带头”和前面博客中提到的“头结点”是两个概念，实际前面的在单链表阶段称呼是不严谨的，但是为了更好地帮助大家理解，我们才直接称为单链表的头结点。

二、双向链表的实现

2.1  头文件的准备

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next; //指针保存下⼀个结点的地址struct ListNode* prev; //指针保存前⼀个结点的地址LTDataType data;
}LTNode;//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode *LTFind(LTNode* phead,LTDataType x);

2.2  函数的实现

2.2.1  LTPushBack( )函数（尾插）

        我们先来画图分析一下：

        当然，在正式实现尾插函数之前，我们照旧还得先写一下双向链表的创建结点函数、链表初始化函数和链表打印函数 —— LTBuyNode( )、LTInit( )和LTPrint( )，如下所示：

（1）LTBuyNode( )

        实现逻辑如下：

  1. 内存分配：为新节点分配内存空间

  2. 内存检查：检查内存分配是否成功

  3. 数据赋值：将数据存储到新节点

  4. 指针初始化：将前驱和后继指针都指向自己（循环链表特性）

        完整代码如下：

LTNode* LTBuyNode(LTDataType x) {// 1. 内存分配LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));// 2. 内存分配失败检查if (newnode == NULL) {perror("malloc fail!");  // 打印错误信息exit(1);                 // 退出程序}// 3. 数据赋值newnode->data = x;// 4. 指针初始化（双向循环链表的关键）newnode->next = newnode->prev = newnode;return newnode;
}
（2）LTInit( )

        该函数的实现逻辑如下：

  1. 创建哨兵节点：使用LTBuyNode函数创建特殊节点

  2. 返回链表头：返回指向哨兵节点的指针

  3. 建立空链表：初始化一个标准的空双向循环链表

        完整代码如下：

// 初始化双向循环链表
LTNode* LTInit() {// 1. 创建哨兵节点，通常使用特殊值（如-1）标记LTNode* phead = LTBuyNode(-1);// 2. 返回哨兵节点作为链表头return phead;
}
（3）LTPrint( )

        该函数的实现逻辑如下：

  1. 遍历链表：从第一个有效节点开始遍历

  2. 打印数据：输出每个节点的数据值

  3. 循环检测：利用哨兵节点作为循环终止条件

  4. 格式化输出：使用箭头表示节点间的连接关系

        完整代码如下：

void LTPrint(LTNode* phead) {// 1. 从第一个有效节点开始（跳过哨兵节点）LTNode* pcur = phead->next;// 2. 遍历链表，直到回到哨兵节点while (pcur != phead) {printf("%d -> ", pcur->data);  // 打印当前节点数据pcur = pcur->next;            // 移动到下一个节点}// 3. 打印换行，结束输出printf("\n");
}
（4）LTPushBack( )

        该函数的实现逻辑如下：

  1. 参数验证：确保头结点phead不为NULL。

    assert(phead);

  2. 创建新节点：使用LTBuyNode函数创建新结点，新结点包含数据x，prev和next指针初始化

    LTNode* newnode = LTBuyNode(x);

  3. 设置新结点的指针：newnode->prev 指向原来的尾节点（即 phead->prev）；newnode->next 指向头节点 phead。

    newnode->prev = phead->prev;
newnode->next = phead;

  4. 更新相邻结点的指针：将原来的尾结点的next指向新结点，将头结点的prev指向新结点（现在的新结点称为新的尾结点）。

    phead->prev->next = newnode;
phead->prev = newnode;

                完整代码如下：

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

2.2.2  LTPushFront( )函数（头插）

        画图分析如下：

        函数实现逻辑如下：

        1.参数验证：确保头结点phead不为NULL。

        2.创建新结点：调用LTBuyNode函数创建新结点。

        3.设置新结点的指针：newnode->next 指向原来的第一个数据节点（即 phead->next）；newnode->prev 指向头节点 phead。

newnode->next = phead->next;
newnode->prev = phead;

        4.更新相邻结点的指针：将原来的第一个数据节点的 prev 指向新节点；将头节点的 next 指向新节点（现在新节点成为新的第一个数据节点）。

phead->next->prev = newnode;
phead->next = newnode;

        完整代码如下：

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

2.2.3  LTPopBack( )函数（尾删）

        首先我们要先来实现一个判空函数LTEmpty（）：

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

        下面来画图分析一下：

        实现逻辑分析如下：

        1.前置条件检查：使用LTEmpty 函数检查链表是否为空；如果链表为空（只有头节点），则断言失败，不能删除；确保链表至少有一个数据节点可删除。

assert(!LTEmpty(phead));

        2.定位要删除的结点：尾结点就是头结点的 prev 指向的节点；将尾节点保存到 del 变量中。

LTNode* del = phead->prev;

        3.更新指针连接：

  • del->prev->next = phead：将尾节点的前一个节点的 next 指向头节点

  • phead->prev = del->prev：将头节点的 prev 指向尾节点的前一个节点

del->prev->next = phead;
phead->prev = del->prev;

        4.释放内存：释放被删除结点的内存；将指针置为NULL，避免野指针。

free(del);
del = NULL;

        完整代码如下：

//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

2.2.4  LTPopFront( )函数（头删）

        画图分析如下：

        函数实现逻辑如下：

        1.前置条件检查：使用 LTEmpty 函数检查链表是否为空。

        2.定位要删除的结点：第一个数据节点就是头结点的next指向的结点；将该结点保存到 del 变量中。

LTNode* del = phead->next;

        3.更新指针连接：

  • del->next->prev = phead：将第二个数据节点的 prev 指向头节点

  • phead->next = del->next：将头节点的 next 指向第二个数据节点

  • 这样就跳过了要删除的第一个数据节点

    del->next->prev = phead;
phead->next = del->next;

    4.释放内存：释放被删除节点的内存；将指针置为 NULL，避免野指针。

        完整代码如下：

//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

2.2.5  LTInsert( )函数（在pos位置之后插入数据）

        画图分析如下：

        实现逻辑：

        1. 参数验证：确保 pos 节点不为 NULL。

        2.创建新结点：调用 LTBuyNode 函数创建新节点。

        3.设置新结点的指针：

  • newnode->prev 指向 pos 节点（前驱节点）

  • newnode->next 指向 pos 节点原来的下一个节点

    newnode->prev = pos;
newnode->next = pos->next;

    4.更新相邻结点的指针：

  • 将 pos 节点原下一个节点的 prev 指向新节点

  • 将 pos 节点的 next 指向新节点

pos->next->prev = newnode;
pos->next = newnode;

        完整代码如下：

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

2.2.6  LTErase( )函数（删除pos位置的结点）

        先画图分析一下：

        实现逻辑分析如下：

        1.参数验证：确保 pos 节点不为 NULL。

        2.更新指针连接（跳过要删除的节点）：

  • pos->prev->next = pos->next：将前驱节点的 next 指向后继节点

  • pos->next->prev = pos->prev：将后继节点的 prev 指向前驱节点

  • 这样就完全跳过了要删除的 pos 节点

    pos->prev->next = pos->next;
pos->next->prev = pos->prev;

    3.释放内存：释放被删除节点的内存。

    free(pos);
pos = NULL;

    完整代码如下所示：

    //删除pos位置的节点
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

    2.2.7  LTFind( )函数（查找结点）

        实现逻辑如下：

        1.参数验证：确保头节点 phead 不为 NULL

        2.初始化遍历指针：创建当前指针 pcur 并初始化为第一个数据节点（phead->next）；跳过哨兵头节点，从第一个数据节点开始遍历。

LTNode* pcur = phead->next;

        3.遍历链表查找数据：循环条件 pcur != phead：当回到头节点时停止（完成一圈遍历）；对每个数据节点检查其 data 是否等于目标值 x；如果找到匹配的节点，立即返回该节点的指针。

while (pcur != phead)
{if (pcur->data == x){return pcur;}pcur = pcur->next;
}

        4.未找到的情况：如果遍历完所有数据节点都没有找到匹配的节点；返回 NULL 表示查找失败。

return 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.2.8  LTDestroy( )函数（销毁）

        画图分析如下：

        函数实现逻辑：

        1.初始化遍历指针：创建当前指针 pcur 并初始化为第一个数据节点；从头节点的下一个节点开始遍历。

LTNode* pcur = phead->next;

        2.遍历并释放所有数据结点：

  • 循环条件：pcur != phead —— 当回到头节点时停止；

  • 保存下一个节点：在释放当前节点前，先保存下一个节点的指针；

  • 释放当前节点：使用 free() 释放当前数据节点的内存；

  • 移动到下一个节点：将 pcur 指向之前保存的下一个节点。

while (pcur != phead)
{LTNode* next = pcur->next;free(pcur);pcur = next;
}

        3.释放头结点：释放头节点（哨兵节点）的内存；将指针置为 NULL，避免野指针。

free(phead);
phead = NULL;

        完整代码如下：

//销毁
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//销毁头结点free(phead);phead = NULL;
}

三、顺序表与链表的分析

不同点顺序表

链表（单链表）

存储空间上物理上⼀定连续逻辑上连续，但物理上不⼀定连续
随机访问⽀持O(1)不⽀持：O(N)
任意位置插⼊或者删除元素可能需要搬移元素，效率低O(N)只需修改指针指向
插⼊动态顺序表，空间不够时需要扩
容和空间浪费		没有容量的概念，按需申请释放，不存在
空间浪费
应⽤场景元素⾼效存储+频繁访问任意位置⾼效插⼊和删除

总结

        以上就是本期博客的全部内容啦！本期我为大家介绍了双向链表的实现逻辑以及顺序表与链表的对比分析，希望能够对大家学习数据结构有所帮助，谢谢大家的支持~！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/pingmian/95096.shtml
繁体地址，请注明出处：http://hk.pswp.cn/pingmian/95096.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

从拿起简历（resume）重新找工作开始聊起

从拿起简历（resume）重新找工作开始聊起

经济萧条或经济衰退在经济相关学术上似乎有着严格的定义，我不知道我们的经济是否已经走向了衰退或者萧条，但有一点那是肯定的，那就现在我们的经济肯定是不景气的。经济不景气会怎么样？是的，会有很多人失业，…
阅读更多...
OS+MySQL+(其他)八股小记

OS+MySQL+(其他)八股小记

鲁迅先生曾经说过，每天进步一点点，妈妈夸我小天才。 依旧今日八股，这是我在多个文档整合一起的，可能格式有些问题，请谅解。 操作系统 1.进程和线程的区别？ 进程是代码在数据集合的一次执行活动，…
阅读更多...
Transformer的并行计算与长序列处理瓶颈总结

Transformer的并行计算与长序列处理瓶颈总结

🌟 第0层：极简版（30秒理解）一句话核心：Transformer像圆桌会议——所有人都能同时交流（并行优势），但人越多会议越混乱（长序列瓶颈）。核心问题 并行优势&#x…
阅读更多...
Vue 3 useId 完全指南：生成唯一标识符的最佳实践

Vue 3 useId 完全指南：生成唯一标识符的最佳实践

📖 概述 useId() 是 Vue 3 中的一个组合式 API 函数，用于生成唯一的标识符。它确保在服务端渲染（SSR）和客户端渲染之间生成一致的 ID，避免水合不匹配的问题。 🎯 基本概念 什么是 useId？ useId…
阅读更多...
CGroup 资源控制组 + Docker 网络模式

CGroup 资源控制组 + Docker 网络模式

1 CGroup 资源控制组1.1 为什么需要 CGroup - 容器本质 宿主机上一组进程 - 若无资源边界，一个暴走容器即可拖垮整机 - CGroup 提供**内核级硬限制**，比 ulimit、nice 更可靠1.2 核心概念 3 件套 | 概念 | 一句话解释 | 查看方式 | | Hierarchy | 树…
阅读更多...
【ArcGIS微课1000例】0150：如何根据地名获取经纬度坐标

【ArcGIS微课1000例】0150：如何根据地名获取经纬度坐标

本文介绍了三种获取地理坐标的方法：1）在ArcGIS Pro中通过搜索功能定位目标点（如月牙泉）并查看其WGS84坐标；2）使用ArcGIS内置工具获取坐标；3）推荐三个在线工具（maplocation、地球在线、yanue）支持批量查询和多地图源坐标转换。强调了使用WGS84坐标系以减少误差，并展示…
阅读更多...
HTML应用指南：利用GET请求获取MSN财经股价数据并可视化

HTML应用指南：利用GET请求获取MSN财经股价数据并可视化

随着数字化金融服务的不断深化，及时、准确的财经信息已成为投资者决策与市场分析的重要支撑。MSN财经股价数据服务作为广受信赖的金融信息平台，依托微软强大的技术架构与数据整合能力，持续为全球用户提供全面、可靠的证券市场数据。平台不仅提…
阅读更多...
雅思听力第四课：配对题核心技巧与词汇深化

雅思听力第四课：配对题核心技巧与词汇深化

现在，请拿出剑桥真题，开始你的刻意练习！ 内容大纲 课程核心目标旧题回顾与基础巩固配对题/匹配题核心解题策略考点总结与精听训练表 一、课程核心目标 掌握第二部分配对题的解题策略攻克第三部分匹配题的改写难点系统整理高频场景词汇与特…
阅读更多...
SQL Server从入门到项目实践（超值版）读书笔记 25

SQL Server从入门到项目实践（超值版）读书笔记 25

第12章 存储过程的应用 🎉学习指引 存储过程（Stored Procedure）是在大型数据库系统中，一组为了完成特定功能的SQL语句集，存储过程时数据库中的一个重要对象，它代替了传统的逐条执行SQL语句的方式。本章就来…
阅读更多...
20.29 QLoRA适配器实战：24GB显卡轻松微调650亿参数大模型

20.29 QLoRA适配器实战：24GB显卡轻松微调650亿参数大模型

QLoRA适配器实战：24GB显卡轻松微调650亿参数大模型 QLoRA 适配器配置深度解析 一、QLoRA 适配器核心原理 QLoRA 作为当前大模型微调领域的前沿技术，通过量化与低秩适配的协同设计，在保证模型效果的前提下实现了显存占用的革命性降低。其核心由三大技术支柱构成： 4位量化…
阅读更多...
QMainWindow使用QTabWidget添加多个QWidget

QMainWindow使用QTabWidget添加多个QWidget

QTabWidget添加其它Wdiget的2个函数如下&#xff1a; QTabWidget的介绍可参考官网QTabWidget Class | Qt Widgets | Qt 6.9.1 直接上代码&#xff0c;代码如下&#xff1a; #include <QMainWindow>#include <QApplication> #include <QVBoxLayout> #includ…
阅读更多...
AI学习机哪个好？选这几款步步高就对了

AI学习机哪个好？选这几款步步高就对了

随着新教改政策的推进&#xff0c;教育对孩子的综合素养提出了更高要求。英语更重听说、数学更重思维&#xff0c;这让许多家长在辅导孩子时感到压力倍增。因此&#xff0c;如何选择一款能真正帮助孩子提升能力的学习机&#xff0c;成为了大家普遍关心的问题。面对市场上功能各…
阅读更多...
【设计模式】--重点知识点总结

【设计模式】--重点知识点总结

题1 1、工厂和产品之间是依赖关系 2、工厂方法模式&#xff1a;工厂方法不能为静态方法。如果是静态方法&#xff0c;子类无法重写行为。 简单工厂可以用静态方法 3、采用设计模式&#xff0c;以保证成功的设计和体系结构 4、建造者模式&#xff1a;&#xff08;1&#xf…
阅读更多...
轻量实现 OCPP 1.6 JSON 协议（欧洲版）的充电桩调试平台

轻量实现 OCPP 1.6 JSON 协议（欧洲版）的充电桩调试平台

1 项目概览 1.1 目标与适用场景 1.1.1 简介 本文介绍的开源项目 ocpp_charge&#xff0c;是一个 自研轻量实现 OCPP 1.6 JSON 协议&#xff08;欧洲版&#xff09; 的充电桩调试平台。 它没有依赖官方 OCPP 1.6J 库&#xff0c;而是从零实现协议解析与会话管理&#xff0c;适…
阅读更多...
Ubuntu 搭建 Solana 区块链开发环境 + Anchor 智能合约完整教程

Ubuntu 搭建 Solana 区块链开发环境 + Anchor 智能合约完整教程

文章目录简介特征核心概念Solana 的工作原理&#xff08;简单版&#xff09;为什么人们选择 Solana开发环境准备Solana 官网Solana 文档Anchor 文档GithubRust SDK快速安装 Solana&#xff08;推荐&#xff09;单独安装 Solana安装依赖项安装 Solana CLI安装 Anchor CLI安装 AV…
阅读更多...
curl 介绍及使用教程

curl 介绍及使用教程

文章目录 什么是 curl？ 1. 解析用户输入与初始化 2. 建立网络连接 3. 构建并发送请求 4. 接收并处理响应 5. 清理资源 核心特点总结 基本语法 常用功能及示例 1. 基本 HTTP 请求 2. 发送 GET 请求 3. 发送 POST 请求 4. 设置请求头 5. 处理认证 6. 断点续传 7. 跟随重定向 8. …
阅读更多...
【第十一章】Python 队列全方位解析：从基础到实战

【第十一章】Python 队列全方位解析：从基础到实战

Python 队列全方位解析&#xff1a;从基础到实战 本文将从基础概念到高级应用&#xff0c;用 “文字解释 代码示例 图表对比 实战案例” 的方式&#xff0c;全面覆盖 Python 队列知识&#xff0c;零基础也能轻松掌握。 文章目录Python 队列全方位解析&#xff1a;从基础到实…
阅读更多...
跨平台开发框架实测：React Native vs Flutter vs Kotlin Multiplatform

跨平台开发框架实测：React Native vs Flutter vs Kotlin Multiplatform

本文聚焦 React Native、Flutter 和 Kotlin Multiplatform 三大跨平台开发框架&#xff0c;从性能表现、开发效率、生态系统、跨平台一致性及学习成本五个关键维度展开实测对比。通过具体场景的测试数据与实际开发体验&#xff0c;剖析各框架的优势与短板&#xff0c;为开发者在…
阅读更多...
【网弧软著正版】2025最强软著材料AI生成系统，基于GPT5.0

【网弧软著正版】2025最强软著材料AI生成系统，基于GPT5.0

软著材料AI一键生成系统 网址&#xff1a;AI软著材料生成平台 | 一键生成全套软著文档 - 网络弧线 产品简介&#xff1a; 专业的软件著作权材料AI生成平台&#xff0c;基于GPT-5模型开发&#xff0c;自2022年运营至今已服务数万用户成功获得软著证书。输入软件名称即可自动生成…
阅读更多...
存储掉电强制拉库引起ORA-01555和ORA-01189/ORA-01190故障处理---惜分飞

存储掉电强制拉库引起ORA-01555和ORA-01189/ORA-01190故障处理---惜分飞

机房存储突然掉电导致Oracle数据库访问存储异常,数据库报出大量的ORA-27072: File I/O error,Linux-x86_64 Error: 5: Input/output error,ORA-15081: failed to submit an I/O operation to a disk等错误,实例直接crash Wed Aug 27 07:11:53 2025 Errors in file /u01/app/ora…
阅读更多...
最新文章

Copyright @ 2022~2023