探索数据结构：双向链表的灵活优势


✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 前言

前面我们学习了单链表，它解决了顺序表中插入删除需要挪动大量数据的缺点。但同时也有仍需改进的地方，比如说：我们有时候需要寻找某个节点的前一个节点，对于单链表而言只能遍历，这样就可能造成大量时间的浪费。为了解决这个问题，我们就要学习今天的主角——带头双向循环链表。

2. 双向链表的功能

  1. 初始化顺序表中的数据。
  2. 对顺序表进行尾插(末尾插入数据)。
  3. 对顺序表进行头插(开头插入数据)。
  4. 对顺序表进行头删(开头删除数据)。
  5. 对顺序表进行尾删(末尾删除数据)。
  6. 对顺序表就像查找数据。
  7. 对顺序表数据进行修改。
  8. 任意位置的删除和插入数据。
  9. 打印顺序表中的数据。
  10. 销毁顺序表。

3. 双向链表的定义

双向链表的定义结构体需要包含三个成员，一个成员存储数值，一个成员存储前一个节点的地址，最后一个成员存储下一个节点的地址。

typedef int LTDataType;
typedef struct DoubleList
{struct DoubleList* prev;//指向前一个节点LTDataType data;struct DoubleList* next;//指向下一个节点
}DListNode;

4. 双向链表的功能

4.1 初始化双向链表

在初始化双向链表时，我们需要创建一个头节点，也就是我们常说的哨兵位头节点。

(1) 创建头结点
DListNode* DLNodeCreat(LTDataType x)
{DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));if (newnode == NULL){perror("malloc fail:");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}
(2) 初始化

初始化将头节点的前后指针都指向自己，并将数值至为-1。

DListNode* InitDList()
{DListNode* phead = DLNodeCreat(-1);phead->prev = phead;phead->next = phead;return phead;
}
(3) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

4.2 双向链表尾插

因为我们实现的双向链表存在头节点，所以我们不需要像实现单链表一样先判断链表是否为空。

