数据结构 - 双向链表

文章目录

目录

文章目录

前言

一、什么是双向链表?

双向链表有什么优势?

二、双向链表的设计和实现

1.设计思想

尾增 : 在链表的末尾添加新的元素

 头插 : 在链表头部插入节点

 删除 : 根据val的值删除节点

 查找 : 根据索引的值查找并返回节点

总结



前言

大家好,今天给大家讲解一下双向链表的设计和实现,和单向链表不同的是,双向链表中加入了指向前一个节点的指针。


一、什么是双向链表?

如上图所示,双向链表中包含了两个指针,一个指向前驱结点,一个指向后继节点,其中头结点没有前驱节点,尾结点没有后继节点

前驱 : 前驱指的是当前节点的前一个节点,即在链表中位于当前节点之前的节点。它可以通过前向指针(previous pointer)来访问。

后继 : 后继指的是当前节点的后一个节点,即在链表中位于当前节点之后的节点。它可以通过后向指针(next pointer)来访问。

双向链表有什么优势?

相对于单链表,双向链表具有以下优势:

  1. 可以从任意一个节点开始进行正向或反向遍历。由于每个节点都有指向前一个节点和后一个节点的指针,因此可以方便地在链表中进行前向和后向的遍历操作。

  2. 在插入和删除节点时,不需要遍历整个链表来找到前一个节点。在单链表中,如果要在某个节点之后插入或删除节点,需要先找到该节点的前一个节点,而双向链表可以直接通过指针找到前一个节点,从而提高了插入和删除操作的效率。

  3. 双向链表可以更方便地实现反向查找。在单链表中,如果要查找某个节点的前一个节点,需要从头节点开始遍历整个链表,而双向链表可以通过后向指针直接找到前一个节点,从而实现了反向查找。

总之,双向链表相对于单链表在遍历、插入和删除操作上具有更高的效率和灵活性。然而,双向链表的缺点是需要更多的内存空间来存储额外的指针。

二、双向链表的设计和实现

1.设计思想

前言 : 为了简单起见,我们在类中只定义最基本的属性

节点类: 不管是双向链表还是单向链表,都是有节点所构成,所以说节点类是必不可少的(值得一提的是,节点类不一定要定义成外部类,这么一想,好像定义成内部类更加合适,毕竟节点是链表的一部分,大家如果自己实现的话可以使用内部类的方式,由于我写博客准备的就是外部类的方式,在此就不做修改)

链表类: 类中应该需要包含什么信息? 聪明的读者肯定已经想到了吧,节点啊! 你们都是聪明人啊,除了节点之外我们还需要包含一个成员变量Head(链表的头结点),一个构造方法(链表写出来是给别人用的),还有其他的成员方法(自己设计)。

下面给出框架代码

