李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构学习--双向链表
Leefs
2020-01-27 PM
1360℃
0条
# 数据结构学习--双向链表 ### 一、管理单向链表的缺点分析 (1)单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找 (2)单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面我们在单链表删除节点时,总是找到temp,temp是待删除节点的前一个节点 ### 二、双向链表如何完成遍历,添加,修改和删除 **示意图** ![05.双向链表01.png][1] > 思路: > > 1. 1.遍历方法和单链表一样,只是可以向前,也可以向后查找 > > 2. 2.添加(默认添加到双向链表的最后) > > + 先找到双向链表的最后这个节点 > > + `temp.next=newHeroNode` > > + `newHeroNode.pre=temp;` > > 3. 3.修改思路和原来的单向链表一样 > > 4. 4.删除 > > + 因为是双向链表,因此,我们可以实现自我删除某个节点 > + 直接找到要删除的这个节点,比如temp > + `temp.pre.next=temp.next` > + `temp.next.pre=temp.pre` **代码实现** ```java public class DoubleLinkedListDemo { public static void main(String[] args) { //测试 //先创建节点 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.add(hero1); doubleLinkedList.add(hero2); doubleLinkedList.add(hero3); doubleLinkedList.add(hero4); doubleLinkedList.list(); //修改 HeroNode2 newHeroNode = new HeroNode2(4,"公孙胜","入云龙"); doubleLinkedList.update(newHeroNode); System.out.println("修改后的链表情况"); doubleLinkedList.list(); //删除 doubleLinkedList.del(3); System.out.println("删除后的链表情况"); doubleLinkedList.list(); } } //创建一个双向链表的类 class DoubleLinkedList{ //先初始化一个头节点,头节点不要动,不存放具体的数据 private HeroNode2 head = new HeroNode2(0,"",""); //返回头节点 public HeroNode2 getHead(){ return head; } //从双向链表中删除一个节点 //1.对于双向链表,我们可以直接找到要删除的这个节点 //2. 找到后,自我删除即可 public void del(int no){ //判断当前链表是否为空 if(head.next == null){//空链表 System.out.println("链表为空,无法删除"); return; } HeroNode2 temp = head.next;//辅助变量 boolean flag = false;//标志是否找到待删除节点 while(true){ if(temp==null){//已经找到链表的最后 break; } if(temp.no == no){ //找到的待删除节点的前一个节点temp flag=true; break; } temp=temp.next;//temp后移,遍历 } //判断flag if(flag){//找到 //可以删除 temp.pre.next=temp.next;// //如果是最后一个节点,就不需要执行下面这句话,否则出现空指针 if(temp.next!=null){ temp.next.pre=temp.pre; } }else{ System.out.printf("要删除的%d节点不存在\n",no); } } //修改节点的信息,根据no编号来修改,即no编号不能改/ public void update(HeroNode2 newHeroNode){ //判断是否为空 if(head.next == null){ System.out.println("链表为空!"); return; } //找到需要修改的节点,根据No编号 //定义一个辅助变量 HeroNode2 temp = head.next; boolean flag = false;//表示是否找到该节点 while(true){ if(temp == null){ break;//已经遍历完链表 } if(temp.no == newHeroNode.no){ //找到 flag = true; break; } temp = temp.next; } //根据flag判断是否找到要修改的节点 if(flag){ temp.name = newHeroNode.name; temp.nickname=newHeroNode.nickname; }else{//没有找到 System.out.printf("没有找到 编号%d的节点,不能修改\n",newHeroNode.no); } } //添加一个节点到双向链表的最后 public void add(HeroNode2 heroNode2){ //因为head节点不能动,因此我们需要一个辅助遍历temp HeroNode2 temp = head; //遍历链表,找到最后 while(true){ //找到链表的最后 if(temp.next == null){ break; } //如果没有找到最后,将temp后移 temp=temp.next; } //当退出while循环时,temp就指向链表的最后 //形成一个双向链表 temp.next=heroNode2; heroNode2.pre=temp; } //遍历双向链表的方法 //显示链表【遍历】 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 = temp.next; } } } //定义HeroNode2,每个HeroNode2对象就是一个节点 class HeroNode2{ public int no; public String name; public String nickname; public HeroNode2 next;//指向下一个节点,默认为null public HeroNode2 pre;//指向前一个节点,默认为null //构造器 public HeroNode2(int no,String name,String nickname){ this.no=no; this.name=name; this.nickname=nickname; } //为了显示方法,我们重新toString @Override public String toString(){ return "HeroNode [no="+no+",name="+name+",nickname="+nickname+"]"; } } ``` [1]: https://lilinchao.com/usr/uploads/2020/01/3482699161.png
标签:
数据结构
,
链表
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://www.lilinchao.com/archives/485.html
上一篇
数据结构学习--单链表面试题
下一篇
数据结构学习--单向环形链表
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
43
标签云
Java阻塞队列
Spring
栈
递归
Docker
Yarn
并发编程
Ubuntu
序列化和反序列化
哈希表
Golang
BurpSuite
Flink
Java工具类
Spark RDD
Linux
Hbase
算法
Jquery
Typora
FileBeat
机器学习
数学
HDFS
ajax
JavaSE
锁
Java
SpringBoot
Golang基础
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