【数据结构与算法】什么是双向链表?并用代码手动实现一个双向链表

文章目录

  • 一、什么是双向链表
  • 二、双向链表的简单实现

在这里插入图片描述

一、什么是双向链表

我们来看一下这个例子:

在一个教室里,所有的课桌排成一列,如图
在这里插入图片描述

相信在你们的读书生涯中,老师肯定有要求你们记住自己的前后桌是谁。所以该例子中,老师就要求学生们记住自己的前后桌,其中坐在第一排的学生需要记住自己是第一排的学生以及自己的后桌是谁;最后一排的学生要记住自己的前桌是谁以及自己是最后一排的学生。如图:
在这里插入图片描述

这一列座位就相当于一个 双向链表

假如有一天,老师还没记住每个学生的名字,于是就问:这一列第三个人叫什么名字?这时就要从第一个学生开始数,例如从图中坐在第一个的 小5 开始数:第一个人是 小5,他的后桌是 小7;因此第二个人就是 小7,他的后桌是 小1;因此第三个人就是 小1 了。此时老师问 小1:你的前桌叫什么名字?你的后桌叫什么名字?

因为刚开始老师就让每个学生记住了自己的前桌以及后桌,所以此时 小1 能很快地告诉老师他的前桌是 小7,他的后桌是 小6。

但是,我们设想一下,如果是上一篇文章的 链表结构 的例子中,如果老师在得知了第三个人是 小1 以后,询问 小1 的前桌叫什么名字,小1 能回答上来吗?并不能,因为老师只让每个学生记住了自己的后桌,所以此时想要得知 小1 的前桌叫什么名字,只能这样:第三个学生叫 小1,那么他的前桌就坐在第二个位置,所以从第一个学生开始数,第一个学生是 小5,他的后桌是 小7;因此第二个学生就是 小7。当然本文举得例子中学生数量有点少,但一旦数量多起来了,每次问一个学生他的前桌叫什么名字的时候,都要从头开始数。

从中可以看出,让每个学生记住自己的前桌后桌是非常有必要的,因为在某些情况下,可以快速地解决问题。

上面讲了那么多,接下来我们就来看一下 双向链表 是什么样的,如图

在这里插入图片描述

可以看到,对比 链表结构,双向链表 多了一个指针 tail,它是指向最后一个元素的,就相当于例子中的学生记住了自己是最后一排。

双向链表与单链表基本相似,但是最大的区别在于双向链表在节点中除了指向下一节点的next指针外,还有指向前一节点的prev指针,这使得双向链表在可以在任意节点从头尾两个方向进行遍历,是“双向”的。

和单链表相比,双向链表在删除和查询等方面明显在操作上更具有灵活性,但是会消耗更多的内存,需要根据使用条件进行取舍。

java中的LinkedHashMap的本质即是一个双向链表。
在这里插入图片描述

二、双向链表的简单实现

修改原来的Node类,在里面添加一个新成员变量Node prev

/**
 * @Author:huang
 * @Date:2023-03-23 20:10
 * @Description:节点类
 */
public class Node {

    //节点序号
    int num;

    //数据
    Object data;

    //下一个节点
    Node next;

    //上一节点
    Node prev;

    public Node(int num, Object data) {
        this.num = num;
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
            "num=" + num +
            ", data=" + data +
            '}';
    }
}
  1. 添加
    添加与单向链表代码逻辑一样,但是新节点在添加时需要修改prev指针指向原来的尾节点。
    举个例子,对于无排序插入,原本有节点A,现在要插入一个B:
  • 找到A,然后让A.next指向B
  • 让B.prev指向A

而对于排序插入,就是原有节点A,C,要在中间插入B:

  • 找到A,让B.prev指向A
  • 让B.next指向A.next,也就是让B的next指向C
  • 让A.next.prev指向B,也就是让C的prev指向B
  • 让A.next指向B
/**
 * 添加节点到链表
 * @param node 要插入的节点
 */
public void add(Node node) {
    Node temp = head;
    //遍历链表
    while (true) {
        if (temp.next == null) {
            break;
        }
        //不是尾节点就继续遍历下一个节点
        temp = temp.next;
    }
    //将尾节点指向即将插入的新节点
    temp.next = node;
    node.prev = temp;
}

/**
 * 按顺序添加节点到链表
 * @param node 要插入的节点
 */
public void addByOrder(Node node) {
    Node temp = head;
    //遍历链表
    while (true) {
        //如果链表到底了就直接插入
        if (temp.next == null) {
            temp.next = node;
            node.prev = temp;
            return;
        }
        else if (temp.next.num > node.num){
            //如果后一节点比当新节点大,就插入当前节点
            node.prev = temp;
            node.next = temp.next;

            temp.next.prev = node;
            temp.next = node;
            return;
        }else if (temp.next.num == node.num){
            //如果后一节点等于新节点,抛异常
            throw new RuntimeException("插入节点与已有节点序号重复!");
        }
        //如果后一节点比当前节点小,就继续遍历
        temp = temp.next;
    }
}
  1. 删除
    由于相对单链表,双向链表的节点可以自己找到上一节点,所以删除的时候可以直接找到要删除的节点进行操作。

