【数据结构】双向链表（真正的零基础）

链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过指针的链接来实现的！在上篇我们学习了单向链表，而单向链表虽然空间利用率高，插入和删除也只需改变指针就可以达到！但是我们在每次查找、删除、访问.....时，都受到单向链表的一个特性干扰：单向不可逆，只能以遍历的形式去使用，这样使得需要从头到尾找到特定的节点再进行操作！今天我们来学习另外一种链表结构：双向链表。既然是零基础，我会从小白的角度进行讲解！放心食用！

目录

                                                            一.链表的分类

                                                   二.带头双向循环链表

                                                                               二.（1）链表节点设置

                                                                      二.（2）链表新增节点

                                                             二.（3）链表初始化 

                                                    二.（4）链表扩容节点

                                                    二.（5）链表打印

                                                    二.（6）在目标节点前面插入

                                                    二.（7）在目标节点后面插入

                                                    二.（8）链表头删

                                                    二.（9）链表尾删

                                                    二.（10）链表头插

                                                    二.（11）链表尾插

                                                    二.（12）删除中间目标节点

                                                    二.（13）释放双链表

               三.总结

               四.代码合并

一.链表的分类

这里就不介绍哈是链表了，如果对此感到疑惑，可以看我上一篇投稿，咱直接进入分类！

链表主要可以分为以下3大类：

单向链表：

单向链表是链表中最简单的一种，它由一系列节点组成，每个节点包含两个部分：指针域与数据域。指针域用来指向下一个节点的地址，数据域用来存储数据。以下是抽象草图，方便巧记：

双向链表：

 双向链表与单向链表不同，它的每个节点有两个指针（next跟prev）跟一个数据域，两个指针分别指向前一个节点和后一个节点。同样，如图巧记：

循环链表：
 循环链表是一种特殊的单链表，它的最后一个节点的指针指向头节点，形成一个“环”，如图：

在进行下面的学习之前，针对链表的各种分类，我们需要理清几个名词：

头指针：

头指针本质上是结构体类型的指针，指向一个节点，这个节点一般是 第一个节点 或者 头节点

头结点：

简单理解为在 第一个节点 前面还有一个节点，这个节点就称为头节点。头节点一般不存储数据

带头：

头指针指向头节点就称为带头节点，如图：

不带头： 

头指针指向第一个节点就称为不带头节点，如图：

针对这几种分类：带头或者不带头、单向或者双向、循环或者非循环 

我们总共可以组合八种链表，我们主要学习 无头双向非循环链表     带头双向循环链表    这两种！

八种链表结构中其中这两种最具代表性，另外六种便自然理解了！上一篇我们已经学完了第一种，今天我们来学习第二种！

注意：双链表一般需要改变四个指针的指向，因此建议大家画图理解！这样就可以轻松操作了！

二.带头双向循环链表

理解了上面几个名词后，我们就能轻易理解哈是带头双向循环链表了！

带头：无非就是第一个节点前还有一个头节点嘛！

双向：节点里面有两个指针，两个指针分别指向一前一后的节点

循环：尾节点的后指针指向头节点，头节点的前指针指向尾节点，达到封闭，形成循环！

二.（1）链表节点设置

不论怎样，我们都需要先创建一个结构体作为接下来各种功能的节点基础， 这个结构体里面有两个指针，一个数据域。这里为了缩短结构体类型，我们用 typedef 重定义以下，需要注意的是typedef重定义的这个结构体里面，结构体指针必须写完整，因为此处还属于声明阶段，后续才可以正常缩写。代码如下：

typedef struct Pointdef
{struct Pointdef* next;//指向下一个节点struct Pointdef* prev;//指向上一个节点int data;//数据域
}Pointdef;
二.（2）链表新增节点

因为我们不管初始化还是各种增添功能，都需要节点，所以我们先完成开辟节点的函数，让这个函数返回指向这个开辟好的节点指针，然后才可以进行初始化操作，代码如下：

