链表(3):双链表
引入
我们之前学的单向链表有什么缺点呢?
缺点:后一个节点无法看到前一个节点的内容
那我们就多设置一个格子prev用来存放前面一个节点的地址,第一个节点的prev存最后一个节点的地址(一般是null)
这样一个无头双向链表就造好啦😊
老规矩,手搓双链表
初始
和单链表一样,我们也是实现IList接口的方法
初始化差不多,可以去看我前面的博客
数据结构:链表(1)_cx努力编程中的博客-CSDN博客
跟前驱没关系的函数我先放进来
@Overridepublic boolean contains(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}@Overridepublic int size() {int count = 0;ListNode cur = this.head;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void display() {ListNode cur = head;while(cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}
插入
头插法
实例化一个node,如果只有一个节点的话就把head和last都放在这个节点的下面
node.next = head;
head.prev = node;
head = node;//把head的位置放到node这里
public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null){head = node;last = node;}else{node.next = this.head;head.prev = node;head = node;}}
尾插法
跟单链表不一样的是,双链表有last,所以时间复杂度是O(1)
@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null){head = node;last = node;}else{last.next = node;node.prev = head;last = node;}}
指定位置插入
比如我们实例化一个节点,想要将其插入到1和2之间
那么我们就要将cur移动到2的位置(走index步)
这个cur的前驱(节点1)的next就是这个新节点的地址
node.next = cur
cur.prev.next = node(0x123)
node.prev = cur.prev
cur.prev = node
代码:
@Overridepublic void addIndex(int index, int data) {//检查index是否异常int len = size();if(index < 0 || index > len){System.out.println("异常索引"+index);return;}if(index == 0){//头插法addFirst(data);return;}if(index == len){//尾插法addLast(data);return;}ListNode cur = findIndex(index);ListNode node = new ListNode(data);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}
删除
假如删除中间45这个节点,先让cur走到这个节点,再让45前一个节点的地址等于45后一个节点地址,让45后一个节点的前驱等于45前一个节点的地址
但是假如要删除的是13这个节点(头节点),那么cur.prev.next = cur.next这行代码有问题
所以我们这么干,直接把头节点的后一个节点的前驱prev置为null就行了
if(cur == head){head = head.next;head.prev = null;
假如要删除的是56这个节点(尾节点),那么cur.next.prev = cur.prev这行代码有问题
那我们这么干,直接把尾节点的前一个节点的next置为null就行了
cur.prev.next = cur.next;
last = last.prev;
我们发现尾节点的删除和中间节点删除有一行代码是一样的
cur.prev.next = cur.next;
我们可以把它作为这二者的公用代码
cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else {cur.next.prev = cur.prev;}
其实这段代码还存在问题
当链表只有一个元素的时候,
head = head.next //这行代码一走完表明head此时已经是空的了,下一行代码还说head.prev就根本不存在(注意:head.prev = null是赋值操作,首先你得有head.prev才能进行赋值)
更改代码:
整个remove代码
@Overridepublic void remove(int key) {ListNode cur = head;while(cur != null){if(cur.val == key){if(cur == head){head = head.next;if(head == null){last = null;}else{head.prev = null;}}else {cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else {cur.next.prev = cur.prev;}}return;}else{cur = cur.next;}}}
删除指定值的所有相同值的节点
跟上面的代码很像,区别就是删除之后不要return,让cur继续往下走
@Overridepublic void removeAllKey(int key) {ListNode cur = head;while(cur != null){if(cur.val == key) {if (cur == head) {head = head.next;if (head == null) {last = null;} else {head.prev = null;}} else {cur.prev.next = cur.next;if (cur.next == null) {last = last.prev;} else {cur.next.prev = cur.prev;}}}cur = cur.next;}}
清除链表
暴力方法:
head = null; last = null;
细致方法:
定义一个cur,遍历整个链表,每到一个节点就把prev和next都置为空
@Overridepublic void clear() {ListNode cur = head;while(cur!=null){ListNode curNext = cur.next;//防止将这个节点的next置为空之后,cur没办法继续遍历cur.prev = null;cur.next = null;cur = curNext;}}
总结:
ArrayList和LinkedList的区别是?
如果是经常根据下标查找的,使用顺序表(ArrayList)或者数组
如果经常进行插入和删除操作的,就使用链表(LinkedList)
相关文章:
链表(3):双链表
引入 我们之前学的单向链表有什么缺点呢? 缺点:后一个节点无法看到前一个节点的内容 那我们就多设置一个格子prev用来存放前面一个节点的地址,第一个节点的prev存最后一个节点的地址(一般是null) 这样一个无头双向…...
【TES720D】基于复旦微的FMQL20S400全国产化ARM核心模块
TES720D是一款基于上海复旦微电子FMQL20S400的全国产化核心模块。该核心模块将复旦微的FMQL20S400(兼容FMQL10S400)的最小系统集成在了一个50*70mm的核心板上,可以作为一个核心模块,进行功能性扩展,特别是用在控制领域…...
Python 列表切片陷阱:引用、复制与深复制
大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 如果有什么疑惑/资料需要的可以点击文章末尾名片领取源码 Python 列表的切片和赋值操作很基础,之前也遇到过一些坑, 但今天刷 Codewars 时发现了一个更大的坑,故在此记录。 Python 列表赋值&am…...
macbook电脑删除app怎么才能彻底清理?
macBook是苹果公司推出的一款笔记本电脑,它的操作系统是macOS。在macBook上安装的app可能会占用大量的存储空间,因此,当我们不再需要某个app时,需要将其彻底删除。macbook删除app,怎么才能彻底呢?本文将给大…...
【数据结构】二叉树--链式结构的实现 (遍历)
目录 一 二叉树的遍历 1 构建一个二叉树 2 前序遍历 3 中序遍历 4 后续遍历 5 层序 6 二叉树销毁 二 应用(递归思想) 1 二叉树节点个数 2 叶子节点个数 3 第K层的节点个数 4 二叉树查找值为x的节点 5 判断是否是二叉树 一 二叉树的遍历 学习二叉树结构࿰…...
reids基础数据结构
文章目录 一.整体1.RedisDb2.对象头 二.string三.list1.ziplist2.quicklist 四.hash五.set六.zset1.查找2.插入3.删除4.更新5.元素排名 一.整体 1.RedisDb redis内部的所有键值对是两个hash结构,维护了键值对和过期时间 dict *dictdict *expire 2.对象头 int t…...
gitlab 维护
一 环境信息 二 日常维护 2.1 gitlab mirror 2.1.1 常见方法 社区版本gitab mirror 只能push,默认限制了局域网内mirror 需要修改admin/setting/network(网络)/outbound(出站请求) 勾选允许局域网即可。 2.1.2 疑难问题 内网有三个gitlab A: GITLAB 12 B\C GI…...
ABB机器人RWS连接方法
目录 方法一:curl 方法二:网页地址 方法三:Postman 与ABB机器人通讯,较新机器人,可以使用Robot Web Services,直接方便地使用网页进行查看当前数据,但是网页需要用户名密码验证,测…...
Spring Boot的循环依赖问题
目录 1.循环依赖的概念 2.解决循环依赖的方法 1.构造器方法注入: 2.Lazy注解 3.DependsOn注解 1.循环依赖的概念 两个或多个bean之间互相依赖,形成循环,此时,Spring容器无法确定先实例化哪个bean,导致循环依赖的…...
postgresql|数据库|恢复备份的时候报错:pg_restore: implied data-only restore的处理方案
一, 前情回顾 某次在使用pg_dump命令逻辑备份出来的备份文件对指定的几个表恢复的时候,报错pg_restore: implied data-only restore 当然,遇到问题首先就是百度了,但好像没有什么明确的解决方案,具体的报错命令和…...
Elasticsearch:使用 Langchain 和 OpenAI 进行问答
这款交互式 jupyter notebook 使用 Langchain 将虚构的工作场所文档拆分为段落 (chunks),并使用 OpenAI 将这些段落转换为嵌入并将其存储到 Elasticsearch 中。然后,当我们提出问题时,我们从向量存储中检索相关段落,并使用 langch…...
安全巡检管理系统—隐患排查治理
安全管理越来越重要,每个生产企业都需要一个安全隐患排查治理小程序!利用凡尔码平台搭建安全巡检管理系统主要有以下四个功能 1、制定巡检计划:安全巡检管理系统可以帮助用户制定巡检计划,用户可以根据需要创建不同的计划…...
第9期ThreadX视频教程:自制个微秒分辨率任务调度实现方案(2023-10-11)
视频教程汇总帖:【学以致用,授人以渔】2023视频教程汇总,DSP第12期,ThreadX第9期,BSP驱动第26期,USB实战第5期,GUI实战第3期(2023-10-11) - STM32F429 - 硬汉嵌入式论坛 …...
C++ 11 lamdba表达式详解
C lamdba 表达式 Lambda表达式是C11引入的一个新特性,它允许我们在需要函数对象的地方,使用一种更加简洁的方式定义匿名函数。Lambda表达式通常用于STL中的算法、回调函数、事件处理程序等场合。 Lambda表达式的基本语法为: Copy Code[captu…...
Linux运行环境搭建系列-Zookeeper安装
Zookeeper安装 ## 下载Zookeeper:https://zookeeper.apache.org/releases.html https://dlcdn.apache.org/zookeeper/zookeeper-3.8.3/apache-zookeeper-3.8.3-bin.tar.gz ## 解压 tar -zxvf apache-zookeeper-3.8.3-bin.tar.gz ## 删除原文件,重命名 r…...
vscode利用lauch.json和docker中的delve调试本地crdb
---- vscode利用delve调试crdb 创建了一个delve容器用于debug crdbdelve: Delve是一个用于Go编程语言的调试器。它提供了一组命令和功能,可以帮助开发人员在调试过程中检查变量、设置断点、单步执行代码等操作。Delve可以与Go程序一起使用,…...
【java|golang】多字段排序以及排序规则
奖励最顶尖的 K 名学生 给你两个字符串数组 positive_feedback 和 negative_feedback ,分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。 一开始,每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分,每个负面的词…...
腾讯云 轻量云 上海 VPS 测评
description: 发布于 2023-07-05腾讯云 轻量云 上海 VPS 测评 腾讯云国内机非常稳定,一年用下来没有掉线丢包的情况。国内机适合与备案域名一起建站使用。带宽很小,图片资源使用CDN加速或海外机提供。 规格 CPU - 2核 内存 - 2GB 系统盘 - SSD云硬盘…...
消息称苹果或在明年推出搭载M3芯片的MacBook产品
近日据 DigiTimes 发布的博文,苹果公司计划在 2024 年推出搭载 M3 芯片的 MacBook 产品。然而,关于这款新产品的发布日期仍存在争议。虽然一些爆料认为苹果可能会在今年发布这款产品,但也有一些爆料认为发布时间会推迟到 2024 年。根据各项报…...
Generalizable NeRF in ICCV‘23
文章目录 前置知识Generalizable《Enhancing NeRF akin to Enhancing LLMs: Generalizable NeRF Transformer with Mixture-of-View-Experts》《WaveNeRF: Wavelet-based Generalizable Neural Radiance Fields》NeO 360: Neural Fields for Sparse View Synthesis of Outdoor …...
Unity2017适配安卓12
测试版本为Unity2017.4.25f1 1.在自定义AndroidManifest.xml(位于Assets\Plugins\Android\)中添加android:exported"true" <?xml version"1.0" encoding"utf-8"?> <manifestxmlns:android"http://schema…...
ios UI 基础开发一
目录 第一节:基础库 第二节:弹出模拟器的键盘 第三节:模拟器回到桌面 第四节:Viewcontroller 与 View 的关系 第五节:快捷键 第六节:键盘召回 第七节:启动流程xcode介绍 第八节…...
echarts一些配置项的使用
前言:我是自己最近写项目用到的,我做个整理; 一. 基本使用 1.具有大小(宽高)的div ,id唯一; 例如: <div id"crewEchart"></div> 2.在项目中引入: import * as echarts from "echarts"; 3.写一个关于他的方法,在mounted的时候调用: moun…...
python yaml库:safe_load()(安全解析函数,解析yaml)(防止yaml文件中包含恶意代码)
文章目录 Python YAML: 使用 safe_load 进行安全解析什么是 safe_load?如何使用 safe_load?为什么选择 safe_load 而非 load? Python YAML: 使用 safe_load 进行安全解析 YAML (YAML Ain’t Markup Language) 是一种人类可读的数据序列化标准。它被广泛用于配置文件、多语言…...
小程序:下拉刷新+上拉加载+自定义导航栏
下拉刷新 : <scroll-view scroll-y"true" 允许纵向滚动 refresher-enabled"true" 开启自定义下拉刷新 默认为false :refresher-triggered&quo…...
判断两个二叉树是否相等
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//两个都为空if(pNULL&&qNULL){return true;}//有一个为空if(pNULL||qNULL){return false;}//两个不为空,但值不相同if(p->val!q->val){return false;}//值相同return isSameTree(p->le…...
springcloud----检索中间件 ElasticSearch 分布式场景的运用
如果对es的基础知识有不了解的可以看 es看这个文章就会使用了 1.分布式集群场景下的使用 单机的elasticsearch做数据存储,必然面临两个问题:海量数据存储问题、单点故障问题。 海量数据存储问题:将索引库从逻辑上拆分为N个分片(…...
qt创建线程类并实现通信 C++
需求描述: 通过VS创建了一个QT项目,我需要一个线程类去实时获取设备取流的图像,并将图像传给qt的类用于在QLabel上显示。 实现: 头文件: //include ...省略//Qt界面的类Your_Project class Your_Project : public Q…...
【elasticsearch】使用自建证书搭建elasticsearch8.0.1集群
概述 本文将分享使用自建证书搭建加密的es集群,如果想使用rpm包安装,前期的搭建过程请参考上面一篇文章https://blog.csdn.net/margu_168/article/details/133344675。后续的操作与使用tar包安装的类似,只是需要注意目录的区别。 es8.0.1安…...
一篇文章带你用动态规划解决打家劫舍问题
动态规划的解题步骤可以分为以下五步,大家先好好记住 1.创建dp数组以及明确dp数组下标的含义 2.制定递推公式 3.初始化 4.遍历顺序 5.验证结果 根据打家劫舍的题意:两个直接相连的房子在同一天晚上被打劫会触发警报 所以我们制定出核心策略——偷东…...
idea中导入eclipse的javaweb项目——tomact服务(保姆级别)
idea中导入eclipse的javaweb项目——tomact服务(保姆级别) 1. 导入项目2. Project Settings下的各种配置步骤2.1 检查/修改 jdk 的引入2.2 配置Modules-Dependencies2.2.1 删掉eclipse相关的多余配置2.2.2 删掉jar包2.2.3 添加tomcat的依赖 2.3 配置Libr…...
【开源】给ChatGLM写个,Java对接的SDK
作者:小傅哥 - 百度搜 小傅哥bugstack 博客:bugstack.cn 沉淀、分享、成长,让自己和他人都能有所收获!😄 大家好,我是技术UP主小傅哥。 清华大学计算机系的超大规模训练模型 ChatGLM-130B 使用效果非常牛&…...
基于Pytest+Allure+Excel的接口自动化测试框架
1. Allure 简介 简介 Allure 框架是一个灵活的、轻量级的、支持多语言的测试报告工具,它不仅以 Web 的方式展示了简介的测试结果,而且允许参与开发过程的每个人可以从日常执行的测试中,最大限度地提取有用信息。 Allure 是由 Java 语言开发的…...
20.2 FMC驱动SDRAM的时序初始化实现及内存测试
继续上一篇的话题,写到SDRAM通过CubeMx配置后,在工程代码编写时直接引用的是我事先写好的时序初始化、内存测试文件,而未对其进行详细的解释,所以本篇文章就来娓娓道来。不多说,开始吧 SDRAM的初始化流程简述 SDRAM初…...
联想电脑一键重装系统Win10操作方法
很多用户都会利用重装系统的方法,来解决系统崩溃、病毒感染等问题。但是,很多新手用户不知道联想电脑Win10系统重装的详细方法步骤,下面小编给大家详细介绍关于联想电脑Win10系统重装的操作方法,帮助大家轻松快速地完成系统的重装…...
Mysql数据库 1.概述
Mysql内容概述 1. Mysql概述 数据库相关概念: 名称 全称 简称 数据库 存储数据的仓库,数据是有组织的进行存储 …...
Qt编程,文件操作、UDP通信
目录 1、文件类 QFile 2、 UPD/TCP网络编程 1、##UDP客户端 2、##UDP服务器端 1、文件类 QFile QFile file(filename); file.exists() file.setFileName(filename1); file.fileName() file.bytesAvailable() file.size() file.copy("2.txt") file1.errorString(…...
Docker 的数据管理和Dockerfile镜像的创建
目录 Docker 的数据管理 管理 Docker 容器中数据的方式 端口映射 容器互联(使用centos镜像) Docker 镜像的创建 Dockerfile 操作常用的指令 编写 Dockerfile 时格式 Dockerfile 案例 Docker 的数据管理 管理 Docker 容器中数据的方式 管理 Doc…...
[python] 利用 Pydoc 快速生成整个 Python 项目的文档
如何写注释 class MyClass:"""This is a simple example class.Attributes:param1 (int): The first parameter.param2 (str): The second parameter."""def __init__(self, param1, param2):"""The constructor for MyClass.:p…...
Maven 配置指南
目录 一、配置本地存储库 二、配置并行Artifact 解析 三、安全和部署设置 四、将镜像用于存储库 五、Profiles 六、可选配置 七、Settings 八、安全性 九、工具链 Maven配置发生在3个级别: 项目-大多数静态配置发生在pom.xml中安装-这是为Maven安装添加的…...
第十八章 类和对象——多态
一、多态的基本概念 多态是C面向对象三大特性之一 多态分为两类 静态多态: 函数重载 和 运算符重载属于静态多态,复用函数名 动态多态: 派生类和虚函数实现运行时多态 静态多态和动态多态区别: 静态多态的函数地址早绑定 - 编译阶段确定函数地址 动…...
京东数据平台:2023年服饰行业销售数据分析
最近看到有些消费机构分析,不少知名的运动品牌都把“主战场”放到了冲锋衣,那么羽绒服市场就比较危险了。但其实羽绒服市场也有机会点可寻。 先来说冲锋衣。的确,从今年的销售数据以及增长情况,冲锋衣的确会是今年冬天的大热门品…...
Nginx proxy_set_header参数设置
一、不设置 proxy_set_header Host 不设置 proxy_set_header Host 时,浏览器直接访问 nginx,获取到的 Host 是 proxy_pass 后面的值,即 $proxy_host 的值,参考Module ngx_http_proxy_module 1 2 3 4 5 6 7 8 # cat ngx_header.c…...
如何用 ChatGPT 的 Advanced Data Analysis 帮你采集数据?
(注:本文为小报童精选文章,已订阅小报童或加入知识星球「玉树芝兰」用户请勿重复付费) 想采集网页数据却不会写 Python 爬虫?不会就不会吧,ChatGPT 会就可以了 😂 问题描述 朋友最近遇到了一点儿…...
Linux运行环境搭建系列-Flink安装
Flink安装 ## 下载 https://archive.apache.org/dist/flink/flink-1.16.2 ## 解压 tar -zxvf flink-1.16.2-bin-scala_2.12.tgz && rm -rf flink-1.16.2-bin-scala_2.12.tgz ## 启动 cd flink-1.16.2/bin ## 修改/etc/hosts文件,把第一行的127.0.0.1改成自…...
求最大bit数(java)
题目描述 求一个int类型数字对应的二进制数字中1的最大连续数 例如3的二进制为00000011,最大连续2个1 数据范围:数据组数:11t15,11n1500000进阶: 时间复杂度: O(logn),空间复杂度: O(1) 输入: 200 输出 2 说明 200的二进制表示是11001000&am…...
【Java 进阶篇】JavaScript 与 HTML 的结合方式
JavaScript是一种广泛应用于Web开发中的脚本语言,它与HTML(Hypertext Markup Language)结合使用,使开发人员能够创建交互式和动态的网页。在这篇博客中,我们将深入探讨JavaScript与HTML的结合方式,包括如何…...
华为云云耀云服务器L实例评测 | 实例评测使用之硬件参数评测:华为云云耀云服务器下的 Linux 磁盘目录分析神器 ncdu
华为云云耀云服务器L实例评测 | 实例评测使用之硬件参数评测:华为云云耀云服务器下的 Linux 磁盘目录分析神器 ncdu 介绍华为云云耀云服务器 华为云云耀云服务器 (目前已经全新升级为 华为云云耀云服务器L实例) 华为云云耀云服务器…...
Linux大老都是怎么记住这么多命令的?
今天给大家带来的是面试/实际工作中经常用到的Linux相关操作命令: 一. vi/vim编辑器 ---->文本编辑器 作用:创建文件,编辑文件,查看文件 格式:vi/vim 文件的名字 解析:如果该文件不存在,vi就会创建该…...
LoRa技术未来发展前景:物联网和边缘计算的引领者
随着物联网和边缘计算的快速发展,低功耗广域网(LoRa)技术在连接远距离设备、实现长距离通信和满足低功耗需求方面崭露头角。本文将分析LoRa技术在未来的发展前景,尤其是在物联网和边缘计算领域的潜在影响。 LoRa技术的核心优势 1…...