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

带头双向循环链表

在前面我们学习了单链表,发现单链表还是有一些不够方便,比如我们要尾插,需要遍历一遍然后找到它的尾,这样时间复炸度就为O(N),现在我们引入双向带头链表就很方便了,我们先看看它的结构。

通过观察,我们发现一个结构体里面我们存两个指针,一个指向前面的,一个指向后面的,这样就是双向了,头指针指向尾,我们找尾,只需要通过头指针找,很方便,我们找一个指针节点上一个,也很便利,如果是单链表,我们还需要从头开始找。所以是带头双向循环链表真的很方便。

我们先创建一个结构体,接下来就是对它初始化了。

因为我们我们是带头的,这个哨兵位的头需要在初始化的时候创建,后面我们插入数据也需要创建节点,所以我们就将创建节点的过程写成一个函数。

我们利用一个函数创建节点,初始化时结构体里面的指针指向自己

带头双向循环链表也和单链表一样,有头插,尾插,头删,尾删,在某个位置前插入,删除。

我们先来看看插入的操作,头插

头插,我们只需要改连接关系就好。
首先,我们创捷一个节点。
然后,在哨兵的后面插入节点,改变连接关系就可以完成连接。

尾插的插又怎么实现呢?

在之前的单链表,我们还需要找尾,然后在尾的后面插入(改连接关系)

我们的带头双向循环链表的便利之处在于,我们可以快速的找到尾,我们哨兵位的prev就是链表的尾。

在某个位置前面插入我们应该怎么做?

在单链表,我们需要找到pos位置前面的地址,我们要从头开始找。带头双向循环链表的便利在于我们的pos的prev就是我们要找的地址。简单的修改连接关系,就能完成我们的插入。

写着写着,我们发现,我们在某个位置插入元素好像和头插,尾插,有相似的地址。
头插,就是在哨兵位后一个节点的前面插入,我们也可以利用在某处插入元素的函数,这样大大节省书写时间。
尾插,就是在哨兵位的前面插入,这个更加简单。
所以我们的头插,尾插,可以复用我们在某处插入的函数。

插入讲完了,下面我们来说说删除。

尾删,是怎么操作的?

在单链表我们需要找到尾,同时记录尾的前一个,我们将尾释放,将尾前一个的next置尾空指针.

头删的操作。

我们带头双向循环链表,有一个哨兵位,所以我们需要绕开它,然后删除它后面的第一个节点,然后修改连接关系。我们删除前需要判断链表是否为空。

我们发现删除好像都需要判断是否为空,我们前面的尾删也需要,所以我们需要在尾删的地方加上判断。

如何删除某个节点的,我们需要配合一个查找函数,来查找节点。

我们发现删除某个节点位置的函数也可以与头删,尾删复用。

尾删我们传哨兵位的prev

头删我们传哨兵位的next

相关文章:

  • Python自动化抖音自动刷视频
  • CANoe中使用CAPL刷写流程详解(Trace图解)(CAN总线)
  • Angular学习笔记(一)
  • 技术掉:PDF显示,使用pdf.js
  • Xinlinx zynq7045国产替代 FMQL45T900全国产化 ARM 核心板+扩展板
  • 硬刚ChatGPT!文心一言能否为百度止颓?中国版ChatGPT“狂飙”的机会在哪儿?
  • 【python】喜欢XJJ?这不得来一波大采集?
  • 用Python求解牛顿的草地与母牛问题
  • 面试官:MQ的好处到底有哪些?
  • 想要成为高级网络工程师,只需要具备这几点
  • 我在字节当主管:百次面试结果,总结一个刷掉99%求职者的问题!
  • 基于GPT-4的免费代码生成工具
  • 今年还能学java么?
  • 硬刚ChatGPT!文心一言能否为百度止颓?
  • CSS实现一个展示框
  • 【Java实战】不会还有人用if else进行参数校验吧
  • 系统架构:经典三层架构
  • 28岁小公司程序员,无车无房不敢结婚,要不要转行?
  • 十二、51单片机之DS1302
  • ES+Redis+MySQL,这个高可用架构设计太顶了!
  • HTB-baby~
  • Docker使用DockerFile部署Go项目
  • 自己设计的网站,如何实现分页功能?(详细代码+注释)
  • O2O、C2C、B2B、B2C是什么意思
  • 带你一文透彻学习【PyTorch深度学习实践】分篇——加载数据集(Dataset类、DataLoader类核心参数讲解)附:实例源代码
  • 基于html+css的图片居中排列
  • Python通用验证码识别OCR库ddddocr的安装使用
  • 「无服务器架构」无服务器架构是应用程序的正确选择?需要考虑利弊。
  • Pycharm中修改git提交代码的账户和用户名【Git追溯注解,git blame】
  • 中介变量、调节变量与协变量