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

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

关于智能控制领域中模糊控制算法的概述

智能控制领域中的模糊控制算法是一种基于模糊逻辑的控制策略&#xff0c;它通过对模糊集合的刻画来处理模糊信息&#xff0c;从而获得模糊输出并进行控制。模糊控制算法在实际控制工程中具有良好的应用前景&#xff0c;它不但具有较强的鲁棒性和适应性&#xff0c;而且可以为复…

【干货】VS2017简介、编译、启动单项目和启动多项目

1. VS2017简单介绍 解决方案和项目的区别&#xff1a; 一般一个解决方案会有多个项目&#xff0c;一个项目里面一般只有一个main文件&#xff0c;所以需要右键单击某个项目将其设置成启动项目&#xff0c;才可以启动该项目。 2. 编译github的代码仓 一般都会有CMakeLists.t…

Go函数介绍与一等公民

Go函数介绍与一等公民 函数对应的英文单词是 Function&#xff0c;Function 这个单词原本是功能、职责的意思。编程语言使用 Function 这个单词&#xff0c;表示将一个大问题分解后而形成的、若干具有特定功能或职责的小任务&#xff0c;可以说十分贴切。函数代表的小任务可以…

基于nodejs+vue校园失物招领平台设计与实现

科学技术日新月异的如今&#xff0c;计算机在生活各个领域都占有重要的作用&#xff0c;尤其在信息管理方面&#xff0c;在这样的大背景下&#xff0c;学习计算机知识不仅仅是为了掌握一种技能&#xff0c;更重要的是能够让它真正地使用到实目 录 摘 要 I ABSTRACT II 目 录 II…

用servlet实现一个简单的猜数字游戏。

需要两个页面&#xff0c;一个jsp页面&#xff08;guess.jsp&#xff09;和servlet页面&#xff08;servlet&#xff09;。 一.jsp页面 在jsp页面中需要实现&#xff1a; 1.创建随机数并且保存在session中。 2.做个form表单提交猜的数字给servlet页面。 <%page import&…

CakePHP 3.x/4.x反序列化RCE链

最近网上公开了cakephp一些反序列化链的细节&#xff0c;但是没有公开poc&#xff0c;并且网上关于cakephp的反序列化链比较少&#xff0c;于是自己跟一下 &#xff0c;构造pop链。 CakePHP简介 CakePHP是一个运用了诸如ActiveRecord、Association Data Mapping、Front Contr…

手搭手Mybatis-Plus数据迁移至TDSQL

环境介绍 技术栈 springbootmybatis-plusdruidbaomidoumysqloracle 软件 版本 mysql 8 IDEA IntelliJ IDEA 2022.2.1 JDK 1.8 Spring Boot 2.7.13 mybatis 2.3.1 Navicat测试连接TDSQL 开启访问外网 IDEA环境搭建 pom.xml所需依赖 <dependencies><dep…

【Minecraft开服教程】使用 MCSM 面板一键搭建我的世界服务器,并内网穿透公网远程联机

文章目录 前言1.Mcsmanager安装2.创建Minecraft服务器3.本地测试联机4. 内网穿透4.1 安装cpolar内网穿透4.2 创建隧道映射内网端口 5.远程联机测试6. 配置固定远程联机端口地址6.1 保留一个固定TCP地址6.2 配置固定TCP地址 7. 使用固定公网地址远程联机 前言 MCSManager是一个…

【通义千问】大模型Qwen GitHub开源工程学习笔记(4)-- 模型的量化与离线部署

摘要: 量化方案基于AutoGPTQ,提供了Int4量化模型,其中包括Qwen-7B-Chat和Qwen-14B-Chat。更新承诺在模型评估效果几乎没有损失的情况下,降低存储要求并提高推理速度。量化是指将模型权重和激活的精度降低以节省存储空间并提高推理速度的过程。AutoGPTQ是一种专有量化工具。…

通讯网关软件023——利用CommGate X2HTTP实现HTTP访问Modbus TCP

本文介绍利用CommGate X2HTTP实现HTTP访问Modbus TCP。CommGate X2HTTP是宁波科安网信开发的网关软件&#xff0c;软件可以登录到网信智汇(http://wangxinzhihui.com)下载。 【案例】如下图所示&#xff0c;SCADA系统上位机、PLC、设备具备Modbus RTU通讯接口&#xff0c;现在…