//开辟新节点
Pointdef* Newspoint(int x)
{Pointdef* news = (Pointdef*)malloc(sizeof(Pointdef));if (news == NULL){perror("malloc");return NULL;}//初始化新节点news->next = NULL;news->prev = NULL;news->data = x;return news;
}

我们刚开辟好的节点还没有连接，只是一个结构体大小，因此它的prev跟next指针都指向NULL，x就是初始化节点的数据域，如下图理解：

二.（3）链表初始化 

上面我们先调用 新增节点 的函数，在外面开辟一个节点作为头节点（如果有问题，可以先看下面的合并代码！），接下来对这个头节点进行初始化，将它作为头节点，此时头节点的next跟prev指针都应该指向自己（因为是循环链表，此时只有一个节点）。代码如下：

//链表初始化
void Initialize(Pointdef* head)
{head->next = head;head->prev = head;
}

二.（4）链表扩容节点

此时我们已经初始化了链表，下面我们给它新增几个节点，调用新增函数，改变节点指针指向，代码如下：

//链表扩容节点
Pointdef* tail = head;
for (int i = 2; i <= 5; i++)
{Pointdef* news = Newspoint(i);//连接tail->next = news;news->prev = tail;news->next = head;head->prev = news;tail = tail->next;
}

二.（5）链表打印

与单向链表访问区别不大，只需要注意是这里的链表是循环的，需要控制打印的条件不能是当前指针不能指向头节点，否则就是死循环了，代码如下： 

//链表打印
void Printf(Pointdef* head)
{Pointdef* tail = head->next;while (tail != head){printf("%d <= ", tail->data);tail = tail->next;}printf("NULL\n");
}

二.（6）在目标节点前面插入

我们已经写好了一条双链表，那么我们只需要找到目标节点然后连接四个指针就行了，代码如下：

这里我们假设目标节点是 tail ，新节点 news  新节点前面的节点是 prev

//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{assert(tail);Pointdef* prev = tail->prev;Pointdef* news = Newspoint(x);prev->next = news;news->prev = prev;news->next = tail;tail->prev = news;}

二.（7）在目标节点后面插入

将找到的目标节点作为参数，然后在函数中改变它的前后四个指针就行，如图：

//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{assert(tail);//目标节点的下一个节点不能是空，否则就是尾插了assert(tail->next);Pointdef* news = Newspoint(x);Pointdef* next = tail->next;tail->next = news;news->prev = tail;news->next = next;next->prev = news;
}


 二.（8）链表头删

头删咱直接将头节点作为参数就行了，再记录第二个节点方便释放，然后用四个指针连接头节点和第二个节点，最后记得释放第一个节点的空间，如图：

//链表头删
void Outomit(Pointdef* head,int x)
{assert(head);assert(head->next);Pointdef* tail = head->next->next;Pointdef* next = head->next;head->next = tail;tail->prev = head;free(next);next = NULL;
}

二.（9）链表尾删

这个咱就不多说了！就是先记录倒数第二个节点，将它作为尾节点就行了，同样记得释放空间，直接上代码：

//链表尾删
void Tailomit(Pointdef* head, int x)
{assert(head);Pointdef* prev = head->prev->prev;Pointdef* tail = head->prev;prev->next = head;head->prev = prev;free(tail);tail = NULL;
}

二.（10）链表头插

但凡插入节点的都具有很大的相似之处，无非就是将这个节点插入某处，通过记录附近节点的位置，再把新增节点的左右节点与它进行连接，看代码：

//链表头插
void Headinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail = head->next;Pointdef* news = Newspoint(x);head->next = news;news->prev = head;news->next = tail;tail->prev = news;
}

二.（11）链表尾插
//链表尾插
void Tailinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail = head->prev;Pointdef* news = Newspoint(x);tail->next = news;news->prev = tail;head->prev = news;news->next = head;
}

二.（12）删除中间目标节点

删除节点我们肯定要先找到目标节点，我们在链表中可以通过以下两种方式寻找：指针域  数据域，在上面的前后插入中，我们选择的指针查找方式，下面我们进行数据查找方式来删除：

