双向链表专题

目录

1. 双向链表的结构

2. 双向链表的实现

2.1 双向链表的初始化

2.2 双向链表的打印

2.3 双向链表的尾插

2.4 双向链表的头插

2.5 双向链表的判空函数

2.6 双向链表的尾删 

2.7 双向链表的头删 

2.8 双向链表的查找

2.9 在pos位置之后插入节点 

2.10 删除指定位置节点

2.11 双向链表的销毁

2.12 双向链表的优化 

2.12.1 销毁的函数优化

2.12.2 初始化函数的优化

3.顺序表和链表的优缺点分析

4.双向链表代码

1. 双向链表的结构

带头双向循环链表 - 简称双向链表

注意:这里的“带头”跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了更好的理解就直接称为单链表的头节点。

带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”“哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

2.1 双向链表的初始化

代码:

//申请节点
//申请节点的代码后续插入数据还要用,所以这里封装一个函数
LTNode* LTBuyNode(LTDataType x)
{//malloc申请节点LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//判断malloc的返回值if (newnode == NULL){//打印错误信息并且退出perror("malloc fail!!!\n");exit(1);}//设置data,next指针以及prev指针newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}
//初始化
//要想改变头节点,就必须传一级指针的地址,所以这里用二级指针接收
void LTInit(LTNode** pphead)
{//参数不能传NULLassert(pphead);//创建一个头节点(哨兵位置)*pphead = LTBuyNode(-1);
}

双向链表初始化问题:

双向链表哨兵位指针指向问题:

 如果后续想要插入新的节点往后面直接插入就可以了,在插入节点时也不需要判断节点是否为空了,因为有哨兵位。

调式:

prev指针和next指针都指向自己。

双向链表为空的情况:只有一个哨兵位,因为它不存储任何效数据，如果哨兵位都没有,那就是一个单链表。

2.2 双向链表的打印

代码:

//打印
void LTPrint(LTNode* phead)
{//不能传空指针,因为就算双向链表为空,哨兵位是有的assert(phead);//哨兵位的下一个节点才是双向链表的第一个有效节点LTNode* pcur = phead->next;//pcur遍历双向链表,当遍历的节点是哨兵位的时候跳出循环while (pcur != phead){//打印当前节点的data值printf("%d->", pcur->data);//走向下一个节点pcur = pcur->next;}//双向链表中没有NULL,只需要换行就行//printf("NULL\n");printf("\n");
}

2.3 双向链表的尾插

代码:

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{//不能传空指针assert(phead);//申请节点LTNode* newnode = LTBuyNode(x);/*注意:在修改节点指针指向的时候一定要注意顺序如果先修改哨兵位节点的prev指针的指向,那么最后一个节点就会找不到如果先修改原来的节点都有可能会影响原链表,所以我们先修改newnode节点的next指针和prev指针的指向才不会影响原链表*///新节点的next指针指向哨兵位newnode->next = phead;//新节点的prev指针指向哨兵位的prev指针指向的节点,也就是原链表的尾节点newnode->prev = phead->prev;//新节点的前节点的next指针指向新节点自己newnode->prev->next = newnode;//哨兵为的prev节点指向newnode节点phead->prev = newnode;
}

函数传参问题:

指针指向:

 测试:

2.4 双向链表的头插

代码: 

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{//不能传空指针assert(phead);//申请节点LTNode* newnode = LTBuyNode(x);//将newnode的next指针指向phead->nextnewnode->next = phead->next;//将newnode的prev指针指向哨兵位newnode->prev = phead;//将哨兵位的next指针指向newnodephead->next = newnode;//将newnode的next指针指向的节点的prev指针指向newnode自己newnode->next->prev = newnode;
}

指针指向:

测试:

2.5 双向链表的判空函数

代码:

//双向链表的判空
//该函数的返回值是布尔类型,所以得包含头文件,#include <stdbool.h>
bool LTEmpty(LTNode* phead)
{//不能传空指针assert(phead);//当哨兵位的next指针指向的不是哨兵位节点自己的时候,返回false//否则返回truereturn phead->next == phead;
}

2.6 双向链表的尾删 

代码:

//尾删
//哨兵位不能删除,所以这里传一级指针就可以了
void LTPopBack(LTNode* phead)
{//不能传空指针以及双向链表为空不能删除/*双向链表为空指的是该链表只有一个哨兵位节点该哨兵位节点的next指针和prev指针指向自己所以当phead的next指针和prev指针指向自己的时候就不能指向删除操作(判断一个即可),因为next指针指向自己的时候prev指针也就指向自己了*/assert(phead );//assert直接断言链表是否为空和函数判断链表是否为空，任意选择一种即可//assert(phead->next != phead);assert(!LTEmpty(phead));//phead  phead->prev->prev  phead->prev//将phead->prev->prev的节点的next指针指向哨兵位phead->prev->prev->next = phead;//保存尾节点(要释放的节点)LTNode* del = phead->prev;//保存尾节点的前一个节点LTNode* prev = del->prev;//将prev的next指针不再指向尾节点,要指向哨兵位prev->next = phead;//将哨兵位的前一个节点不再指向尾节点,要指向prev节点phead->prev = prev;//释放尾节点free(del);//将del指针置为空,防止变成野指针del = NULL;
}

指针的指向

测试:

如果再删除,链表就会变成空链表,空链表继续删除,断言就会报错。

2.7 双向链表的头删 

代码:

//头删
void LTPopFront(LTNode* phead)
{//不能传空指针以及空链表不能删除assert(phead && !LTEmpty(phead));//phead phead->next phead->next->next//保存要删除的节点LTNode* del = phead->next;//将哨兵位的next节点指向要删除节点的后一个节点phead->next = del->next;//将要删除节点的后一个节点的prev指针指向哨兵位del->next->prev = phead;//释放del节点free(del);//将del置为空指针,防止变为野指针del = NULL;
}

指针的指向:

测试:

如果再删除,链表就会变成空链表,空链表继续删除,断言就会报错。

2.8 双向链表的查找

代码:

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{//不能传空指针assert(phead);//从有效节点开始查找,也就是哨兵位的下一个节点LTNode* pcur = phead->next;//当变量节点的指针指向哨兵位的时候跳出循环while (pcur != phead){//判断当前节点的data值是不是等于xif (pcur->data == x){//如果等于x就返回当前节点的地址return pcur;}//走向下一个节点pcur = pcur->next;}//查找失败返回NULLreturn NULL;
}

 测试:

注意该函数的返回值以及返回值的类型。 

2.9 在pos位置之后插入节点 

代码:

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{//pos不能位空assert(pos);//申请节点LTNode* newnode = LTBuyNode(x);//pos newnode pos->next//修改newnode节点不会影响原链表,所以我们先修改newnode节点//将newnode的next指针指向pos之后的节点newnode->next = pos->next;//将newnode节点的prev指针指向pos节点newnode->prev = pos;//将pos节点的next指针指向newnodepos->next = newnode;//将原链表pos节点后的节点的prev指针指向newnodenewnode->next->prev = newnode;
}

指针指向:

测试:

2.10 删除指定位置节点

 代码:

//删除指定位置数据
void LTErase(LTNode* pos)
{//pos不能为空assert(pos);//pos->prev pos pos->next//将pos节点的前一个节点的next指针pos指向下一个节点pos->prev->next = pos->next;//将pos节点的下一个节点的prev指针指向pos前一个节点pos->next->prev = pos->prev;//释放pos节点free(pos);//将pos指针置为空指针,防止变为野指针pos = NULL;
}

指针指向:

测试:

2.11 双向链表的销毁

代码:

//销毁双向链表
//链表是整个都销毁,包括哨兵位,所以这里传二级
void LTDesTroy(LTNode** pphead)
{//不能传空指针以及链表不能为空assert(pphead && *pphead);//创建临时指针,用来遍历节点,初始指向第一个有效位(哨兵位后面的节点)LTNode* pcur = (*pphead)->next;//节点要一个一个销毁,所以要遍历链表,当遍历的指针指向哨兵位的时候跳出循环while (pcur != *pphead){//创建临时变量,将当前节点的下一个节点保存起来,要不然下面free就找不到了LTNode* Next = pcur->next;//销毁当前节点free(pcur);//走下一个节点pcur = Next;}//将pcur置为空,防止变成野指针pcur = NULL;//销毁哨兵位 - 哨兵位在循环中没被释放,所以要单独释放free(*pphead);//指向哨兵位的指针也置为空,防止变为野指针*pphead = NULL;}

调试:

 当断点打在销毁函数之前,此时所以的节点都在,包括哨兵位,还是一个完整的双向链表。

当我按下F10,销毁代码执行完成,此时plist链表直接位NULL。

2.12 双向链表的优化 

双向链表的很多函数都是传的一级指针,因为双向链表有哨兵位,有哨兵位的话就不会去修改哨兵位。但是我们会发现,初始化和销毁又是二级指针,不统一,对使用者不友好。

2.12.1 销毁的函数优化

代码:

void LTDesTroyPro(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* Next = pcur->next;free(pcur);pcur = Next;}free(phead);//这里的phead销毁不会影响plist,但是plist指向的地址已经被销毁phead = pcur = NULL;
}

代码和优化前的代码只是形参的二级指针变为了一级指针,其它没变化。

调试:

断点打在销毁函数之前,链表还是完整的。

 当代码free完哨兵位之后,我们的链表中的节点以及被操作系统回收,指针也置为空,哨兵位也被回收,只不过还没置空,我们还可以看到phead和plist指向的是同一块地址空间。

代码在往下执行一步,phead被置空。

当跳出循环我们还可以看到plist指针还是指向那块空间,可是那块空间以及在销毁函数中被free掉了,被操作系统回收掉了,这是因为我们是值传递,形参的修改并不会影响实参,所以即使phead在函数中被置空,plist也不会被置空,此时plist变成了野指针,所以我们要在函数结束之后手动置空。 

我们把销毁函数的形参改为了一级指针之后我们得在函数外手动置空,这就是我们的优化操作。但是传一级,需要手动将plist置为空,这就是统一接口之后带来的问题。

2.12.2 初始化函数的优化

代码:

//初始化函数的优化
LTNode* LTInitPro()
{LTNode* phead = LTBuyNode(-1);return phead;
}

直接调用该函数接收返回值即可。

初始化函数优化前和优化后的区别:

优化前就是通过形参传递,优化后是通过返回值传递。

3.顺序表和链表的优缺点分析

 顺序表和链表哪一个更好?

不同点顺序表链表(单链表)
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持O(1),因为地址是连续的不支持,O(N)
任意位置插入或删除元素可能需要搬移元素,效率低O(N)只需修改指针指向O(1)
插入动态顺序表,空间不够时需要扩容,有一定的空间浪费没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁

所以顺序表和链表哪个好就得取决于应用场景了,没有绝对的更好,存在即合理,要根据不同的场景选择对应的数据结构。

4.双向链表代码

Elementary data structure: Data structure code and blackboard writing - Gitee.comicon-default.png?t=N7T8https://gitee.com/Axurea/elementary-data-structure/tree/master/2024_7_18_Project

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

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

相关文章

云备份服务端

云备份服务端

文件使用工具和json序列化反序列化工具 //文件和json工具类的设计实现 #ifndef __UTIL__ #define __UTIL__ #include<iostream> #include<fstream> #include<string> #include <vector> #include<sys/stat.h> #include"bundle.h" #inc…
阅读更多...
【C++ | 抽象类】纯虚函数 和 抽象基类，为什么需要抽象基类

【C++ | 抽象类】纯虚函数 和 抽象基类，为什么需要抽象基类

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…
阅读更多...
ETL数据集成丨通过ETLCloud工具，将Oracle数据实时同步至Doris中

ETL数据集成丨通过ETLCloud工具，将Oracle数据实时同步至Doris中

ETLCloud是一个全面的数据集成平台&#xff0c;专注于解决大数据量和高合规要求环境下的数据集成需求。采用先进的技术架构&#xff0c;如微服务和全Web可视化的集成设计&#xff0c;为用户提供了一站式的数据处理解决方案。 主要特点和功能包括&#xff1a; 实时数据处理&…
阅读更多...
拖拽上传（预览图片）

拖拽上传（预览图片）

需求 点击上传图片&#xff0c;或直接拖拽图片到红色方框里面也可上传图片&#xff0c;上传后预览图片 效果 实现 <!DOCTYPE html> <html lang"zh-cn"><head><meta charset"UTF-8"><meta name"viewport" content&…
阅读更多...
【QT】label中添加QImage图片并旋转（水平翻转、垂直翻转、顺时针旋转、逆时针旋转）

【QT】label中添加QImage图片并旋转（水平翻转、垂直翻转、顺时针旋转、逆时针旋转）

目录 0.简介 1.详细代码及解释 1&#xff09;原label显示在界面上 2&#xff09;水平翻转 3&#xff09;垂直翻转 4&#xff09;顺时针旋转45度 5&#xff09;逆时针旋转 0.简介 环境&#xff1a;windows11 QtCreator 背景&#xff1a;demo&#xff0c;父类为QWidget&a…
阅读更多...
收银系统源码-商城下单，门店接单

收银系统源码-商城下单，门店接单

随着新零售时代的不断进步&#xff0c;线下线上一体化的收银系统&#xff0c;被很多门店越来越重视。用户在线上商城下单后&#xff0c;门店如何接单呢&#xff0c;如何处理订单呢&#xff1f; 1.收银系统开发语言 核心开发语言: PHP、HTML5、Dart后台接口: PHP7.3后合管理网…
阅读更多...
ClickHouse 入门（二）【基础SQL操作】

ClickHouse 入门（二）【基础SQL操作】

1、ClickHouse 1.1、SQL 操作 这里只介绍一些和我们之前 MySQL 不同的语法&#xff1b; 1.1.1、Update 和 Delete ClickHouse 提供了 Delete 和 Update 的能力&#xff0c;这类操作被称为 Mutation 查询&#xff08;可变查询&#xff09;&#xff0c;它可以看 做 Alter 的一…
阅读更多...
C语言 | Leetcode C语言题解之第241题为运算表达式设计优先级

C语言 | Leetcode C语言题解之第241题为运算表达式设计优先级

题目&#xff1a; 题解&#xff1a; #define ADDITION -1 #define SUBTRACTION -2 #define MULTIPLICATION -3int* diffWaysToCompute(char * expression, int* returnSize) {int len strlen(expression);int *ops (int *)malloc(sizeof(int) * len);int opsSize 0;for (in…
阅读更多...
钡铼分布式 IO 系统 OPC UA边缘计算耦合器BL205

钡铼分布式 IO 系统 OPC UA边缘计算耦合器BL205

深圳钡铼技术推出的BL205耦合器支持OPC UA Server功能&#xff0c;以服务器形式对外提供数据。符合IEC 62541工业自动化统一架构通讯标准&#xff0c;数据可以选择加密&#xff08;X.509证书&#xff09;、身份验证方式传送。 安全策略支持basic128rsa15、basic256、basic256s…
阅读更多...
Web开发：ASP.NET CORE前后端交互之AJAX（含基础Demo）

Web开发：ASP.NET CORE前后端交互之AJAX（含基础Demo）

目录 一、后端 二、前端 三、代码位置 四、实现效果 五、关键的点 1.后端传输给前端&#xff1a; 2.前端传输给后端 一、后端 using Microsoft.AspNetCore.Mvc; using Microsoft.AspNetCore.Mvc.RazorPages; using Microsoft.AspNetCore.Mvc.Rendering; using WebAppl…
阅读更多...
LNMP环境配置问题整理

LNMP环境配置问题整理

首先是一键安装直接报错： 换教程：搭建LNMP，步骤最详细，附源码，学不会打我-CSDN博客 mysql安装成功之后： MySQL 启动报错：Job for mysqld.service failed because the control process exited with error code. 如果所有方法都试过之后卸载后重装可以快速解决： 参考…
阅读更多...
AI算不出9.11和9.9哪个大？六家大模型厂商总结了这些原因

AI算不出9.11和9.9哪个大？六家大模型厂商总结了这些原因

大模型“答对”或“答错”其实是个概率问题。关于“9.11和9.9哪个大”&#xff0c;这样一道小学生难度的数学题难倒了一众海内外AI大模型。7月17日&#xff0c;第一财经报道了国内外“12个大模型8个都会答错”这道题的现象&#xff0c;大模型的数学能力引发讨论。 “从技术人员…
阅读更多...
idea双击没有反应，打不开

idea双击没有反应，打不开

问题描述 Error opening zip file or JAR manifest missing : /home/IntelliJ-IDEA/bin/jetbrains-agent.jar解决方案
阅读更多...
第三篇 Vue项目目录结构介绍

第三篇 Vue项目目录结构介绍

1、最外层目录结构 passagerFrontPage ├── .vscode //vscode配置&#xff0c;不用理会 ├── node_modules //项目依赖&#xff0c;npm install命令执行后自动生成 ├── public //公共资源存放 ├── src //源码 ├── tests //选装&#xff1a;测试模块 ├── .git…
阅读更多...
STM32智能安防系统教程

STM32智能安防系统教程

目录 引言环境准备智能安防系统基础代码实现&#xff1a;实现智能安防系统 4.1 数据采集模块 4.2 数据处理与控制模块 4.3 通信与网络系统实现 4.4 用户界面与数据可视化应用场景&#xff1a;家庭与企业安防管理问题解决方案与优化收尾与总结 1. 引言 智能安防系统通过STM32…
阅读更多...
逻辑门的题目怎么做？

逻辑门的题目怎么做？

FPGA语法练习——二输入逻辑门&#xff0c;一起来听~~ FPGA语法练习——二输入逻辑门 题目介绍&#xff1a;F学社-全球FPGA技术提升平台 (zzfpga.com)
阅读更多...
ABAP使用SQL直接更新数据库与使用IN UPDATE TASK的区别

ABAP使用SQL直接更新数据库与使用IN UPDATE TASK的区别

1. 背景 刚接触ABAP的小伙伴常常会有这样的疑问&#xff0c;为什么不直接使用Open SQL直接更新数据库&#xff0c;而要把对DB的操作封装到IN UPDATE TASK中呢&#xff1f; 对于这个问题&#xff0c;比较常见的解释是&#xff0c;IN UPDATE TASK的方式会保证数据更新的一致性。…
阅读更多...
Artix7系列FPGA实现SDI视频编解码+UDP以太网传输，基于GTP高速接口，提供工程源码和技术支持

Artix7系列FPGA实现SDI视频编解码+UDP以太网传输，基于GTP高速接口，提供工程源码和技术支持

目录 1、前言工程概述免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本博已有的以太网方案本博已有的FPGA图像缩放方案本方案的缩放应用本方案在Xilinx--Kintex系列FPGA上的应用本方案在Xilinx--Zynq系列FPGA上的应用 3、详细设计方案设计原理框图SDI 输入设备Gv8601a 均衡…
阅读更多...
STM32智能城市交通管理系统教程

STM32智能城市交通管理系统教程

目录 引言环境准备智能城市交通管理系统基础代码实现&#xff1a;实现智能城市交通管理系统 4.1 数据采集模块 4.2 数据处理与控制模块 4.3 通信与网络系统实现 4.4 用户界面与数据可视化应用场景&#xff1a;城市交通管理与优化问题解决方案与优化收尾与总结 1. 引言 智能城…
阅读更多...
Chromium CI/CD 之Jenkins实用指南2024- Windows节点开启SSH服务（七）

Chromium CI/CD 之Jenkins实用指南2024- Windows节点开启SSH服务（七）

1.引言 在现代软件开发和持续集成的过程中&#xff0c;自动化部署和远程管理是不可或缺的关键环节。SSH&#xff08;Secure Shell&#xff09;协议以其强大的安全性和灵活性&#xff0c;成为连接和管理远程服务器的首选工具。对于使用Windows虚拟机作为Jenkins从节点的开发者而…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023