当前位置: 首页 > news >正文

【数据结构】-----双链表(小白必看!!!)

9efbcbc3d25747719da38c01b3fa9b4f.gif

 c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343

给大家分享一句我很喜欢我话:

知不足而奋进,望远山而前行!!!

铁铁们,成功的路上必然是孤独且艰难的,但是我们不可以放弃,远山就在前方,但我们能力仍然不足,所有我们更要奋进前行!!!

今天我们更新了双链表内容,

🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

什么是双链表?

双链表的定义
 为什么引入双链表?

 单链表的结点中只有一个指向其后继的指针,使得单链表要访问某个结点的前驱结点时,只能从头开始遍历,访问后驱结点的复杂度为O(1),访问前驱结点的复杂度为O(n)。为了克服上述缺点,引入了双链表。

 双链表的结点中有两个指针prior和next,分别指向前驱结点和后继结点。

 双链表中结点类型的描述:

typedef int ListDataType;struct ListNode 
{ListDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;typedef struct ListNode LTNode;

这里可以看到我们把int变为ListNodeType类型,因为我们这个节点不一定就是int类型,用ListData代替int,就可以存储别的类型的数据了。啥时候用啥时候换。

然后用LTNode代替struct ListNode,这样更方便一些。

双链表上的操作:

1.1双链表的初始化:

在初始化之前,我们这里先说一下如何创建一个新节点。因为刚开始数据为空,因此我们先要创建新节点才可以。

//创建新节点
LTNode* BuyNode(ListDataType x)
{LTNode* newhead = (LTNode*)malloc(sizeof(LTNode));if (newhead == NULL){perror("malloc fail !!!");}newhead->next = newhead->prev = NULL;newhead->data = x;return newhead;
}

这就是创建新节点的代码。

下面我们来看一下初始化的代码:

//初始化
LTNode* InitNode()
{LTNode* phead = BuyNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

这样我们就完成了第一步,链表的初始化。这里记住我们创建出来的第一个节点,不能直接去使用,而是要指向本身才可以。否则会将自身变为NULL。

1.2打印链表:

这里也是非常简单,就是我们遍历链表即可。

void ListNodeprint(LTNode* head)
{assert(head);LTNode* cur = head->next;while (cur != head){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

这里要注意的就是,while循环中条件不能是cur,否则这样就会无限的进行下去,我们要令cur!=head。这里的head就是我们的第一个节点,我们也叫它为哨兵位。

1. 3后插

后插相对来说也是比较简单的,下面我们来看一下代码。

//后插
void LTNPushBack(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead = BuyNode(x);LTNode* Tail = phead->prev;Tail->next = newhead;newhead->prev = Tail;newhead->next = phead;phead->prev = newhead;}

首先我们要对phead进行断言,防止传过来的是空指针。

然后这个交换的过程需要大家自己慢慢去琢磨,原理很简单,就是将原本的最后一个变成新的节点,哨兵位的上一个变成新的节点。只是存在一些细节需要大家去注意一下。

1.4前插

//前插
void LTPushFront(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead = BuyNode(x);LTNode* Tail = phead->next;newhead->next = Tail;Tail->prev = phead;phead->next = newhead;newhead->prev = phead;}

这个是前插的代码,原理和后插也大差不差,还是将哨兵位的下一个变成新节点,原本的第一个节点变成第二个节点。

1.5头删

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

头删就是一定要断言head和head的下一个,如果只有一个哨兵位也无法进行删除。

然后剩下的就是把哨兵位的下一个变成第二个节点,第二个节点的上一个变成哨兵位,最后将原本的第一个节点释放掉,置为NULL。

1.6尾删

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

依然是对head和他的下一个进行断言。然后思路与前面的头删大致相同。只是是对哨兵位的上一个进行操作。

1.7任意插入

//任意插入
void LTInsert(LTNode* pos, ListDataType x)
{assert(pos);LTNode* newhead = BuyNode(x);LTNode* posPrev = pos->prev;newhead->prev = posPrev;posPrev->next = newhead;pos->prev = newhead;newhead->next = pos;}

这里的任意插入我们需要事先找到我们要插入的数的位置,然后在这个位置的后面进行插入。这就需要一个find函数,这个我们后面会讲到,暂时不用去管,我们先弄清楚任意插入的思路,就是将创建一个新的节点,然后将pos的下一个变成它,后面的节点的前一个变成他。

1.8任意位置删除

//pos删除
void LTErase(LTNode* pos)
{//pos理论上不能为phead,但是没有参数phead,无法增加校验assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;

这个依然要用到Find函数,还是先不用去管,我们先看一下这个的思路,思路也是很简单,就是将pos前面的节点指向pos后面,pos后面的节点指向pos前面。

1.9寻找

LTNode* LTFind(LTNode* head, ListDataType x)
{assert(head);assert(head->next != NULL);LTNode* cur = head->next;while (cur != head){if (cur->data == x){return cur;}cur = cur->next;}printf("找不到\n");return NULL;
}

这里就是我们find函数的代码了,我们首先要对head和head->next进行断言,防止其是NULL,然后创建一个cur,进行while循环,条件依旧是cur!=head,然后找到的话就返回这个节点,找不到就返回空指针。

1.10链表的销毁

最后我们来说一下链表的销毁,这里我们要对每一个节点都要销毁。

//链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

这个就要相对简单一些了,就是令pcur等于head->next,然后遍历,最后对phead进行销毁。

全部代码

List.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int ListDataType;struct ListNode 
{ListDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;typedef struct ListNode LTNode;//初始化
LTNode* InitNode();//创建新节点
LTNode* BuyNode(ListDataType x);//打印
void ListNodeprint(LTNode* head);//后插
void LTNPushBack(LTNode* phead, ListDataType x);//前插
void LTPushFront(LTNode* phead, ListDataType x);//头删
void LTPopFront(LTNode* head);//尾删
void LTPopBack(LTNode* head);//任意点插入
void LTInsert(LTNode* pos, ListDataType x);//任意点删除
void LTErase(LTNode* pos);//查找
LTNode* LTFind(LTNode* head, ListDataType x);//链表的销毁
void LTDestroy(LTNode* phead);

List.c:

#include"List.h"//创建新节点
LTNode* BuyNode(ListDataType x)
{LTNode* newhead = (LTNode*)malloc(sizeof(LTNode));if (newhead == NULL){perror("malloc fail !!!");}newhead->next = newhead->prev = NULL;newhead->data = x;return newhead;
}//初始化
LTNode* InitNode()
{LTNode* phead = BuyNode(-1);phead->next = phead;phead->prev = phead;return phead;
}//打印
void ListNodeprint(LTNode* head)
{assert(head);LTNode* cur = head->next;while (cur != head){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//后插
void LTNPushBack(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead = BuyNode(x);LTNode* Tail = phead->prev;Tail->next = newhead;newhead->prev = Tail;newhead->next = phead;phead->prev = newhead;}//前插
void LTPushFront(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead = BuyNode(x);LTNode* Tail = phead->next;newhead->next = Tail;Tail->prev = phead;phead->next = newhead;newhead->prev = phead;}//头删
void LTPopFront(LTNode* head)
{assert(head);assert(head->next != head);LTNode* Next = head->next;head->next = Next->next;Next->prev = head;free(Next);Next = NULL;}//尾删
void LTPopBack(LTNode* head)
{assert(head);assert(head->next != head);LTNode* cur = head->prev;head->prev = cur->prev;head->prev->next = head;free(cur);cur = NULL;
}//任意插入
void LTInsert(LTNode* pos, ListDataType x)
{assert(pos);LTNode* newhead = BuyNode(x);LTNode* posPrev = pos->prev;newhead->prev = posPrev;posPrev->next = newhead;pos->prev = newhead;newhead->next = pos;}//pos删除
void LTErase(LTNode* pos)
{//pos理论上不能为phead,但是没有参数phead,无法增加校验assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;}LTNode* LTFind(LTNode* head, ListDataType x)
{assert(head);assert(head->next != NULL);LTNode* cur = head->next;while (cur != head){if (cur->data == x){return cur;}cur = cur->next;}printf("找不到\n");return NULL;
}//链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

test.c:

#include"List.h"int main()
{LTNode* head = InitNode();LTNPushBack(head, 1);LTNPushBack(head, 2);LTNPushBack(head, 3);LTNPushBack(head, 4);LTNode* find = LTFind(head, 1);LTErase(find);find = NULL;//打印ListNodeprint(head);//销毁LTDestroy(head);
}

总结:

双链表是一种常见的数据结构,与单链表相比,每个节点不仅保存了指向下一个节点的指针,还保存了指向前一个节点的指针。这种结构的引入增加了链表的灵活性和功能性。

首先,双链表支持双向遍历。由于每个节点都有指向前一个节点的指针,可以从任一节点开始向前或向后遍历链表,这对于某些操作如逆序遍历或者在特定节点前后插入节点非常方便。

其次,双链表更便于节点的删除和插入。在单链表中,要删除或插入一个节点,需要找到其前一个节点,而在双链表中,只需要修改节点本身的指针即可,无需额外的查找操作,从而提高了操作效率。

然而,双链表相比单链表需要额外的空间来存储前一个节点的指针,因此会占用更多的内存。在某些情况下,如果对内存占用有限制,可能需要权衡选择是否使用双链表。

总的来说,双链表是一种功能强大的数据结构,适用于需要频繁进行节点插入、删除和双向遍历的场景,但在内存占用上需要谨慎权衡。

相关文章:

【数据结构】-----双链表(小白必看!!!)

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…...

【数据结构】考研真题攻克与重点知识点剖析 - 第 8 篇:排序

前言 本文基础知识部分来自于b站&#xff1a;分享笔记的好人儿的思维导图与王道考研课程&#xff0c;感谢大佬的开源精神&#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析&#xff0c;本人技术…...

数字乡村可视化大数据-DIY拖拽式设计

DIY拖拽式大数据自由设计万村乐可视化大数据V1.0 随着万村乐数字乡村系统的广泛使用&#xff0c;我们也接收到了客户的真实反馈&#xff0c;最终在公司的决定下&#xff0c;我们推出了全新的可视化大数据平台V1.0版本&#xff0c;全新的可视化平台是一个通过拖拽配置生成可视化…...

数据集学习

1&#xff0c;CIFAR-10数据集 CIFAR-10数据集由10个类的60000个32x32彩色图像组成&#xff0c;每个类有6000个图像。有50000个训练图像和10000个测试图像。 数据集分为五个训练批次和一个测试批次&#xff0c;每个批次有10000个图像。测试批次包含来自每个类别的恰好1000个随机…...

【解决】npm run dev Syntax Error: TypeError: eslint.CLIEngine is not a constructor

问题&#xff1a; 由于代码语法不符合eslint而照成此错误&#xff0c;可以参照eslint规则修改语法&#xff0c;或者将eslint停掉 以下为停掉eslint的方法。 You may use special comments to disable some warnings. Use // eslint-disable-next-line to ignore the ne…...

Android 如何通过屏幕大小来适配不同大小的图片

可以使用Android中的dp(密度无关像素)单位来设置不同屏幕密度下的图片大小。dp是Android中的一种尺寸单位&#xff0c;它与屏幕密度无关&#xff0c;只与字体大小有关。在开发过程中&#xff0c;可以使用dp来设置布局和控件的大小&#xff0c;以便在不同的屏幕密度下保持一致的…...

【面试题】细说mysql中的各种锁

前言 作为一名IT从业人员&#xff0c;无论你是开发&#xff0c;测试还是运维&#xff0c;在面试的过程中&#xff0c;我们经常会被数据库&#xff0c;数据库中最经常被问到就是MySql。当面试官问MySql的时候经常会问道一个问题&#xff0c;”MySQL中有哪些锁&#xff1f;“当我…...

TMS320F280049 EPWM模块--TZ子模块(6)

下图是TZ子模块在epwm中的位置&#xff0c;可以看到TZ子模块接收内外部多种信号&#xff0c;经过处理后生成最终epwm波形&#xff0c;然后通过gpio向外发出。 TZ的动作有4个&#xff1a;拉高/拉低/高阻/不变。 TZ的内部框图见下图&#xff0c;可以看出&#xff1a; 1&#xf…...

数字乡村创新实践探索农业现代化路径:科技赋能农业产业升级、提升乡村治理效能与农民幸福感

随着信息技术的快速发展和数字化时代的到来&#xff0c;数字乡村建设正成为推动农业现代化、提升农业产业竞争力、优化乡村治理以及提高农民幸福感的重要途径。本文将围绕数字乡村创新实践&#xff0c;探讨其在农业现代化路径中的积极作用&#xff0c;以及如何通过科技赋能实现…...

linux中rpm包与deb包的区别及使用

文章目录 1. rpm与deb的区别2. deb软件包的格式和使用2.1 deb软件包命令遵行如下约定2.2 dpkg命令2.3 apt-命令 3. Unix和Linux的区别Reference 1. rpm与deb的区别 有的系统只支持使用rpm包安装&#xff0c;有的只支持deb包安装&#xff0c;混乱安装会导致系统问题。 关于rpm和…...

Linux中安装seata

Linux中安装seata 一、准备1、环境2、下载3、上传到服务器4、解压 二、配置1、备份配置文件2、导入sql3、修改配置前4、修改配置后5、在nacos中配置 三、使用1、启动2、关闭 一、准备 1、环境 因为要在 nacos 中配置&#xff0c;要求安装并启动 nacos 。可以参考这篇博客。 …...

预印本仓库ArXiv——防止论文录用前被别人剽窃

文章目录 一、什么是预印本二、什么是ArXiv2.1 ArXiv的领域2.2 如何使用 一、什么是预印本 预印本&#xff08;Preprint&#xff09;是指科研工作者的研究成果还未在正式出版物上发表&#xff0c;而出于和同行交流目的自愿先在学术会议上或通过互联网发布的科研论文、科技报告…...

LNMP 架构

1. 环境准备 环境准备 lnmp 需要 安装 nginx mysql php 软件 1.1 关闭防火墙 systemctl disable --now firewalld setenforce 0 1.2 安装依赖包 yum -y install pcre-devel zlib-devel gcc gcc-c make 1.3 创建运行用户、组 &#xff08;Nginx 服务程序默认以 nobody 身份…...

谈谈Python中的单元测试和集成测试

谈谈Python中的单元测试和集成测试 Python中的单元测试和集成测试是软件开发过程中的重要环节&#xff0c;它们确保了代码的质量和稳定性。单元测试主要关注代码的最小可测试单元——通常是函数或类的方法&#xff0c;而集成测试则关注这些单元之间的协作和交互。下面&#xf…...

【2024】Prometheus通过node_exporter都监控了什么

我们通过prometheus进行监控,通过node_exporter进行Linux系统的监控。 那么我们通过node_exporter都监控了什么? 目录 常用指标CPU相关内存相关磁盘相关网络相关其他指标常用监控告警案例:cpu案例:内存案例:磁盘案例:网络案例:常用指标 Prometheus通过node_exporter可以…...

Centos7配置秘钥实现集群免密登录

设备&#xff1a;MacBook Pro、多台Centos7.4服务器(已开启sshd服务) 大体流程&#xff1a;本机生成秘钥&#xff0c;将秘钥上传至服务器即可实现免密登录 1、本地电脑生成秘钥&#xff1a; ssh-keygen -t rsa -C "邮箱地址 例&#xff1a;*****.163.com"一路回车…...

Android匿名共享内存(Ashmem)

在Android中我们熟知的IPC方式有Socket、文件、ContentProvider、Binder、共享内存。其中共享内存的效率最高&#xff0c;可以做到0拷贝&#xff0c;在跨进程进行大数据传输&#xff0c;日志收集等场景下非常有用。共享内存是Linux自带的一种IPC机制&#xff0c;Android直接使用…...

MySOL之旅--------MySQL数据库基础( 3 )

本篇碎碎念:要相信啊,胜利就在前方,要是因为一点小事就停滞不前,可能你也不适合获取胜利,成功的路上会伴有泥石,但是走到最后,你会发现身上的泥泞皆是荣耀的勋章! 今日份励志文案: 凡是发生皆有利于我 目录 查询(select) 1.全列查询 2.指定列查询 3.查询字段为表达式 ​编…...

阿药陪你学Java(第零讲)

第零讲&#xff1a;基本数据类型 Java包括两种数据类型&#xff0c;分别是内置数据类型&#xff08;基本数据类型&#xff09;和引用数据类型。 内置数据类型 Java提供了8中内置类型&#xff0c;其中包括4种数字整型、2种数字浮点型、1中字符型、1中布尔型。下面进行详细介绍…...

华院计算参编《金融业人工智能平台技术要求》标准

随着人工智能技术的迅猛发展&#xff0c;金融机构正在从业务场景化向企业智能化演进&#xff0c;金融业对智能化的需求愈加迫切。为引导产业有序发展、规范行业自律、加快金融行业智能化转型&#xff0c;中国信通院依托中国人工智能产业发展联盟&#xff08;AIIA&#xff09;及…...

DbGate数据库管理工具:Docker一键部署与跨平台远程访问实战

1. 为什么选择DbGateDocker组合 第一次接触DbGate是在一个需要同时管理MySQL和MongoDB的项目中。当时团队里有人用Navicat&#xff0c;有人用DBeaver&#xff0c;数据库类型切换时总要重新适应界面。直到发现这个支持多数据库的开源工具&#xff0c;才真正体会到什么叫"一…...

3MF格式与Blender从入门到精通:重塑3D打印工作流

3MF格式与Blender从入门到精通&#xff1a;重塑3D打印工作流 【免费下载链接】Blender3mfFormat Blender add-on to import/export 3MF files 项目地址: https://gitcode.com/gh_mirrors/bl/Blender3mfFormat 概念解析&#xff1a;为什么3MF正在取代STL成为行业新标准 …...

别再手动填Token了!用Knife4j的OAuth2配置,一键搞定接口文档自动化认证

告别手动Token时代&#xff1a;Knife4j与OAuth2的自动化认证实战 每次调试API都要复制粘贴Token的日子该结束了。作为后端开发者&#xff0c;我们花了大量时间在接口文档和认证流程之间来回切换——这不仅是效率问题&#xff0c;更是一种思维中断。想象一下&#xff0c;当你的微…...

手把手调参:在TMS320F28034上实现永磁电机的高功率因数控制(附代码思路)

手把手调参&#xff1a;在TMS320F28034上实现永磁电机的高功率因数控制&#xff08;附代码思路&#xff09; 当你在调试一台采用薄膜电容的永磁电机驱动器时&#xff0c;是否遇到过这样的困境&#xff1a;明明按照教科书设计了PWM波形&#xff0c;但实测功率因数始终卡在0.92上…...

OpCore-Simplify:实现OpenCore EFI自动化生成的黑苹果配置解决方案

OpCore-Simplify&#xff1a;实现OpenCore EFI自动化生成的黑苹果配置解决方案 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 副标题&#xff1a;告别…...

交易数据一致性保障:大数据环境下的挑战

交易数据一致性保障:大数据环境下的挑战 1. 引入与连接:数字世界的"货币守卫" 想象一下:当你在电商平台下单支付后,银行显示扣款成功,但商家却显示支付失败;或者在股票交易中,你看到的股价与实际成交价格存在差异。这些看似微小的数据不一致,可能导致企业声…...

从零到一:手把手教你用海康VisionMaster完成第一个字符识别项目(附完整流程与避坑点)

从零到一&#xff1a;手把手教你用海康VisionMaster完成第一个字符识别项目&#xff08;附完整流程与避坑点&#xff09; 在工业自动化领域&#xff0c;字符识别技术正逐渐成为生产线上的"眼睛"。无论是产品追溯码读取、包装日期检测&#xff0c;还是仪表盘数值记录&…...

nlp_structbert_sentence-similarity_chinese-large实战教程:本地知识库向量化检索完整指南

nlp_structbert_sentence-similarity_chinese-large实战教程&#xff1a;本地知识库向量化检索完整指南 你是不是经常遇到这样的问题&#xff1a;面对公司内部堆积如山的文档、产品手册、客服记录&#xff0c;想找某个特定信息时&#xff0c;却像大海捞针一样困难&#xff1f;…...

OpenClaw对接Qwen3-VL:30B:飞书智能助手配置

OpenClaw对接Qwen3-VL:30B&#xff1a;飞书智能助手配置 1. 为什么选择这个组合&#xff1f; 去年我在团队内部尝试搭建一个能处理图片和文本的智能助手时&#xff0c;遇到了三个痛点&#xff1a;一是商业API调用成本太高&#xff0c;二是数据安全性无法保证&#xff0c;三是…...

手把手教你学Simulink——基于Simulink的同步整流Buck变换器效率提升仿真

目录 手把手教你学Simulink——基于Simulink的同步整流Buck变换器效率提升仿真​ 摘要​ 一、背景与挑战​ 1.1 传统二极管整流的效率瓶颈​ 1.1.1 二极管损耗机理​ 1.2 同步整流的优势与挑战​ 1.2.1 同步整流原理​ 1.2.2 核心挑战​ 1.3 设计目标​ 二、系统架构与…...