//链表中间节点删除
void Omit(Pointdef* tail)
{Pointdef* pc = tail->prev;Pointdef* pt = tail->next;pc->next = pt;pt->prev = pc;free(tail);tail = NULL;
}

二.（13）释放双链表

咋从第一个节点释放到尾就OK了！注意：链表的空间不是连续的，因此需要一个个销毁！

//双链表销毁
void Undermine(Pointdef* head)
{assert(head);Pointdef* cur = head->next;Pointdef* tail = cur->next;while (cur != head){tail = cur->next;free(cur);cur = tail;}free(head);head=NULL;printf("释放完毕\n");
}
三.总结

针对以上实现的双链表，其实针对整个链表，都有以下特点：

1：首先我们要有设计好开辟节点的函数，然后知道如何连接这些节点

2：头插、尾插、中间插其实都有很大的共性，只是目标地点稍微差异，这点大家可以画图理解！

3：删除某个节点需要及时释放该空间，避免空间泄漏。需要注意是先连接，再释放

4：针对为何单向链表很多涉及二级指针，而双向链表大多是一级指针？

因为单向链表有很多地方需要改变头指针（单向链表将第一个节点作为头节点）的指向，而双向链表是固定了哨兵节点，因此其它操作其实是针对结构体里面的指针操作的。该知识的原理是：对形参的改变不影响实参，如需改变形参，需要使用二级指针

5：双向链表为哈要从第一个节点开始释放？

双向链表的头节点是链表结构的一部分，不是数据节点，应该先释放数据节点，再释放链表结构

四.代码合并

流程文件（可以使用打印来进行功能的测试！）

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"int main()
{int x = 4;//链表新增节点Pointdef* head=Newspoint(1);//链表初始化void Initialize(head);//链表扩容节点Pointdef* tail = head;for (int i = 2; i <= 5; i++){Pointdef* news = Newspoint(i);//连接tail->next = news;news->prev = tail;news->next = head;head->prev = news;tail = tail->next;}//链表打印Printf_t(head);//在目标节点前面插入                      tail = (head->next)->next;x = 6;FrontInsertion(tail, x);//在目标节点后面插入                OutInsertion(tail, x);//                                  测试点Printf_t(head);//链表头删x = 7;Outomit(head,x);//链表尾删x = 8;Tailomit(head, x);//                                  测试点Printf_t(head);//链表头插x = 1;Headinsert(head, x);//链表尾插x = 9;Tailinsert(head, x);//                                  测试点Printf_t(head);//链表中间节点删除x = 4;tail = head -> next;while (tail->data != x){tail = tail->next;}Omit(tail);//                                   测试点Printf_t(head);//双链表销毁Undermine(head);return 0;
}

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>typedef struct Pointdef
{struct Pointdef* next;//指向下一个节点struct Pointdef* prev;//指向上一个节点int data;//数据域
}Pointdef;//链表新增节点
Pointdef* Newspoint(int x);
//链表初始化
void Initialize(Pointdef* head);
//链表打印
void Printf_t(Pointdef* head);
//在目标节点前面插入
void FrontInsertion(Pointdef* tail, int x);
//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x);
//链表头删
void Outomit(Pointdef* head ,int x);
//链表尾删
void Tailomit(Pointdef* head, int x);
//链表头插
void Headinsert(Pointdef* head, int x);
//链表尾插
void Tailinsert(Pointdef* head, int x);
//链表中间节点删除
void Omit(Pointdef* tail);
//双链表销毁
void Undermine(Pointdef* head);

