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

链表(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):双链表

引入 我们之前学的单向链表有什么缺点呢&#xff1f; 缺点&#xff1a;后一个节点无法看到前一个节点的内容 那我们就多设置一个格子prev用来存放前面一个节点的地址&#xff0c;第一个节点的prev存最后一个节点的地址&#xff08;一般是null&#xff09; 这样一个无头双向…...

【TES720D】基于复旦微的FMQL20S400全国产化ARM核心模块

TES720D是一款基于上海复旦微电子FMQL20S400的全国产化核心模块。该核心模块将复旦微的FMQL20S400&#xff08;兼容FMQL10S400&#xff09;的最小系统集成在了一个50*70mm的核心板上&#xff0c;可以作为一个核心模块&#xff0c;进行功能性扩展&#xff0c;特别是用在控制领域…...

Python 列表切片陷阱:引用、复制与深复制

大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 如果有什么疑惑/资料需要的可以点击文章末尾名片领取源码 Python 列表的切片和赋值操作很基础&#xff0c;之前也遇到过一些坑&#xff0c; 但今天刷 Codewars 时发现了一个更大的坑&#xff0c;故在此记录。 Python 列表赋值&am…...

macbook电脑删除app怎么才能彻底清理?

macBook是苹果公司推出的一款笔记本电脑&#xff0c;它的操作系统是macOS。在macBook上安装的app可能会占用大量的存储空间&#xff0c;因此&#xff0c;当我们不再需要某个app时&#xff0c;需要将其彻底删除。macbook删除app&#xff0c;怎么才能彻底呢&#xff1f;本文将给大…...

【数据结构】二叉树--链式结构的实现 (遍历)

目录 一 二叉树的遍历 1 构建一个二叉树 2 前序遍历 3 中序遍历 4 后续遍历 5 层序 6 二叉树销毁 二 应用(递归思想) 1 二叉树节点个数 2 叶子节点个数 3 第K层的节点个数 4 二叉树查找值为x的节点 5 判断是否是二叉树 一 二叉树的遍历 学习二叉树结构&#xff0…...

reids基础数据结构

文章目录 一.整体1.RedisDb2.对象头 二.string三.list1.ziplist2.quicklist 四.hash五.set六.zset1.查找2.插入3.删除4.更新5.元素排名 一.整体 1.RedisDb redis内部的所有键值对是两个hash结构&#xff0c;维护了键值对和过期时间 dict *dictdict *expire 2.对象头 int t…...

gitlab 维护

一 环境信息 二 日常维护 2.1 gitlab mirror 2.1.1 常见方法 社区版本gitab mirror 只能push&#xff0c;默认限制了局域网内mirror 需要修改admin/setting/network(网络)/outbound(出站请求) 勾选允许局域网即可。 2.1.2 疑难问题 内网有三个gitlab A: GITLAB 12 B\C GI…...

ABB机器人RWS连接方法

目录 方法一&#xff1a;curl 方法二&#xff1a;网页地址 方法三&#xff1a;Postman 与ABB机器人通讯&#xff0c;较新机器人&#xff0c;可以使用Robot Web Services&#xff0c;直接方便地使用网页进行查看当前数据&#xff0c;但是网页需要用户名密码验证&#xff0c;测…...

Spring Boot的循环依赖问题

目录 1.循环依赖的概念 2.解决循环依赖的方法 1.构造器方法注入&#xff1a; 2.Lazy注解 3.DependsOn注解 1.循环依赖的概念 两个或多个bean之间互相依赖&#xff0c;形成循环&#xff0c;此时&#xff0c;Spring容器无法确定先实例化哪个bean&#xff0c;导致循环依赖的…...

postgresql|数据库|恢复备份的时候报错:pg_restore: implied data-only restore的处理方案

一&#xff0c; 前情回顾 某次在使用pg_dump命令逻辑备份出来的备份文件对指定的几个表恢复的时候&#xff0c;报错pg_restore: implied data-only restore 当然&#xff0c;遇到问题首先就是百度了&#xff0c;但好像没有什么明确的解决方案&#xff0c;具体的报错命令和…...

Elasticsearch:使用 Langchain 和 OpenAI 进行问答

这款交互式 jupyter notebook 使用 Langchain 将虚构的工作场所文档拆分为段落 (chunks)&#xff0c;并使用 OpenAI 将这些段落转换为嵌入并将其存储到 Elasticsearch 中。然后&#xff0c;当我们提出问题时&#xff0c;我们从向量存储中检索相关段落&#xff0c;并使用 langch…...

安全巡检管理系统—隐患排查治理

安全管理越来越重要&#xff0c;每个生产企业都需要一个安全隐患排查治理小程序&#xff01;利用凡尔码平台搭建安全巡检管理系统主要有以下四个功能 1、制定巡检计划&#xff1a;安全巡检管理系统可以帮助用户制定巡检计划&#xff0c;用户可以根据需要创建不同的计划&#xf…...

第9期ThreadX视频教程:自制个微秒分辨率任务调度实现方案(2023-10-11)

视频教程汇总帖&#xff1a;【学以致用&#xff0c;授人以渔】2023视频教程汇总&#xff0c;DSP第12期&#xff0c;ThreadX第9期&#xff0c;BSP驱动第26期&#xff0c;USB实战第5期&#xff0c;GUI实战第3期&#xff08;2023-10-11&#xff09; - STM32F429 - 硬汉嵌入式论坛 …...

C++ 11 lamdba表达式详解

C lamdba 表达式 Lambda表达式是C11引入的一个新特性&#xff0c;它允许我们在需要函数对象的地方&#xff0c;使用一种更加简洁的方式定义匿名函数。Lambda表达式通常用于STL中的算法、回调函数、事件处理程序等场合。 Lambda表达式的基本语法为&#xff1a; Copy Code[captu…...

Linux运行环境搭建系列-Zookeeper安装

Zookeeper安装 ## 下载Zookeeper&#xff1a;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 ## 删除原文件&#xff0c;重命名 r…...

vscode利用lauch.json和docker中的delve调试本地crdb

---- vscode利用delve调试crdb 创建了一个delve容器用于debug crdbdelve&#xff1a; Delve是一个用于Go编程语言的调试器。它提供了一组命令和功能&#xff0c;可以帮助开发人员在调试过程中检查变量、设置断点、单步执行代码等操作。Delve可以与Go程序一起使用&#xff0c;…...

【java|golang】多字段排序以及排序规则

奖励最顶尖的 K 名学生 给你两个字符串数组 positive_feedback 和 negative_feedback &#xff0c;分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。 一开始&#xff0c;每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分&#xff0c;每个负面的词…...

腾讯云 轻量云 上海 VPS 测评

description: 发布于 2023-07-05腾讯云 轻量云 上海 VPS 测评 腾讯云国内机非常稳定&#xff0c;一年用下来没有掉线丢包的情况。国内机适合与备案域名一起建站使用。带宽很小&#xff0c;图片资源使用CDN加速或海外机提供。 规格 CPU - 2核 内存 - 2GB 系统盘 - SSD云硬盘…...

消息称苹果或在明年推出搭载M3芯片的MacBook产品

近日据 DigiTimes 发布的博文&#xff0c;苹果公司计划在 2024 年推出搭载 M3 芯片的 MacBook 产品。然而&#xff0c;关于这款新产品的发布日期仍存在争议。虽然一些爆料认为苹果可能会在今年发布这款产品&#xff0c;但也有一些爆料认为发布时间会推迟到 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 …...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...