(1) 代码实现
void DListPushBack(DListNode* ptr, LTDataType x)
{assert(ptr);DListNode* tail = ptr->prev;DListNode* newnode = DLNodeCreat(x);tail->next = newnode;newnode->prev = tail;ptr->prev = newnode;newnode->next = ptr;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

4.3 双向链表头插

因为带头双向循环链表的特性，即使只有头节点进行头插，代码实现也是相同的。

(1) 代码实现
void DListPushFront(DListNode* ptr, LTDataType x)
{assert(ptr);DListNode* next = ptr->next;DListNode* newnode = DLNodeCreat(x);ptr->next = newnode;newnode->prev =ptr;newnode->next = next;next->prev = newnode;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

4.4 双向链表尾删

有了循环找尾节点也十分容易，双向链表尾删自然并不困难。但是需要防止删除头节点。

(1) 代码实现
void DListPopBack(DListNode* ptr)
{assert(ptr);assert(ptr->next != ptr);//放置删除头节点DListNode* tail = ptr->prev;DListNode* tailprev = tail->prev;free(tail);tail == NULL;tailprev->next = ptr;ptr->prev = tailprev;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.5 双向链表头删

头删与尾删一样，都需要防止删除头节点。

(1) 代码实现
void DListPopFront(DListNode* ptr)
{assert(ptr);assert(ptr->next != ptr);DListNode* phead = ptr->next;DListNode* pheadnext = phead->next;free(phead);ptr->next = pheadnext;pheadnext->prev = ptr;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.6 双向链表查找

和单链表一样，我们也可以对双向链表进行查找。如果找到就返回该节点的地址，否则返回NULL。

(1) 代码实现
DListNode* DListFind(DListNode* ptr, LTDataType x)
{assert(ptr);DListNode* cur = ptr->next;while (cur != ptr){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
(2) 复杂度分析
  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.7 修改双向链表

我们可以结合双向链表的查找，对双向链表进行修改。

(1) 代码实现
void DListModify(DListNode* ptr, DListNode* pos, LTDataType x)
{assert(ptr);assert(ptr != pos);//防止对头节点操作DListNode* cur = ptr->next;while (cur != ptr){if (cur == pos){cur->data = x;}cur = cur->next;}
}
(2) 复杂度分析
  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.8 双向链表指定插入数据

随机插入数据可以分为：向前插入与向后插入。

(1) 向前插入
void DListInsertF(DListNode* ptr, DListNode* pos, LTDataType x)
{assert(ptr);DListNode* newnode = DLNodeCreat(x);DListNode* prev = pos->prev;newnode->prev = prev;newnode->next = pos;prev->next = newnode;pos->prev = newnode;
}
(2) 向后插入
void DListInsertB(DListNode* ptr, DListNode* pos, LTDataType x)
{assert(ptr);DListNode* newnode = DLNodeCreat(x);DListNode* next = pos->next;newnode->prev = pos;newnode->next = next;next->prev = newnode;pos->next = newnode;
}
(3) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.9 指定位置删除数据

任意删除也需要放置删除头节点，并且因为其特点只需要一个参数就能完成该操作。

(1) 代码实现
void DListErase(DListNode* pos)
{assert(pos);assert(pos != pos->next);pos->prev->next = pos -> next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.10 打印双向链表

打印双向链表只需将循环之前的数据全部打印即可。

(1) 代码实现
void DLTPrint(DListNode* ptr)
{assert(ptr);printf("guard");DListNode* cur = ptr->next;while (cur != ptr){printf("<==>%d", cur->data);cur = cur->next;}printf("\n");
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.11 销毁双向链表

(1) 代码实现
void DListDestroy(DListNode* ptr)
{assert(ptr);DListNode* cur = ptr->next;while (cur != ptr){DListNode* next = cur->next;free(cur);cur = next;}free(ptr);
}
(2) 复杂度分析
  • 时间复杂度：没有其他额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

5. 完整代码

5.1 DList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct DoubleList
{struct DoubleList* prev;//指向前一个节点LTDataType data;struct DoubleList* next;//指向下一个节点
}DListNode;
DListNode* InitDList();//初始化
void DListPushBack(DListNode* ptr, LTDataType x);//尾插
void DLTPrint(DListNode* ptr);//打印
void DListPushFront(DListNode* ptr, LTDataType x);//头插
void DListPopBack(DListNode* ptr);//尾删
void DListPopFront(DListNode* ptr);//头删
DListNode*DListFind(DListNode* ptr, LTDataType x);//查找
void DListModify(DListNode* ptr, DListNode* pos);//修改
void DListInsertF(DListNode* ptr, DListNode* pos, LTDataType x);//任意位置之前插入
void DListInsertB(DListNode* ptr, DListNode* pos, LTDataType x);//任意位置之后插入
void DListErase(DListNode* pos);//任意位置删除
void DListDestroy(DListNode* ptr);//销毁双向链表

5.2 DList.c

#include"DoubleList.h"
DListNode* DLNodeCreat(LTDataType x)
{DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));if (newnode == NULL){perror("malloc fail:");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}
DListNode* InitDList()
{DListNode* phead = DLNodeCreat(-1);phead->prev = phead;phead->next = phead;return phead;
}
void DListPushBack(DListNode* ptr, LTDataType x)
{assert(ptr);DListNode* tail = ptr->prev;DListNode* newnode = DLNodeCreat(x);tail->next = newnode;newnode->prev = tail;ptr->prev = newnode;newnode->next = ptr;
}
void DListPushFront(DListNode* ptr, LTDataType x)
{assert(ptr);DListNode* next = ptr->next;DListNode* newnode = DLNodeCreat(x);ptr->next = newnode;newnode->prev =ptr;newnode->next = next;next->prev = newnode;
}
void DListPopBack(DListNode* ptr)
{assert(ptr);assert(ptr->next != ptr);//放置删除头节点DListNode* tail = ptr->prev;DListNode* tailprev = tail->prev;free(tail);tail == NULL;tailprev->next = ptr;ptr->prev = tailprev;
}
void DListPopFront(DListNode* ptr)
{assert(ptr);assert(ptr->next != ptr);DListNode* phead = ptr->next;DListNode* pheadnext = phead->next;free(phead);ptr->next = pheadnext;pheadnext->prev = ptr;
}
DListNode* DListFind(DListNode* ptr, LTDataType x)
{assert(ptr);DListNode* cur = ptr->next;while (cur != ptr){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
void DListModify(DListNode* ptr, DListNode* pos, LTDataType x)
{assert(ptr);assert(ptr != pos);//防止对头节点操作DListNode* cur = ptr->next;while (cur != ptr){if (cur == pos){cur->data = x;}cur = cur->next;}
}
void DListInsertF(DListNode* ptr, DListNode* pos, LTDataType x)
{assert(ptr);DListNode* newnode = DLNodeCreat(x);DListNode* prev = pos->prev;newnode->prev = prev;newnode->next = pos;prev->next = newnode;pos->prev = newnode;
}
void DListInsertB(DListNode* ptr, DListNode* pos, LTDataType x)
{assert(ptr);DListNode* newnode = DLNodeCreat(x);DListNode* next = pos->next;newnode->prev = pos;newnode->next = next;next->prev = newnode;pos->next = newnode;
}
void DListErase(DListNode* pos)
{assert(pos);assert(pos != pos->next);pos->prev->next = pos -> next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
void DLTPrint(DListNode* ptr)
{assert(ptr);printf("guard");DListNode* cur = ptr->next;while (cur != ptr){printf("<==>%d", cur->data);cur = cur->next;}printf("\n");
}
void DListDestroy(DListNode* ptr)
{assert(ptr);DListNode* cur = ptr->next;while (cur != ptr){DListNode* next = cur->next;free(cur);cur = next;}free(ptr);
}

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

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

相关文章

深度学习——数据预处理

深度学习——数据预处理

一、数据预处理 为了能用深度学习来解决现实世界的问题&#xff0c;我们经常从预处理原始数据开始&#xff0c; 而不是从那些准备好的张量格式数据开始。 在Python中常用的数据分析工具中&#xff0c;我们通常使用pandas软件包。 像庞大的Python生态系统中的许多其他扩展包一样…
阅读更多...
知识蒸馏——深度学习的简化之道 ！！

知识蒸馏——深度学习的简化之道 ！！

文章目录 前言 1、什么是知识蒸馏 2、知识蒸馏的原理 3、知识蒸馏的架构 4、应用 结论 前言 在深度学习的世界里&#xff0c;大型神经网络因其出色的性能和准确性而备受青睐。然而&#xff0c;这些网络通常包含数百万甚至数十亿个参数&#xff0c;使得它们在资源受限的环境下&…
阅读更多...
中霖教育：注册会计师考试难度大吗?

中霖教育：注册会计师考试难度大吗?

注册会计师被很多人认为是非常具有挑战性的考试&#xff0c;内容涵盖《会计》《审计》《税法》《经济法》《财务成本管理》《公司战略与风险管理》&#xff0c;考的知识点多而复杂&#xff0c;需要牢牢掌握&#xff0c;所以很多人认为这项考试的难度非常大。 注册会计师考试分…
阅读更多...
uniapp使用Echarts图表H5显示正常 打包app显示异常

uniapp使用Echarts图表H5显示正常 打包app显示异常

uniapp使用Echarts在H5页面调试 调试完在H5正常显示 然后通过安卓机调试的时候 发现直接空白了 还有这个爆错 Initialize failed: invalid dom 我有多个图表、图表是通过v-for循环出来的 解决方案 原来是yarn直接安装Echarts 然后改成本地JS文件引入 gitbub文件地址 — dist/…
阅读更多...
[python]bar_chart_race绘制动态条形图

[python]bar_chart_race绘制动态条形图

最近在 B 站上看到了一个宝藏 up 主&#xff0c;名叫 "Jannchie见齐"&#xff0c;专门做动态条形图相关的数据可视化。 可以看到做出的效果还是很不错的&#xff0c;但工具使用的是 JS&#xff0c;不是 Python&#xff0c;于是尝试搜索了一下&#xff0c;看看 Python…
阅读更多...
[C语言]——函数递归

[C语言]——函数递归

目录 一.什么是递归 1.递归的思想&#xff1a; 二.递归的限制条件 三.递归举例 1.举例1&#xff1a;求n的阶乘 1.1分析和代码实现 1.2画图推演 2.举例2&#xff1a;顺序打印⼀个整数的每⼀位 2.1分析和代码实现 2.2画图推演 四.递归与迭代 1.举例3&#xff1a;求第…
阅读更多...
Git全套教程一套精通git.跟学黑马笔记

Git全套教程一套精通git.跟学黑马笔记

Git全套教程一套精通git.跟学黑马笔记 文章目录 Git全套教程一套精通git.跟学黑马笔记1.版本管理工具概念2. 版本管理工具介绍2.1版本管理发展简史(维基百科)2.1.1 SVN(SubVersion)2.1.2 Git 3. Git 发展简史4. Git 的安装4.1 git 的下载4.2 安装4.3 基本配置4.4 为常用指令配置…
阅读更多...
【机器学习】深入解析线性回归模型

【机器学习】深入解析线性回归模型

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…
阅读更多...
STM32CubeMX+freeRTOS+事件组 多任务处理LED和串口打印

STM32CubeMX+freeRTOS+事件组 多任务处理LED和串口打印

摘要：利用CubeMx配置freeeRTOS建立任务并使用事件组实现按键按下时 LED开关和打印信息到串口，上位机接收显示。 验证STM32CubeMx配置的FreeRTOS的任务和事件组使用 方案：按下Key1，绿灯亮或者灭，同时串口打印Key1被按下了到上位机；相关端口和串口配置省略。 新建三个任务…
阅读更多...
VMware部署银河麒麟遇到的问题记录

VMware部署银河麒麟遇到的问题记录

1. 解决VMware Workstation安装VMware Tools显示灰色的办法 1.关闭虚拟机； 2.在虚拟机设置分别设置CD/DVD、CD/DVD2和软盘为自动检测三个步骤； 3.再重启虚拟机，灰色字即点亮。 2.Linux安装vmTool
阅读更多...
Linux - 线程互斥和互斥锁

Linux - 线程互斥和互斥锁

文章目录 前言一、为什么要线程互斥原子性 二、互斥锁互斥锁的创建与销毁互斥锁进行互斥 前言 前几节课&#xff0c;我们学习了多线程的基础概念&#xff0c;这节课&#xff0c;我们来对线程互斥和互斥锁的内容进行学习。 一、为什么要线程互斥 首先我们要明白&#xff0c;对…
阅读更多...
Python模块-基础知识

Python模块-基础知识

Python模块-基础知识 1.模块分类&#xff1a; &#xff08;1&#xff09;自定义模块&#xff1a; 如果你自己写一个py文件&#xff0c;在文件内写入一堆函数&#xff0c;则它被称为自定义模块&#xff0c;即使用python编写的.py文件 &#xff08;2&#xff09;第三方模块&…
阅读更多...
面向对象（C# ）

面向对象（C# ）

面向对象&#xff08;C# &#xff09; 文章目录 面向对象&#xff08;C# &#xff09;ref 和 out传值调用和引用调用ref 和 out 的使用ref 和 out 的区别 结构体垃圾回收GC封装成员属性索引器静态成员静态类静态构造函数拓展方法运算符重载内部类和分布类 继承里氏替换继承中的…
阅读更多...
BM23 二叉树的前序遍历

BM23 二叉树的前序遍历

public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返回方法规定的值即可** * param root TreeNode类 * return int整型一维数组*/public void preorder(List<Integer> list,TreeNode root){if(root null)return;l…
阅读更多...
C语言刷题1

C语言刷题1

和黛玉学编程呀 这期就是普普通通题目和答案啦&#xff0c;大都也比较基础&#xff0c;适合初学者&#xff0c;下期我们就更单链表啦 求Snaaaaaaaaaaaaaaa的前5项之和&#xff0c;其中a是一个数字&#xff0c; 例如&#xff1a;222222222222222 int main() {int a 0;int n …
阅读更多...
力扣---完全平方数

力扣---完全平方数

思路&#xff1a; 还是比较好想的&#xff0c;g[i]定义为和为 i 的完全平方数的最少数量。那么递推关系式是g[i]min(g[i-1],g[i-4],g[i-9],...)1&#xff0c;数组初始化是g[0]0,g[1]1。注意这里要对g[0]初始化&#xff0c;&#xff08;举个例子&#xff09;因为在遍历到g[4]时&…
阅读更多...
如何快速搭建一个完整的vue2+element-ui的项目-二

如何快速搭建一个完整的vue2+element-ui的项目-二

技术细节-继续配置 提示&#xff1a;你以为这样就完了吗,其实还有很多东西需要我们自己手写的 例如&#xff1a; element-ui的配置样式重置配置src使用的配置elinst配置axios异步请求的二次封转配置语言国际化配置(这个看需求,我这里就不用配置了)vuex的配置mixins的配置开发环…
阅读更多...
淘宝店铺如何从1688一键铺货？官方授权API接口，可满足多样化上货需求

淘宝店铺如何从1688一键铺货？官方授权API接口，可满足多样化上货需求

那么新手卖家如何将1688的源头厂货一键铺货到淘宝店铺呢&#xff1f;下面我教大家几招&#xff1a; 1、通过淘宝复制一键复制上货 淘宝API接口采集 taobao.item_get 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretStr…
阅读更多...
未来已来？国内10家AI大模型盘点（附体验网址）

未来已来？国内10家AI大模型盘点（附体验网址）

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 创作者&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 目录 1、阿里云——通义千问2、科大讯飞——星火大模…
阅读更多...
Windows 11 鼠标右键可选择 cmd 命令行选项

Windows 11 鼠标右键可选择 cmd 命令行选项

** Windows 11 鼠标右键可选择 cmd 命令行选项 ** 在文件夹内打开命令行&#xff0c;只能使用 Windows 自带的 PowerShell &#xff0c; 作为一个 cmd 重度使用用户来说很是折磨&#xff0c;需要打开 cmd 然后切换盘符再 cd 。。。 现在咱们自己创建一个可以打开 cmd 的方法…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023