函数执行文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"//链表新增节点
Pointdef* Newspoint(int x)
{Pointdef* news = (Pointdef*)malloc(sizeof(Pointdef));if (news == NULL){perror("malloc");return NULL;}//初始化新节点news->next = NULL;news->prev = NULL;news->data = x;return news;
}//链表初始化
void Initialize(Pointdef* head)
{head->next = head;head->prev = head;
}//链表打印
void Printf_t(Pointdef* head)
{Pointdef* tail = head->next;while (tail != head){printf("%d <= ", tail->data);tail = tail->next;}printf("NULL\n");
}//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{assert(tail);Pointdef* prev = tail->prev;Pointdef* news = Newspoint(x);prev->next = news;news->prev = prev;news->next = tail;tail->prev = news;}//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{assert(tail);//目标节点的下一个节点不能是空，否则就是尾插了assert(tail->next);Pointdef* news = Newspoint(x);Pointdef* next = tail->next;tail->next = news;news->prev = tail;news->next = next;next->prev = news;
}//链表头删
void Outomit(Pointdef* head,int x)
{assert(head);assert(head->next);Pointdef* tail = head->next->next;Pointdef* next = head->next;head->next = tail;tail->prev = head;free(next);next = NULL;
}//链表尾删
void Tailomit(Pointdef* head, int x)
{assert(head);Pointdef* prev = head->prev->prev;Pointdef* tail = head->prev;prev->next = head;head->prev = prev;free(tail);tail = NULL;
}//链表头插
void Headinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail = head->next;Pointdef* news = Newspoint(x);head->next = news;news->prev = head;news->next = tail;tail->prev = news;
}//链表尾插
void Tailinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail = head->prev;Pointdef* news = Newspoint(x);tail->next = news;news->prev = tail;head->prev = news;news->next = head;
}//链表中间节点删除
void Omit(Pointdef* tail)
{Pointdef* pc = tail->prev;Pointdef* pt = tail->next;pc->next = pt;pt->prev = pc;free(tail);tail = NULL;
}//双链表销毁
void Undermine(Pointdef* head)
{assert(head);Pointdef* cur = head->next;Pointdef* tail = cur->next;while (cur != head){tail = cur->next;free(cur);cur = tail;}free(head);head = NULL;printf("释放完毕\n");
}

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

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

相关文章

pip3命令全解析：Python3包管理工具的详细使用指南

pip3命令全解析：Python3包管理工具的详细使用指南

pip3命令全解析：Python3包管理工具的详细使用指南 一、基本使用二、升级和更新三、其他常用命令四、换源操作五、注意事项六、帮助信息pip3命令使用说明 pip3 是 Python 3 的包管理工具，用于安装、升级和卸载 Python 3 的包。以下是 pip3 的常用命令及详细说明： 一、基本使…
阅读更多...
开启对话式智能分析新纪元——Wyn商业智能 BI 携手Deepseek 驱动数据分析变革

开启对话式智能分析新纪元——Wyn商业智能 BI 携手Deepseek 驱动数据分析变革

2月18号&#xff0c;Wyn 商业智能 V8.0Update1 版本将重磅推出对话式智能分析&#xff0c;集成Deepseek R1大模型&#xff0c;通过AI技术的深度融合&#xff0c;致力于打造"会思考的BI系统"&#xff0c;让数据价值触手可及&#xff0c;助力企业实现从数据洞察到决策执…
阅读更多...
使用PyCharm创建项目以及如何注释代码

使用PyCharm创建项目以及如何注释代码

创建好项目后会出现如下图所示的画面&#xff0c;我们可以通过在项目文件夹上点击鼠标右键&#xff0c;选择“New”菜单下的“Python File”来创建一个 Python 文件&#xff0c;在给文件命名时建议使用英文字母和下划线的组合&#xff0c;创建好的 Python 文件会自动打开&#…
阅读更多...
第三个Qt开发实例:利用之前已经开发好的LED驱动在Qt生成的界面中控制LED2的亮和灭

第三个Qt开发实例:利用之前已经开发好的LED驱动在Qt生成的界面中控制LED2的亮和灭

前言 上一篇博文 https://blog.csdn.net/wenhao_ir/article/details/145459006 中&#xff0c;我们是直接利用GPIO子系统控制了LED2的亮和灭&#xff0c;这篇博文中我们利用之前写好的LED驱动程序在Qt的生成的界面中控制LED2的亮和灭。 之前已经在下面两篇博文中实现了LED驱动…
阅读更多...
【Unity】性能优化：UI的合批 图集和优化

