数据结构与算法-双向链表

1.简介

在使用带头节点的单向链表查找时查找的方向只能是一个方向,而双向链表可以向前或向后查找。例如单向链表只能查到一个节点的下一个节点,但是双向链表不仅可以查到下一个节点,还可以查到上一个节点。

在删除节点时,单向链表不能自我删除,需要借助辅助节点temp,因为单向链表就能找到下一个节点,把这个节点删了就不能直接找到下一个节点了。而双向链表可以自我删除,反正可以找到前一个节点,也可以找到后一个节点,这个节点自己就可以实现删除自我,让自己上一个节点和下一个节点连起来。

比如单向链表长这样:一个next可以找到下一个节点

双向链表可以长这样:一个pre指向前一个节点,一个next指向后一个节点

它可以从前往后查找,也可以从后往前查找

2.思路

①遍历:在遍历时遍历方式和单链表一样,只是它可以向前查找,也可以向后查找

②添加:在添加节点时,默认添加到双向链表最后的情况,先找到双向链表最后的节点,找到以后先使temp.next=newHeroNode,再使newHeroNode.pre=temp。就是原来最后一个节点的下一个节点是新节点,新节点的前一个是原来最后一个节点。

③修改:和单向链表一样

④删除:比如删除编号为5的节点,先找到要删除的这个节点temp,然后使temp.pre.next=temp.next,再使temp.next.pre=temp.pre。这样遍历的时候就跳过要删除的节点了。

要注意:在删除最后一个节点时如果要找temp.next.pre就会找不到。所以如果temp.next==null时就不执行temp.next.pre=temp.pre这行代码。

这两行代码可以记成:等号前面是更长的,有next有pre,等号后面是前面的头和尾,没有中间的next或者pre。

temp.next.pre=temp.pre

temp.pre.next=temp.next

⑤考虑编号顺序添加节点:找到要添加位置的前一个节点temp,找到以后新节点.next=temp.next,判断temp.next是否为空,如果不为空就temp.next.pre=新节点。然后temp.next=新节点,新节点.pre=temp。

3.代码