public class List {private Node head;// 头结点public List() {}// 节点类
class Node {int val;Node prev;Node next;public Node() {}public Node(int val) {this.val = val;}@Overridepublic String toString() {return "Node{" +"no=" + val +", prev=" + prev +", next=" + next +'}';}
}

2.代码实现

前言 : 为了简单起见,我们下面只实现基本方法并且只重点针对性的解析我认为对初学者有难度的代码部分

和前面的部分代码相同,有些很简单的方法直接给出

/*
* 链表中元素的个数
* */
public int getSize(){Node cur = head;int count = 0;while(cur != null){cur = cur.next;count++;}return count;
}/*
* 判断链表是否为空
* */
public Boolean IsEmpty() {return head == null;
}

尾增 : 在链表的末尾添加新的元素

public void addNode(int val) {Node node = new Node(val);if (IsEmpty()) {// 链表为空,该节点为新头head = node;}Node cur = head;while (cur.next != null) {cur = cur.next;}// 此时的cur就表示最后一个节点cur.next = node;node.prev = cur;
}

 头插 : 在链表头部插入节点

不知道初学者有没有感觉到什么难度,个人感觉这些代码都是很基础的,所以没有进行解析

如果有问题的可以在评论区提出,我再进行修改

public void addFirst(int val){Node newNode = new Node(val);if(IsEmpty()){head = newNode;}newNode.next = head;head.prev = newNode;head = newNode;
}

 删除 : 根据val的值删除节点

这个和单链表比起来就简单多了,在单链表中需要找到值为val的前一个节点,还需要判断头结点为val的情况,大家搞清楚单链表中的方法,双向链表中的这个就是弟弟!

// 根据节点的no值删除节点
public void DeleteNode(int no) {int count = 0;// 记录被删除节点的个数if(IsEmpty()){System.out.println("链表为空");return;}Node cur = head;// 将head的值赋给变量cur,使其代替head进行循环遍历while(true){if(cur == null){System.out.println("共删除了"+count+"个节点");// 链表中已经没有值为no的节点,跳出循环break;}if(cur.val == no){Node prev = cur.prev;// 记录将要被删除的节点的上一个节点cur = cur.next;// 用下一个节点覆盖当前节点cur.prev = prev;count++;continue;}cur = cur.next;}

 查找 : 根据索引的值查找并返回节点

// 根据索引查找节点
public Node findNode(int index) throws IndexException {// 索引是否合法,一看到和索引相关的问题就应该要想一下是否需要判断索引的合法性,此处需要判断if(index < 0 || index >= getSize()){// 自定义异常来表示索引越界这种不合法的行为throw new IndexException("索引越界");}Node cur = head;while(index > 0){index--;cur = cur.next;}return cur;
}

 写到这里不得不感慨一下JAVA中的深情哥-Exception(异常)-上_喜欢吃animal milk的博客-CSDN博客的下篇到现在还没写

到这里就结束了,方法在精不在多,自行领悟吧!


总结

这篇博客大家应重点关注链表的设计,代码这个东西面试考的更多的是单链表,大家刷题更多的也是单链表,双向链表相对于就没有那么重要了。

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

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

相关文章

MySQL 8.0安装及配置教程

一、下载mysql 进入官网https://www.mysql.com/&#xff0c;下载最新的的mysql8.0版本&#xff0c;该版本新增了许多特性。 进入下载页面&#xff0c;可以选择企业版本和社区版本&#xff0c;一般选择社区免费下载。 二、安装mysql&#xff08;此方法默认安装至C盘&#xff0c…

WangEditor在Vue前端的应用

1、在Vue项目中安装WangEditor 对于Vue2&#xff1a; npm install wangeditor/editor-for-vue --save 或者 yarn add wangeditor/editor-for-vue 对于Vue3&#xff1a; npm install wangeditor/editor-for-vuenext --save 或者 yarn add wangeditor/editor-for-vuenext 2、将Wa…

Java“牵手”易贝商品列表数据,关键词搜索易贝商品数据接口,易贝API申请指南

ebay商城是一个网上购物平台&#xff0c;售卖各类商品&#xff0c;包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取ebay商品列表和商品详情页面数据&#xff0c;您可以通过开放平台的接口或者直接访问ebay商城的网页来获取商品详情信息。以下是两种常用方法的介绍&…

酷开系统游戏空间,开启大屏娱乐新玩法

在这个充满科技感和无限创意的时代&#xff0c;游戏已经成为我们生活的一部分。而随时着科技的不断发展&#xff0c;以及游戏爱好者的游戏需求在不断提高&#xff0c;促使游戏体验也向更加丰富多彩的方向发展。显然&#xff0c;酷开科技早已经认识到游戏发展的新蓝图&#xff0…

Android离线文字识别-tesseract4android调用

Android在线文字识别可以调阿里云的接口Android文字识别-阿里云OCR调用__花花的博客-CSDN博客 需要离线文字识别的话&#xff0c;可以调tesseract4android。个人测试效果不是特别理想&#xff0c;但是速度真的很快&#xff0c;VIVO S10后摄照片&#xff0c;80ms内识别完成。现…

阿里巴巴推出D.Design文生图网站(免费10-20张图)

简介&#xff1a; d.design是阿里巴巴推出的一个基于人工智能的设计工具&#xff0c;可以帮助用户轻松创建3D模型和场景。该工具提供了丰富的素材库和功能&#xff0c;可以满足用户的各种需求。 ​堆友堆友是Alibaba Design打造的设计师全成长周期服务平台&#xff0c;围绕品质…

汽车技术发展趋势及我国节能与新能源汽车技术

一、世界汽车技术发展趋势 汽车技术正向着低碳化、信息化、智能化方向发展&#xff1b;“三化”趋势成为世界主要汽车强国、主要车企共同的战略选择。 主要汽车战略及方向 在“三化”趋势下&#xff0c;各汽车强国在汽车节能技术、新能源汽车技术、智能网联汽车技术等方面持续…

第十八课、Qt 下载、安装与配置

功能描述&#xff1a;介绍了 Qt 的下载、安装和配置的全部过程&#xff0c;并对关键页面选项进行了详细说明 一、Qt 的下载 Qt 官方下载地址&#xff1a;https://www.qt.io/zh-cn/downloadhttps://download.qt.io/https://download.qt.io/https://www.qt.io/zh-cn/download进入…

2023数学建模国赛选题建议及BC题思路

大家好呀&#xff0c;全国大学生数学建模竞赛今天下午开赛啦&#xff0c;在这里先带来初步的选题建议及思路。 目前团队正在写B题和C题完整论文&#xff0c;后续还会持续更新哈&#xff0c;以下只是比较简略的图文版讲解&#xff0c;团队目前正在写B、C题完整论文&#xff0c;…

在线考试组卷Word文档导出|废纸篓|支持搜索组员查看练习情况|官网上线

土著刷题微信小程序v1.16&#xff0c;主要是对系统功能的优化&#xff0c;同时迭代开发了反馈热度比较高的【在线考试组卷word文档导出】和废纸篓功能。 下面将逐条介绍一下这一版的新功能和优化点。 在线考试组卷Word文档导出 【组卷Word导出】这个功能对于线下组织考试是个刚…

LeetCode 904. 水果成篮

题目链接 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目解析 在你去摘水果的时候&#xff0c;你当前只能拥有两种种类的水果&#xff0c;若想拿第三种水果&#xff0c;就需要发下前两种水果中的一种。 法一&#xff1a;滑动窗口哈希表(未优化…

怎么把pdf转换成jpg图片?

怎么把pdf转换成jpg图片&#xff1f;在工作中&#xff0c;如果我们收到无法修改编辑的PDF文件&#xff0c;可能会遇到一些困难。尤其是当平台或网站只支持JPG图片格式&#xff0c;而领导又要求我们将pdf文件改为JPG格式时&#xff0c;情况就更为棘手了。这对于我们打工一族来说…

CSS基础

一、选择器 1.1 元素选择器&#xff1a; 指定元素统一格式 p {text_align: center;}1.2 id选择器&#xff1a; 当我们想精准找到某元素的时候要就id选择器 /* id选择器使用 # 来定义 */ #para1{ text-align:center;}1.3 class选择器&#xff1a; 多个元素统一类型 /* cl…

XCon2023 | 聚铭网络受邀出席并发表“安全运营中心的应用及发展”主题演讲

作为国内信息安全领域“历史最悠久、举办规模最大、知名度最高”的闭门型技术峰会&#xff0c;2023年XCon安全焦点信息安全峰会&#xff08;XFocus Information Security Conference&#xff09;在8月30日于北京盛大召开&#xff0c;本次大会以“链无境皆可能”为主题&#xff…

索尼 toio™应用创意开发征文|toio俄罗斯方块游戏

目录 引言 摘要 创意简述 准备工作&#xff5c;手工开始 代码编写&#xff5c;合理集成 使用体验&#xff5c;近乎奇妙 引言 索尼toio™编程机器人是一款引领技术创新的产品&#xff0c;为开发者提供了一个全新的编程和创造平台。toio™的设计旨在将技术、塑性和乐趣融为…

深度解读智能媒体服务的重组和进化

统一“顶设”的智能媒体服务。 邹娟&#xff5c;演讲者 大家好&#xff0c;首先欢迎各位来到LVS的阿里云专场&#xff0c;我是来自阿里云视频云的邹娟。我本次分享的主题为《从规模化到全智能&#xff1a;智能媒体服务的重组与进化》。 本次分享分为以上四部分&#xff0c;一是…

论数据库的种类

摘要 数据库是现代信息管理和数据存储的重要工具&#xff0c;几乎在各个领域都有广泛应用。不同类型的数据库适用于不同的应用场景和需求。本文将介绍几种常见的数据库种类&#xff0c;并探讨它们的特点和适用范围。 正文 一、关系型数据库&#xff08;RDBMS&#xff09; 关…

2023高教社杯数学建模E题思路代码 - 黄河水沙监测数据分析

# 1 赛题 E 题 黄河水沙监测数据分析 黄河是中华民族的母亲河。研究黄河水沙通量的变化规律对沿黄流域的环境治理、气候变 化和人民生活的影响&#xff0c; 以及对优化黄河流域水资源分配、协调人地关系、调水调沙、防洪减灾 等方面都具有重要的理论指导意义。 附件 1 给出了位…

[.NET学习笔记] - Thread.Sleep与Task.Delay在生产中应用的性能测试

场景 有个Service类&#xff0c;自己在内部实现生产者/消费者模式。即多个指令输入该服务后对象后&#xff0c;Service内部有专门的消费线程执行传入的指令。每个指令的执行间隔为1秒。这里有两部分组成&#xff0c; 工作线程的载体。new Thread与Task.Run。执行等待的方法。…

Map,List,Set 等集合以及底层数据结构

文章目录 概述一、Collection接口&#xff08;1&#xff09;List列表 —— 有序、值可重复&#xff08;2&#xff09;Set 集 —— 值不可重复 二、Map接口&#xff08;1&#xff09;HashMap —— 无序1、取模法2、Hash碰撞冲突3、解决Hash冲突 &#xff08;2&#xff09;HashTa…