双向链表的基本结构及功能实现

1.基本结构:

双向链表是一种链表数据结构,它由一系列节点组成,每个节点包含三个部分:

(1).数据域:存储节点的数据

(2).前驱指针:指向前一个节点

(3).后驱指针:指向下一个节点

2.基本特性:

双向链接:   与单向链表不同,双向链表的每个节点都可以向前和向后移动,这使得在链表中插入和删除节点更加灵活。

3.基本操作:

我们要实现的功能:

addFirst(头插) 、 addLast(尾插)、disPlay(展示)、size(数组长度)、contains(是否包含某个元素)、 index(在某个节点处插入某个元素)、remove(移除某个元素)、removeAllKey(移除所有符合元素)、clear(清除所有数据),当然这些方法都要在接口List中都要进行定义。

3.0 双向链表基本结构的实现:

(1).包含基本结构:数据域、前驱指针、后驱指针

(2) 构造方法的实现:每个数据域对应的值输入(整数)

  (3). 头节点、尾节点的定义

具体代码如下:

 static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val = val;}}public  ListNode head; //头节点public ListNode last;   //尾节点

3.1 头插方法的实现:

1.创建一个node 节点

2.判断头节点是否为空(链表是否为空),为空的话,将头尾节点均置为空。

3. 插入元素:将node.next = head, head.prev = node    

head = node;(更新头节点)

具体代码如下:

 public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null){head = last = null;}else{node.next = head;head.prev = node;head = node;}}

3.2 尾插方法的实现:

1.创建一个新节点node储存新元素

2.判断头节点是否为空

3.插入元素:具体代码如下:

@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null){head = last = null;}else{last.next = node;node.prev = last;last = last.next;}}

3.3 disPlay方法的实现:

1.创建新节点cur 来保存头节点。

2.while循环遍历打印元素,同时更新cur节点

具体代码如下:

 public void disPlay() {ListNode cur = head;while(cur!=null){System.out.println(cur.val);cur = cur.next;}System.out.println();}

3.4 size()方法的实现:

1.创建一个保存头节点的cur节点,以及一个用于记录整形的变量len,while循环,每次len++ 并更新cur节点,最后返回len的值。

具体代码如下:

@Overridepublic int size() {int len = 0;ListNode cur = head;while(cur!=null){len++;cur = cur.next;}return len;}

3.5 contains方法的实现:

1.创建一个新节点cur来保存头节点

2.while循环,遍历过程中判断data是否 == cur.val,是的话,返回true,否则返回false,具体代码如下:

public boolean contains(int key) {ListNode cur = head;while(cur!=null){if(cur.val == key){return true;}cur = cur.next;}return false;}

3.6:index方法的实现:

1.判断给出的index位置是否合理:<0/ >len(链表长度),返回。

2.若index == 0,头插,   index == len,尾插

3.创建findIndex方法,找到位于index位置处的节点。

ListNode cur = head,while循环(index不为0)遍历cur进入下一个节点,同时index自减1,

循环结束返回cur。    具体代码如下:

