带头双向循环链表

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

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

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

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

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

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

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

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

尾插的插又怎么实现呢?

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

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

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

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

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

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

尾删,是怎么操作的?

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

头删的操作。

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

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

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

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

尾删我们传哨兵位的prev

头删我们传哨兵位的next

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Vue全新一代状态管理库 Pinia【一篇通】

文章目录前言1. Pinia 是什么?1.1 为什么取名叫 Pinia?1.2. 为什么要使用 Pinia ?2. 安装 Pinia2.1.创建 Store2.1.1. Option 类型 Store2.1.2 Setup 函数类型 Store2.1.3 模板中使用3. State 的使用事项(Option Store )3.1 读取 State3.2 …

EEPROM芯片(24c02)使用详解(I2C通信时序分析、操作源码分析、原理图分析)

1、前言 (1)本文主要是通过24c02芯片来讲解I2C接口的EEPROM操作方法,包含底层时序和读写的代码; (2)大部分代码是EEPROM芯片通用的,但是其中关于某些时间的要求,是和具体芯片相关的,和主控芯片和外设芯片都有关系&…

一天吃透TCP面试八股文

本文已经收录到Github仓库,该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点,欢迎star~ Github地址:https://github.com/…

vue模板语法

src目录文件说明: 1,数据绑定{{}} 数据绑定最常见的形式就是使用{{}}(双花括号)语法的文本插值 在template中使用{{}}文本插值语法中,设置一个变量,再在script中引入data函数,在return中进行数…

接口测试和性能测试有什么区别?我敢打赌你一定不知道

目录 一、什么是接口测试 二、接口测试原理 三、接口测试步骤 四、什么是性能测试 五、性能测试步骤 六、接口测试和性能测试的区别 一、什么是接口测试 接口测试是测试系统组件间接口的一种测试。接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点…

2023最全Python+Selenium环境搭建教程-你绝对想不到有这么简单!

还有视频版本结合项目实战介绍,轻松学习! PythonSelenium自动化测试环境搭建Web自动化测试全套教程_哔哩哔哩_bilibiliPythonSelenium自动化测试环境搭建Web自动化测试全套教程共计180条视频,包括:1、Web自动化测试需求和挑战、2…

深度学习-Tensorflow使用Keras进行模型训练

本文以FasionMNIST/加州房价数据集为例,介绍KerasAPI进行分类问题/回归问题模型训练的方法Tensorflow版本Tensorflow和keara都需要2.0及以上版本import tensorflow as tf from tensorflow import keras print(tf.__version__) print(keras.__version__)分类MLP构建数…

AI_Papers周刊:第六期

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 2023.03.13—2023.03.19 文摘词云 Top Papers Subjects: cs.CL 1.UPRISE: Universal Prompt Retrieval for Improving Zero-Shot Evaluation 标题:UPRISE:改进零样本评估…

要是早看到这篇文章,你起码少走3年弯路,20年老程序员的忠告

文章目录前言一、程序员的薪资是怎么样的?二、我现在的情况适合做程序员吗?三、大学期间到底应该学些什么?四、工作还是考研?五、总结前言 我是龙叔,一名工作了20多年的退休老程序员。 如果你在工作之前看到这篇文章…

【AI大比拼】文心一言 VS ChatGPT-4

摘要:本文将对比分析两款知名的 AI 对话引擎:文心一言和 OpenAI 的 ChatGPT,通过实际案例让大家对这两款对话引擎有更深入的了解,以便大家选择合适的 AI 对话引擎。 亲爱的 CSDN 朋友们,大家好!近年来&…

libcurl库访问人工智能平台之人脸识别

一、前言上一篇文章我们调用libcurl库去访问了百度,访问的是http协议的百度云主页。那么现在我们要基于翔云人工智能平台来实现人脸识别,具体的操作大概就是我们在linux下调用libcurl库去访问翔云人工智能平台,然后实现我们想要的两张人脸图片…

FPGA纯verilog实现RIFFA的PCIE通信,提供工程源码和软件驱动

目录1、前言2、RIFFA简介RIFFA概述RIFFA架构RIFFA驱动3、vivado工程详解4、上板调试验证并演示5、福利:工程代码的获取1、前言 PCIE是目前速率很高的外部板卡与CPU通信的方案之一,广泛应用于电脑主板与外部板卡的通讯,PCIE协议极其复杂&…

【Linux】基本指令介绍

前言从今天开始,我们一起来学习Linux的相关知识,今天先来介绍怎么登录Linux,并且介绍一些Linux的基本指令。使用 XShell 远程登录 Linux很多同学的 Linux 启动进入图形化的桌面. 这个东西大家以后就可以忘记了. 以后的工作中 没有机会 使用图…

蓝桥杯刷题冲刺 | 倒计时21天

作者:指针不指南吗 专栏:蓝桥杯倒计时冲刺 🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾 文章目录1.迷宫1.迷宫 题目 链接: 迷宫 - 蓝桥云课 (lanqiao.cn) 本题为填空题,只…

Three.js——learn02

Three.js——learn02Three.js——learn02通过轨道控制器查看物体OrbitControls核心代码index2.htmlindex.cssindex2.jsresult添加辅助器1.坐标轴辅助器AxesHelper核心代码完整代码2.箭头辅助器ArrowHelper核心代码完整代码3.相机视锥体辅助器CameraHelper核心代码完整代码Three…

近期投简历、找日常实习的一些碎碎念(大二---测试岗)

嘿嘿嘿,我又回来了,相信不少兄弟已经发现我似乎已经断更了好久,哈哈,我是尝试去找实习,投简历面试去了。 先说一下背景。 目录 背景 求职进行中 简历 投递和沟通 收获和感受 背景 博主,大二软件工程…

Arthas工具的基本使用

介绍 Arthas 是Alibaba开源的Java诊断工具,深受开发者喜爱。在线排查问题,无需重启;动态跟踪Java代码;实时监控JVM状态。Arthas支持JDK 6,支持Linux/Mac/Windows,采用命令行交互模式,同时提供丰…

Python截图自动化工具

1、展示部分源码(写的比较乱,哈哈) 2、功能展示 1)首页 2)按钮截图(用于自动翻页) 3)保存位置按钮(选择图片保存的位置) 4)重复次数,就是要截取多少次 5)定位截屏(截取的内容&#x…

[数据分析与可视化] Python绘制数据地图1-GeoPandas入门指北

本文主要介绍GeoPandas的基本使用方法,以绘制简单的地图。GeoPandas是一个Python开源项目,旨在提供丰富而简单的地理空间数据处理接口。GeoPandas扩展了Pandas的数据类型,并使用matplotlib进行绘图。GeoPandas官方仓库地址为:GeoP…

尚融宝06-ECMAScript基本介绍和使用

目录 一、ECMAScript 1、ECMA 2、ECMAScript 3、什么是 ECMA-262 4、ECMA-262 历史 5、ECMAScript 和 JavaScript 的关系 二、基本语法 1、let声明变量 2、const声明常量 3、解构赋值 4、模板字符串 5、声明对象简写 6、定义方法简写 7、参数的默认值 8、对象拓…
最新文章