举个例子,假设有节点A,B,C,现在要删除B:

  • 找到B,让B.prev.next=B.next,也就是让A的next指向C
  • 让B.next.prev=B.prev,也就是让C的prev指向A

如果要删除的节点已经是尾节点了,那就跟单链表一样了。

/**
 * 删除节点
 * @param num 要删除的节点编号
 */
public void delete(int num) {
    Node temp = head;
    //判断链表是否为空
    if (temp.next == null) {
        throw new RuntimeException("链表为空!");
    }
    //遍历链表
    while (true) {
        //如果链表到底了
        if (temp.next == null) {
            throw new RuntimeException("编号为" + num + "的节点不存在!");
        }
        //如果找到了待删除节点的前一个节点
        if (temp.num == num) {
            //判断待删除节点是否为尾节点
            if (temp.next == null){
                temp.prev.next = null;
            }else {
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
            }
            return;
        }
        //继续遍历下一节点
        temp = temp.next;
    }
}
  1. 修改,查询(与单链表一致)
    由于修改和查询与单链表基本一致,这里就不在赘述了,直接放代码:
/**
 * 展示链表
 */
public void show() {
    //判断链表是否为空
    if (head.next == null) {
        throw new RuntimeException("链表为空!");
    }
    Node temp = head.next;
    //遍历链表
    while (true) {
        if (temp == null) {
            break;
        }
        System.out.println(temp.toString());
        temp = temp.next;
    }
}

/**
 * 根据序号获取节点
 * @param num 要获取的节点序号
 * @return
 */
public Node get(int num){
    //判断链表是否为空
    if (head.next == null) {
        throw new RuntimeException("链表为空!");
    }
    Node temp = head.next;
    //遍历链表
    while (true) {
        if (temp == null) {
            throw new RuntimeException("编号为" + num + "的节点不存在!");
        }
        if (temp.num == num) {
            return temp;
        }
        temp = temp.next;
    }
}

/**
 * 修改节点
 * @param node 要更新的节点
 */