private ListNode findIndex(int index){ListNode cur = head;while( index !=0){cur = cur.next; //到达index位置处index--;}return cur;}

4.插入 node节点:

3.7 remove方法的实现:

创建一个cur节点来存储head节点,while循环cur!=null,循环结束cur要更新至下一个节点

1.头删的实现:

2.尾删的情况:

3.中间情况的实现

具体代码实现:

public void remove(int key) {ListNode cur = head;while(cur!=null){if(cur.val == key){if(cur == head){head = head.next;if(cur!=null){cur.prev = null;}else{cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else{cur.next.prev = cur.prev;}}return ;}cur = cur.next;}}}

3.8 removeAllkey方法的实现:

将remove方法中的return去掉即可,这样消除了一个元素后可以继续遍历循环删除。

3.9 clear方法的实现:

创建新节点cur储存head,while循环遍历链表,设置curN节点为cur的下一个节点,在cur清除当前节点元素后,cur = curN, cur进入下一个位置即curN,进入下一次循环后curN再次后移。

最后,遍历结束后head节点和尾节点要手动置为null。

具体代码如下:

 @Overridepublic void clear() {ListNode cur = head;while(cur!=null){ListNode  curN = cur.next;cur.next = null;cur.prev = null;cur = curN;}head = last = null;}
}

今天分享结束,喜欢的老来个三联把!

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

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

相关文章

【WPF】02 按钮控件圆角配置及状态切换

按钮圆角 先从工具箱里拖进来一个Button控件&#xff0c;然后对这个按钮进行美化。 首先在 xaml 里按钮控件部分 添加如下代码&#xff1a; <Button x:Name"btnLogin" Content"登录" HorizontalAlignment"Center" Margin"0,399,0,0&q…

C++20中头文件compare的使用

<compare>是C20中新增加的头文件&#xff0c;此头文件是language support库的一部分。它包括&#xff1a;concepts、classes、customization point objects、functions。 1.concepts&#xff1a;三向比较运算符<>&#xff0c;目的是简化比对对象的过程&#xff0c;…

微服务配置管理——动态路由

动态路由 网关的路由配置全部是在项目启动时由org.springframework.cloud.gateway.route.CompositeRouteDefinitionLocator在项目启动的时候加载&#xff0c;并且一经加载就会缓存到内存中的路由表内&#xff08;一个Map&#xff09;&#xff0c;不会改变。也不会监听路由变更新…

【PG备份恢复】基于时间点的恢复(踩坑指南)

1 设置基于时间点恢复所需的配置 1.1 修改配置文件 postgresql.conf vim postgresql.conf archive_mode on archive_command cp %p /data1/backups/pg_wal_archive/%f wal_level replica 1.2 生效配置 2 进行一次全备 2.1 创建备份目录 mkdir -p /data/backup/pg_b…

C语言常见字符串函数模拟实现一:(strlen,strcpy,strcat,strcmp,strstr )

strlen模拟实现 重点&#xff1a;1.字符串已经\0作为结束标志&#xff0c;strlen返回的是字符串\0前面出现的字符个数&#xff08;不包含\0&#xff09; 2.参数指向的字符串必须要以\0结束。 3.注意函数的返回值是size_t&#xff0c;是无符号的&#xff0c;加减是无法对比的。…

thinkphp8 从入门到放弃(后面会完善用到哪里写到哪)

thinkphp8 从入门到放弃 引言 thinkphp* 大道至简一、 thinkphp8 安装安装Composerthinkphp 安装命令(tp-项目名称)多应用安装&#xff08;一个项目不会只有一个应用&#xff09;安装完文件目录如下本地部署配置伪静态好了项目可以run 二、架构服务&#xff08;Service&#xf…

大数据新视界 --大数据大厂之探索ES:大数据时代的高效搜索引擎实战攻略

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

app自动化前置准备环境搭建

编写脚本之前的一些前置准备工作。 1&#xff0c;安装appium server&#xff1a;官网地址&#xff1a;http://appium.io/ 安装教程&#xff1a;https://www.cnblogs.com/gancuimian/p/16536322.html 2&#xff0c;安装appium客户端&#xff1a; appium客户端安装相对较简单…

智谱清影 - CogVideoX-2b-部署与使用

&#x1f351;个人主页&#xff1a;Jupiter. &#x1f680; 所属专栏&#xff1a;Linux从入门到进阶 欢迎大家点赞收藏评论&#x1f60a; 目录 体验地址&#xff1a;[丹摩DAMODEL官网](https://www.damodel.com/console/overview) CogVideoX 简介本篇将详细介绍使用丹摩服务器部…

OpenAI GPT o1技术报告阅读(2)- 关于模型安全性的测试案例

✨报告阅读&#xff1a;使用大模型来学习推理(Reason) 首先是原文链接&#xff1a;https://openai.com/index/learning-to-reason-with-llms/ 接下来我们看一个简单的关于模型安全性的测试&#xff0c;当模型被问到一个有风险的话题时&#xff0c;会如何思考并回答用户呢&…

CentOS中使用DockerCompose方式部署带postgis的postgresql(附kartoza/docker-postgis镜像下载)

场景 CentOS中使用Docker部署带postgis的postgresql&#xff1a; CentOS中使用Docker部署带postgis的postgresql_centos postgis插件在容器中如何安装-CSDN博客 上面使用Docker搜索和拉取kartoza/postgis时并没有任何限制。 当下如果不能科学上网时&#xff0c;大部分镜像源…

.Net Core 生成管理员权限的应用程序

创建一个ASP.NET Core Web API项目 给解决方案设置一个名称 选择一个目标框架&#xff0c;这里选择的是 .NET 8.0框架 在Porperties文件夹中添加一个app.manifest文件 设置app.manifest文件属性&#xff0c;生成操作设置为嵌入的资源 双击解决方案名称&#xff0c;编辑WebAppli…

【AI大模型】股票价格预测精度增强,基于变分模态分解、PatchTST和自适应尺度加权层

简介 股票价格指数是金融市场和经济健康的晴雨表&#xff0c;准确预测对投资决策至关重要。股票市场的高频交易和复杂行为使得预测具有挑战性&#xff0c;需开发稳定、准确的预测模型。研究表明&#xff0c;估值比率、数据驱动模型&#xff08;如支持向量机&#xff09;、股票…

Android平台使用VIA创建语音交互应用

Android平台使用VIA创建语音交互应用 概述 在 Android 平台上开发一款语音助手应用需要整合多种技术,包括语音识别(ASR)、文字转语音(TTS)、以及热词检测(Hotword Detection)。这些技术共同构成了语音助手应用的核心交互方式,使用户能够通过语音命令与设备进行无缝交…

RabbitMQ 快速入门

目录 什么是MQ 为什么要使用 MQ MQ 的分类 MQ 的选择 认识 RabbitMQ RabbitMQ 的核心部分 安装 脚本安装 docker 安装 启动 web 管理界面 创建用户 创建消息队列 基本概念 消息应答 持久化 预取值 发布确认 交换机 Exchange 概念 死信队列 死信的来源 延迟…

C++之 string(中)

C之 string string类对象的容量操作 resize 将有效字符的个数该成n个&#xff0c;多出的空间用字符c填充 虽然在string里用的不多&#xff0c;但是在vector里面常见 这里有三种情况&#xff1a; 1&#xff09;resize小于当前的size 2)resize大于当前的size,小于capacity …

重生之我在代码随想录刷算法第十三天 | 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数

参考文献链接&#xff1a;代码随想录 本人代码是Java版本的&#xff0c;如有别的版本需要请上代码随想录网站查看。 110.平衡二叉树 力扣题目链接 解题思路 这道题目刚看到以为和二叉树的最大深度差不多&#xff0c;上来写了一堆迭代求深度的代码结果发现不对劲。 看了题…

通过WinCC在ARMxy边缘计算网关上实现智能运维

随着信息技术与工业生产的深度融合&#xff0c;智能化运维成为提升企业竞争力的关键因素之一。ARMxy系列的ARM嵌入式计算机BL340系列凭借其高性能、高灵活性和广泛的适用性&#xff0c;为实现工业现场的智能运维提供了坚实的硬件基础。 1. 概述 ARMxy BL340系列是专为工业应用…

wpf在图上画矩形,矩形可拖动、大小可调节,使用装饰器Adorner调整矩形大小,限制拖动和调节范围

效果 功能 使用wpf实现 在图片上画一个矩形框该矩形框可以调节大小该矩形框可以拖动调整位置 注&#xff1a;这里的鼠标事件是&#xff0c;双击在图上画一个固定大小的矩形框&#xff0c;右键按住拖动矩形框。有需要的可以自行调整对应的鼠标事件 参考资料&#xff1a;https…

vant van-pull-refresh + van-list实现list列表支持搜索和下拉刷新

1 介绍 在使用 van-pull-refresh van-list实现list列表下拉刷新时遇到几个问题在这里进行一个总结。 2 出现的问题 问题一&#xff1a;当van-pull-refresh van-list组合使用时&#xff0c;下拉刷新会调用两个加载图标。 解答&#xff1a;去除van-pull-refresh加载图标&…