package com.xjj.linkedlist;public class DoubleLinkedListDemo {public static void main(String[] args) {//测试System.out.println("双向链表");//创建节点HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");//创建双向链表DoubleLinkedList doubleLinkedList = new DoubleLinkedList();doubleLinkedList.list();doubleLinkedList.add(hero1);doubleLinkedList.add(hero2);doubleLinkedList.add(hero3);doubleLinkedList.add(hero4);doubleLinkedList.list();//修改双向链表System.out.println("修改双向链表");HeroNode2 newHeroNode = new HeroNode2(2, "卢", "玉麒麟--");doubleLinkedList.update(newHeroNode);doubleLinkedList.list();//删除System.out.println("删除节点1");doubleLinkedList.delete(1);//删除第一个节点doubleLinkedList.list();System.out.println("删除节点4");doubleLinkedList.delete(4);//删除第四个节点doubleLinkedList.list();//按编号顺序添加System.out.println("按编号顺序添加");DoubleLinkedList doubleLinkedList1 = new DoubleLinkedList();doubleLinkedList1.addByOrder(hero2);doubleLinkedList1.addByOrder(hero4);doubleLinkedList1.addByOrder(hero3);doubleLinkedList1.addByOrder(hero1);doubleLinkedList1.list();}
}class HeroNode2 {public int no;public String name;public String nickname;public HeroNode2 next;//指向下一个节点public HeroNode2 pre;//指向上一个节点//构造器public HeroNode2(int hNo, String hName, String hNickname) {this.no = hNo;this.name = hName;this.nickname = hNickname;}//重写toString来显示方法@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}
}class DoubleLinkedList {private HeroNode2 head = new HeroNode2(0, "", "");//返回头节点public HeroNode2 getHead() {return head;}//添加节点。不考虑编号顺序时,先找到当前链表的最后节点,再将这个节点的next指向新节点public void add(HeroNode2 heroNode) {//辅助遍历tempHeroNode2 temp = head;//遍历链表找到最后while (true) {if (temp.next == null) {//找到最后了就退出break;}//没到最后就后移到下一个节点temp = temp.next;}//退出while循环时temp就指向链表最后//我们要添加新节点,就将这个最后节点的next指向节点,将节点的前一个指向temptemp.next = heroNode;heroNode.pre = temp;}//添加节点,考虑编号顺序。也就是插入到链表非末尾位置public void addByOrder(HeroNode2 heroNode) {//辅助变量位于添加位置的前一个节点HeroNode2 temp = head;boolean flag = false;//标识添加的编号是否存在。如果存在就不能添加了while (true) {if (temp.next == null) {//已经在链表最后,要添加的节点可能已经在链表最后break;}if (temp.next.no > heroNode.no) {//temp下一个节点的编号大于要插入的节点编号,就是找到了,要在这个temp后面插入break;} else if (temp.next.no == heroNode.no) {//编号已存在flag = true;//编号存在}temp = temp.next;//后移}//判断编号是否已存在if (flag) {System.out.printf("准备插入的编号 %d 已经存在,无法添加\n", heroNode.no);} else {//新节点插入链表中temp的后面heroNode.next = temp.next;//新节点下一个指向插入节点if (temp.next != null) {temp.next.pre = heroNode;}temp.next = heroNode;//插入节点后一个的前一个指向新节点heroNode.pre = temp;//新节点前一个指向插入节点前一个}}//根据编号修改节点信息,即编号不能修改public void update(HeroNode2 newHeroNode) {//判断链表是否为空if (head.next == null) {//如果链表为空就不遍历了System.out.println("链表为空");return;}//找到需要修改的节点//辅助变量HeroNode2 temp = head.next;boolean flag = false;//判断是否找到该节点while (true) {if (temp == null) {break;//已经遍历完链表}if (temp.no == newHeroNode.no) {//找到flag = true;break;}temp = temp.next;}//判断是否找到节点if (flag) {temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;} else {System.out.printf("没有找到编号为 %d 的节点\n", newHeroNode.no);}}//删除节点//直接找到要删除的节点public void delete(int no) {//判断链表是否为空if (head.next == null) {//如果链表为空就不遍历了System.out.println("链表为空");return;}//找到需要修改的节点//辅助变量HeroNode2 temp = head.next;//直接指向head.nextboolean flag = false;//判断是否找到该节点while (true) {if (temp == null) {break;//已经遍历完链表}if (temp.no == no) {//找到待删除节点flag = true;break;}temp = temp.next;}//判断是否找到节点if (flag) {temp.pre.next = temp.next;//前一个的下一个直接变成下一个//temp.next.pre=temp.pre;//下一个的前一个变成前一个。但是有风险//如果删除最后一个节点,temp就没有next了。所以是删最后一个节点就不用执行下面的代码if (temp.next != null) {temp.next.pre = temp.pre;}} else {System.out.printf("没有找到编号为 %d 的节点\n", no);}}//显示链表,看有没有成功public void list() {//判断链表是否为空,如果为空就不遍历了if (head.next == null) {System.out.println("链表为空");return;}//不为空就遍历//使用辅助变量来遍历HeroNode2 temp = head.next;//这里指向的是下一个while (true) {//看是否到链表最后if (temp == null) {break;}//不为空就输出节点信息System.out.println(temp);//后移temp = temp.next;}}
}

4.运行结果

5.提炼一下

①直接在链表末尾添加节点就是找到末尾节点temp,然后使temp.next=新节点,再使新节点.pre=temp

②在链表中间按编号顺序添加就是找到添加位置的前一个节点temp,找到以后新节点.next=temp.next,判断temp.next是否为空,如果不为空就temp.next.pre=新节点。然后temp.next=新节点,新节点.pre=temp。

②删除节点就遍历找到该节点temp后temp.next.pre=temp.pre,temp.pre.next=temp.next

③遍历以及修改节点与单链表的一样


加油加油^_^

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

AI-数学-高中-47导数与几何意义

原作者视频:【导数】【考点精华】7导数与几何意义考点解析(基础)_哔哩哔哩_bilibili 该点处切点的斜率 该点处导函数的值 示例1: 导数问题解决最常用方法:参数分离,在左边函数有解的值域范围内。 示例2&…

数组的定义及实现

文章目录 前言一、定义二、抽象数据类型定义三、顺序存储四、具体实现总结 前言 T_T此专栏用于记录数据结构及算法的(痛苦)学习历程,便于日后复习(这种事情不要啊)。所用教材为《数据结构 C语言版 第2版》严蔚敏。 一、…

21世纪世界最具影响力的华人颜廷利:乱与净之中的汉字智慧

人类离不开‘卵’字, 众生离不开‘乱’(与‘卵’同音)字; 生命离不开‘精’字, 升命离不开‘净’(与‘精’同音)字…(升命学说) 21世纪东方哲学家思想家、科学家、当代中…

量化研究---pywencai问财数据的使用,提供源代码

文章链接 量化研究---pywencai问财数据的使用,提供源代码 (qq.com) pywencai是一个强大的第三方库库,开源的源代码,但是教程比较少,我简单的写一个教程结合我的使用,也开源直接访问我网页 网页http://120.78.132.143:8023/wencai…

Unity开发微信小游戏(2)分享

目录 1.概述 2.代码 3.示例 4.个人作品 1.概述 这里我们能做有两件事: 1)主动发起分享 2)监听右上角分享(...按钮,发朋友圈也在这里) API:官方文档 2.代码 1)主动发起分享&…

数据结构与算法-单向环形链表与约瑟夫问题

1.简介 单向环形链表&#xff0c;闭合的形成一个环。 单向环形链表的一个应用场景是约瑟夫问题。 约瑟夫问题为&#xff1a;设编号为1&#xff0c;2&#xff0c;…&#xff0c;n的n个人围坐一圈&#xff0c;约定编号为k(1<k<n)的人从1开始报数&#xff0c;数到m的那个人…