public void update(Node node) {
    Node temp = head;
    //判断链表是否为空
    if (temp.next == null) {
        throw new RuntimeException("链表为空!");
    }
    //获取要更新的节点序号
    int nodeNum = node.num;
    //遍历链表
    while (true) {
        //如果已经遍历完链表
        if (temp == null) {
            throw new RuntimeException("编号为" + temp.num + "的节点不存在!");
        }
        //如果找到了该节点
        if (temp.num == nodeNum) {
            temp.data = node.data;
            return;
        }
        //继续遍历下一节点
        temp = temp.next;
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

J 砍竹子

砍竹子 【问题描述】 这天,小明在砍竹子,他面前有 n 棵竹子排成一排,一开始第 i 棵竹子的高度为 hi . 他觉得一棵一棵砍太慢了,决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用,假设这一段竹子的高度…

菜鸟刷题Day5

⭐作者:别动我的饭 ⭐专栏:菜鸟刷题 ⭐标语:悟已往之不谏,知来者之可追 一.一维数组的动态和:1480. 一维数组的动态和 - 力扣(LeetCode) 描述 给你一个数组 nums 。数组「动态和」的计算公式…

为了之后找工作不被虐,每天刷3道《剑指offer》Day-1

本文已收录于专栏🌻《刷题笔记》文章目录前言💖 1、二维数组中的查找题目描述思路💖 2、替换空格题目描述思路💖 3、从尾到头打印链表题目描述思路一(反转函数)思路二(递归)思路二&a…

Celery使用:优秀的python异步任务框架

目录Celery 简介介绍安装基本使用Flask使用Celery异步任务定时任务Celery使用Flask上下文进阶使用参考停止Worker后台运行Celery 简介 介绍 Celery 是一个简单、灵活且可靠的,处理大量消息的分布式系统,并且提供维护这样一个系统的必需工具。 它是一个…

文心一言 vs GPT-4 —— 全面横向比较

文心一言 vs GPT-4 —— 全面横向比较 3月15日凌晨,OpenAI发布“迄今为止功能最强大的模型”——GPT-4。我第一时间为大家奉上了体验报告《OpenAI 发布GPT-4——全网抢先体验》。 时隔一日,3月16日下午百度发布大语言模型——文心一言。发布会上&#…

4万字企业数字化转型大数据湖项目建设和运营综合解决方案WORD

本资料来源公开网络,仅供个人学习,请勿商用,如有侵权请联系删除。部分资料内容: 3.1.4沙盒管理 利用Docker, 基于kubernetes主打的容器技术与微服务应用基础平台,HDFS和YARN均可依此建模,为上层应用提供微服…

不愧是2023年就业最难的一年,还好有车企顶着~

就业龙卷风已经来临,以前都说找不到好的工作就去送外卖,但如今外卖骑手行业都已经接近饱和状态了,而且骑手们的学历也不低,本科学历都快达到了30%了,今年可以说是最难找到工作的一年。 像Android 开发行业原本就属于在…

学习 Python 之 Pygame 开发魂斗罗(十)

学习 Python 之 Pygame 开发魂斗罗(十)继续编写魂斗罗1. 解决敌人不开火的问题2. 创建爆炸效果类3. 为敌人跳入河中增加爆炸效果4. 玩家击中敌人继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗(九)中,…

深度长文 | 数据安全共享技术发展综述及在能源电力领域应用研究

开放隐私计算 编者按数据要素的流通共享与协同应用是数字时代中数据要素市场培育的核心内容,数据安全共享技术能够有效实现数据的安全共享,避免“数据孤岛”现象、隐私泄露事件等.本文对国内外数据安全共享技术研究成果及进展进行了全面综述.首先&#x…

[前端笔记037]vue2之vuex

前言 本笔记参考视频,尚硅谷:BV1Zy4y1K7SH p105 - p116 vuex简介和基本使用 概念:专门在 Vue 中实现集中式状态(数据)管理的一个 Vue 插件,对 vue 应用中多个组件的共享状态进行集中式的管理(读/写&…

CVPR 2023 | 旷视研究院入选论文亮点解读

近日,CVPR 2023 论文接收结果出炉。近年来,CVPR 的投稿数量持续增加,今年收到有效投稿 9155 篇,和 CVPR 2022 相比增加 12%,创历史新高。最终,大会收录论文 2360 篇,接收率为 25.78 %。本次&…

烤鱼界头牌半天妖发文致歉,背后暴露了哪些问题?

3月24日,半天妖烤鱼官方针对“两家门店食品安全问题”,发表致歉声明,并宣布将两家涉事门店永久关停。半天妖烤鱼爆出的食品安全问题再次提醒我们,加强门店监管和管理工作,保障消费者的健康和安全,成为了行业…

7.避免不必要的渲染

目录 1 组件更新机制 2 虚拟DOM配合Diff算法 3 减轻state 4 shouldComponentUpdate() 4.1 基本使用 4.2 使用参数 5 纯组件 5.1 基本使用 5.2 纯组件的比较方法 shallow compere 1 组件更新机制 当父组件重新渲染时,父组件的所有子组件也会重新…

如何理解AQS

AQS核心数据结构 AQS内部主要维护了一个FIFO(先进先出)的双向链表。 AQS数据结构原理 AQS内部维护的双向链表中的各个节点分别指向直接的前驱节点和直接的后续节点。所以,在AQS内部维护的双向链表可以从其中的任意一个节点遍历前驱结点和后…

【尝鲜版】ChatGPT插件开发指南

3月23日,OpenAI官方发布了一则公告,宣告ChatGPT已经支持了插件功能,现在处于内测阶段。插件的意义不仅仅在于功能的扩展,它直接让ChatGTP拥有了联网的能力!简直是猛兽出笼、蛟龙出海,要让ChatGPT大杀特杀啊…

phpstorm断点调试

环境:win10phpstorm2022phpstudy8lnmp 1、phpinfo(); 查看是否安装xdebug,没有走以下流程 2、phpstudy中切换不同版本php版本,有些版本不支持xdebug(如php8.0.2),有些已经自带了(如php7.3.9&a…

Java奠基】Java经典案例讲解

目录 卖飞机票 找质数 开发验证码 数组元素的复制 评委打分 数字加密 数字解密 抢红包 模拟双色球 二维数组 卖飞机票 需求:机票价格按照淡季旺季、头等舱和经济舱收费、输入机票原价、月份和头等舱或经济舱。按照如下规则计算机票价格: 旺季&…

技术分享——Java8新特性

技术分享——Java8新特性1.背景2. 新特性主要内容3. Lambda表达式4. 四大内置核心函数式接口4.1 Consumer<T>消费型接口4.2 Supplier<T>供给型接口4.3 Function<T,R>函数型接口4.4 Predicate<T> 断定型接口5. Stream流操作5.1 什么是流以及流的类型5.2…

[攻城狮计划]如何优雅的在RA2E1上运行RT_Thread

文章目录[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread准备阶段&#x1f697;开发板&#x1f697;开发环境&#x1f697;下载BSP&#x1f697;编译烧录连接串口总结[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread &#x1f680;&#x1f680;开启攻城狮的成长之旅&#xff0…

【ChatGPT】教你搭建多任务模型

ChatGPT教你搭建多任务模型 You: tell me what’s your version of gpt ? ChatGPT: As an AI language model developed by OpenAI, I am based on the GPT (Generative Pretrained Transformer) architecture. However, my version is known as GPT-3.5, which is an updat…