【Unity】性能优化：UI的合批 图集和优化

目录 前言一、合批测试二、图集 前言 注意&#xff1a;DC指的是Draw Call。 温馨小提示&#xff1a;Frame Debugger 窗口&#xff08;菜单&#xff1a;Window > Analysis > Frame Debugger&#xff09;会显示绘制调用信息&#xff0c;并允许您控制正在构建的帧的“回放”…
阅读更多...
【安当产品应用案例100集】037-强化OpenVPN安全防线的卓越之选——安当ASP身份认证系统

【安当产品应用案例100集】037-强化OpenVPN安全防线的卓越之选——安当ASP身份认证系统

在当前数字化时代&#xff0c;网络安全已成为企业发展的重要组成部分。对于使用OpenVPN的企业而言&#xff0c;确保远程访问的安全性尤为重要。安当ASP身份认证系统凭借其强大的功能和便捷的集成方式&#xff0c;为OpenVPN的二次登录认证提供了理想的解决方案&#xff0c;特别是…
阅读更多...
表单与交互：HTML表单标签全面解析

表单与交互：HTML表单标签全面解析

目录 前言 一.HTML表单的基本结构 基本结构 示例 二.常用表单控件 文本输入框 选择控件 文件上传 按钮 综合案例 三.标签的作用 四.注意事项 前言 HTML&#xff08;超文本标记语言&#xff09;是构建网页的基础&#xff0c;其中表单&#xff08;<form>&…
阅读更多...
python卷积神经网络人脸识别示例实现详解

python卷积神经网络人脸识别示例实现详解

目录 一、准备 1&#xff09;使用pytorch 2&#xff09;安装pytorch 3&#xff09;准备训练和测试资源 二、卷积神经网络的基本结构 三、代码实现 1&#xff09;导入库 2&#xff09;数据预处理 3&#xff09;加载数据 4&#xff09;构建一个卷积神经网络 5&#xff0…
阅读更多...
防御保护-----前言

防御保护-----前言

HCIE安全防御 前言 计算机病毒 ​ 蠕虫病毒----->具备蠕虫特性的病毒&#xff1a;1&#xff0c;繁殖性特别强&#xff08;自我繁殖&#xff09;&#xff1b;2&#xff0c;具备破坏性 蠕虫病毒是一种常见的计算机病毒&#xff0c;其名称来源于它的传播方式类似于自然界中…
阅读更多...
java和vue开发的图书馆借阅管理系统小程序

java和vue开发的图书馆借阅管理系统小程序

主要功能&#xff1a; 学生借书还书&#xff0c;管理员管理图书管理学生借书还书。系统显示在馆数量和图书总数量&#xff0c;借书时借书数量不可超过在馆数量&#xff0c;还书时需要输入归还数量&#xff08;可借2本书&#xff0c;归还的时候一本一本归还&#xff0c;可查看归…
阅读更多...
【R】Dijkstra算法求最短路径

【R】Dijkstra算法求最短路径

使用R语言实现Dijkstra算法求最短路径 求点2、3、4、5、6、7到点1的最短距离和路径 1.设置data&#xff0c;存放有向图信息 data中每个点所在的行序号为起始点序号&#xff0c;列为终点序号。 比如&#xff1a;值4的坐标为(1,2)即点1到点2距离为4&#xff1b;值8的坐标为(6,7)…
阅读更多...
Oracle的学习心得和知识总结（三十三）|Oracle数据库数据库的SQL ID的底层计算原理分析

Oracle的学习心得和知识总结（三十三）|Oracle数据库数据库的SQL ID的底层计算原理分析

目录结构 注&#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容&#xff0c;其列表如下&#xff1a; 1、参考书籍&#xff1a;《Oracle Database SQL Language Reference》 2、参考书籍&#xff1a;《PostgreSQL中文手册》 3、EDB Postgres Advanced Server User Gui…
阅读更多...
将DeepSeek接入Excel实现交互式对话