ESP32 烧录固件

第一步&#xff1a;下载固件 git clone --recursive https://github.com/espressif/esp-at.git 第二步&#xff1a;执行编译 在该目录执行 python build.py install 如图&#xff1a; 第三步&#xff1a;选择芯片 输入2 第四步&#xff1a;选择固件 输入1 第五步&#…

eNSP-抓包解析HTTP、FTP、DNS协议

一、环境搭建 1.http服务器搭建 2.FTP服务器搭建 3.DNS服务器搭建 二、抓包 三、http协议 1.HTTP协议&#xff0c;建立在FTP协议之上 2.http请求 3.http响应 请求响应报文参考&#xff1a;https://it-chengzi.blog.csdn.net/article/details/113809803 4.浏览器开发者工具抓包…

分布式事务—> seata

分布式事务之Seata 一、什么是分布式事务&#xff1f; 分布式事务是一种特殊类型的事务&#xff0c;它涉及多个分布式系统中的节点&#xff0c;包括事务的参与者、支持事务的服务器、资源服务器以及事务管理器。 在分布式事务中&#xff0c;一次大型操作通常由多个小操作组成…

【UnityRPG游戏制作】NPC交互逻辑、动玩法

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;就业…

git学习指南

文章目录 一.版本控制1.认识版本控制2.版本控制功能3.集中式版本控制4.分布式版本控制 二.Git的环境安装搭建1.Git的安装2.Git配置分类3.Git配置选项 三.Git初始化本地仓库1. git init/git clone-获取Git仓库2. 本地仓库文件的划分3. git status-检测文件的状态4. git add-文件…

[XYCTF新生赛]-PWN:fmt解析(scanf格式化字符串漏洞,任意地址写)

查看保护 查看ida 这里没什么好说的 完整exp&#xff1a; from pwn import* context(log_leveldebug) #pprocess(./fmt) premote(gz.imxbt.cn,20975) backdoor0x4012BEp.recvuntil(bgift: ) printf_addrint(p.recv(14),16) print(hex(printf_addr)) libcELF(./libc-2.31.so) …

java 学习二

java字面量 java变量 注意事项 十进制转二进制 计算机中表示数据的最小单元 java中的数据类型 java中的类型转换 表达式的自动类型转换 强制类型转换

大气官网(1):家居家电,海量案例来袭。

设计一款大气的家居家电官网&#xff0c;可以考虑以下几个方面&#xff1a; 色彩选择&#xff1a;选择适合家居家电风格的色彩搭配。可以选择温暖的中性色调&#xff0c;如米白色、灰色和棕色&#xff0c;以增加页面的大气感和舒适感。图片展示&#xff1a;使用高质量的图片展…

一加12/11/10/Ace2/Ace3手机上锁回锁BL无限重启黑屏9008模式救砖

一加12/11/10/Ace2/Ace3手机官方都支持解锁BL&#xff0c;搞机的用户也比较多&#xff0c;相对于其他品牌来说&#xff0c;并没有做出限制&#xff0c;这也可能是搞机党最后的救命稻草。而厌倦了root搞机的用户&#xff0c;就习惯性回锁BL&#xff0c;希望彻底变回官方原来的样…

Redis__三大日志

文章目录 &#x1f60a; 作者&#xff1a;Lion J &#x1f496; 主页&#xff1a; https://blog.csdn.net/weixin_69252724 &#x1f389; 主题&#xff1a;Redis__三大日志 ⏱️ 创作时间&#xff1a;2024年04月30日 ———————————————— 对于MySQL来说, 有…

39 死锁

目录 1.死锁 2.线程同步 3.条件变量 4.案例 死锁 概念 死锁是指在一组进程中的各个进程均占有不会释放的资源&#xff0c;但因互相申请被其他进程所占用不会释放的资源而处于的一种永久等待状态 四个必要条件 互斥条件&#xff1a;一个资源每次只能被一个执行流使用 请求…

LeetCode题练习与总结:柱状图中最大的矩形--84

一、题目描述 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 示例 1: 输入&#xff1a;heights [2,1,5,6,2,3] 输出&#xff1a;10 解释&#xff1a…

硬盘选购指南

转载请注明出处&#xff01; author karrysmile date 2024年5月3日19:10:52 结论 先给用途分类和价格表 前置知识 没有不好的品牌&#xff0c;只有不好的系列。不用认准哪个品牌就不好&#xff0c;认准口碑好&#xff0c;稳定性好的系列买。&#xff08;杂牌别买&#xff0…

82、动态规划-杨辉三角

思路&#xff1a; 本题其实很容易看出来&#xff0c;首尾都是1&#xff0c;然后第2个元素就是上一行的第一个元素和第二个元素之和。依次类推。可以得出结论&#xff1a;dp[i][j]dp[i-1][j-1]dp[i-1][j],当然要去掉首尾元素。代码如下&#xff1a; public static List<List&…