Meta开源数字水印Stable Signature,极大增强生成式AI安全

全球社交、科技巨头Meta&#xff08;Facebook、Instagram等母公司&#xff09;在官网宣布&#xff0c;开源数字水印产品Stable Signature&#xff0c;并公开论文。 据悉&#xff0c;Stable Signature是由Meta和INRIA&#xff08;法国国家信息与自动化研究所&#xff09;联合开…

分享一个查询OpenAI Chatgpt key余额查询的工具网站

OpenAI Key 余额查询工具 欢迎使用 OpenAI Key 余额查询工具网站&#xff01;这个工具可以帮助您轻松地验证您的 OpenAI API 密钥&#xff0c;并查看您的余额。 http://tools.lbbit.top/check_key/ 什么是 OpenAI Key 余额查询工具&#xff1f; OpenAI Key 余额查询工具是一…

最详细STM32,cubeMX 按键点亮 led

这篇文章将详细介绍 如何在 stm32103 板子上使用 按键 点亮一个LED. 文章目录 前言一、如何控制按键&#xff1f;为什么按键要接上拉电阻或者下拉电阻呢&#xff1f; 二、cubeMX配置工程自动生成代码解析 三、读取引脚电平函数四、按键为什么要消抖如何消除消抖 五、实现按键控…

八大排序算法(含时间复杂度、空间复杂度、算法稳定性)

文章目录 八大排序算法(含时间复杂度、空间复杂度、算法稳定性)1、&#xff08;直接&#xff09;插入排序1.1、算法思想1.2、排序过程图解1.3、排序代码 2、希尔排序3、冒泡排序3.1、算法思想3.2、排序过程图解3.3、排序代码 4、&#xff08;简单&#xff09;选择排序4.1、算法…

小谈设计模式(27)—享元模式

小谈设计模式&#xff08;27&#xff09;—享元模式 专栏介绍专栏地址专栏介绍 享元模式模式结构分析享元工厂&#xff08;FlyweightFactory&#xff09;享元接口&#xff08;Flyweight&#xff09;具体享元&#xff08;ConcreteFlyweight&#xff09;非共享具体享元&#xff0…

竞赛选题 深度学习LSTM新冠数据预测

文章目录 0 前言1 课题简介2 预测算法2.1 Logistic回归模型2.2 基于动力学SEIR模型改进的SEITR模型2.3 LSTM神经网络模型 3 预测效果3.1 Logistic回归模型3.2 SEITR模型3.3 LSTM神经网络模型 4 结论5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 …

使用 GitHub Action 自动更新 Sealos 集群的应用镜像

在 IT 领域&#xff0c;自动化无疑已成为提高工作效率和减少人为错误的关键。Sealos 作为一个强大的云操作系统&#xff0c;已经为许多企业和开发者提供了稳定可靠的服务。与此同时&#xff0c;随着技术不断发展&#xff0c;集成更多的功能和服务变得尤为重要。考虑到这一点&am…

BAT023:将当前目录同名文件(不包括扩展名)整理到以其命名的文件夹内

引言&#xff1a;编写批处理程序&#xff0c;实现将当前目录同名文件&#xff08;不包括扩展名&#xff09;整理到以其命名的文件夹内。 一、新建Windows批处理文件 参考博客&#xff1a; CSDNhttps://mp.csdn.net/mp_blog/creation/editor/132137544 二、写入批处理代码 1.…

机器人命令表设计

演算命令 CLEAR 将数据 1 上被指定的编号以后的变数的内容&#xff0c;以及数据 2 上仅被指定的个数都清除至 0。 INC 在被指定的变数内容上加上 1。 DEC 在被指定的变数内容上减掉 1。 SET 在数据 1 上设定数据 2。 ADD 将数据 1 和数据 2 相加&#xff0c;得出的结果保存在数…

IDEA—java: 常量字符串过长问题解决

问题描述&#xff1a; Error: java: 常量字符串过长 问题分析&#xff1a; 字符串长度过长&#xff0c;导致 idea 默认使用的 javac 编译器编译不了。 解决办法&#xff1a; Javac 编译器改为 Eclipse 编译器。 File -> Settings -> Build,Execution,Deployment -&…