将DeepSeek接入Excel实现交互式对话

引言 将DeepSeek接入Excel&#xff0c;为你带来前所未有的交互体验&#xff01;“哪里不懂&#xff0c;选中哪里”&#xff0c;然后直接在侧边栏对话框向DeepSeek发问&#xff0c;非常地方便&#xff01; 案例演示 设置接入方式 既可以通过本地部署的DeepSeek接入Excel&#…
阅读更多...
在npm上传属于自己的包

在npm上传属于自己的包

最近在整理代码&#xff0c;上传到npm方便使用&#xff0c;所以学习了如何在npm发布一个包&#xff0c;整理写成一篇文章和大家一起交流。 1、注册npm账号 npm | Home 2、确保是登录状态 &#xff08;在包目录下&#xff0c;终端执行 npm login) 按enter键自动打开页面&…
阅读更多...
JS宏进阶：XMLHttpRequest对象

JS宏进阶：XMLHttpRequest对象

一、概述 XMLHttpRequest简称XHR&#xff0c;它是一个可以在JavaScript中使用的对象&#xff0c;用于在后台与服务器交换数据&#xff0c;实现页面的局部更新&#xff0c;而无需重新加载整个页面&#xff0c;也是Ajax&#xff08;Asynchronous JavaScript and XML&#xff09;…
阅读更多...
【快应用】多语言适配案例

【快应用】多语言适配案例

【关键词】 多语言，$t 【问题背景】 快应用平台的能力会覆盖多个国家地区，平台支持多语言的能力后，可以让一个快应同时支持多个语言版本的切换，开发者无需开发多个不同语言的源码项目，避免给项目维护带来困难。使用系统默认的语言，开发者配置多语言的方式非常简单，只…
阅读更多...
PyQt学习记录

PyQt学习记录

0. 安装配置 0.1 安装相关库 首先打开你的PyCharm程序&#xff0c;然后新建一个目录用于学习&#xff0c;其次在terminal中输入 pip install pyqt5如果你不具有科学上网能力&#xff0c;请改为国内源 pip install pyqt5 -i https://pypi.douban.com/simple然后安装pyqt相关…
阅读更多...
【多模态大模型】系列3：语义分割（LSeg、GroupViT）

【多模态大模型】系列3：语义分割（LSeg、GroupViT）

目录 1 LSeg2 Group ViT 1 LSeg LANGUAGE-DRIVEN SEMANTIC SEGMENTATION LSeg是第一篇将CLIP应用于语义分割的论文。它的分割的效果拔群&#xff0c;容错能力也很高&#xff1a; 模型总览图跟CLIP很像&#xff1a; 对于图像链路&#xff1a;输入一张图片&#xff0c;进入分割…
阅读更多...
【深度学习】多目标融合算法（四）：多门混合专家网络MMOE（Multi-gate Mixture-of-Experts）

【深度学习】多目标融合算法（四）：多门混合专家网络MMOE（Multi-gate Mixture-of-Experts）

目录 一、引言 二、MMoE&#xff08;Multi-gate Mixture-of-Experts&#xff0c;多门混合专家网络&#xff09; 2.1 技术原理 2.2 技术优缺点 2.3 业务代码实践 2.3.1 业务场景与建模 2.3.2 模型代码实现 2.3.3 模型训练与推理测试 2.3.4 打印模型结构 三、总结 一、…
阅读更多...
自动驾驶数据集三剑客：nuScenes、nuImages 与 nuPlan 的技术矩阵与生态协同

自动驾驶数据集三剑客：nuScenes、nuImages 与 nuPlan 的技术矩阵与生态协同

目录 1、引言 2、主要内容 2.1、定位对比&#xff1a;感知与规划的全维覆盖 2.2、数据与技术特性对比 2.3、技术协同&#xff1a;构建全栈研发生态 2.4、应用场景与评估体系 2.5、总结与展望 3、参考文献 1、引言 随着自动驾驶技术向全栈化迈进&#xff0c;Motional 团…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023