基于Java实现双向链表
作者:fan儿 发布时间:2022-11-17 11:39:16
本文实例为大家分享了Java实现双向链表的具体代码,供大家参考,具体内容如下
双向链表与单链表的对比:
1、单向链表查找只能是一个方向,双向链表可以向前或者向后查找
2、单向链表不能自我删除,需要靠辅助节点**(即需要通过找到要删除的节点的前一个节点,通过该节点进行删除的操作,而双向链表只需找到要删除的节点就行了)**。双向链表可以自我删除
双向链表示意图
分析(代码实现原理):temp为辅助节点(因为头节点不可动)
1、遍历:方式与单链表一致,但是是双向的,可以向前,也可以向后
2、添加(默认添加到最后面)
(1)先找到链表的最后一个节点
(2)temp.next=newnode
(3)newnode.pre=temp
3、修改:思路与原理与单链表一致
4、删除:
(1)因为是双向链表,可以自我删除该节点
(2)找到要删除的节点,假设这个节点为temp
(3)temp.pre.next=temp.next
(4)temp.next.pre=temp.pre
添加节点(按顺序):
步骤:
(1)找到要添加节点位置的前一个节点(temp)
(2)node.next=temp.next
(3)temp.next.pre=node
(4)temp.next=node
(5)node.pre=temp
代码实现:
public class DoubleLinkedList {
//创建头结点。表示链表的头
private Node Head=new Node(0,"","");
//返回头结点
public Node getHead() {
return Head;
}
//AddNode1:添加节点到单链表的尾部
//思路:当不考虑节点顺序
//1、找到链表的最后一个节点
//2、将最后这个节点的Next指向新节点
public void AddNode1(Node node) {
//因为头节点不能动,所以需要一个辅助节点遍历
Node temp=Head;
while(true) {
//找到链表的最后一个节点
if(temp.next==null) {
break;
}
//否则temp=temp的下一个节点
temp=temp.next;
}
//循环出来之后,temp是最后一个节点
temp.next=node;
node.pre=temp;
}
//AddNode2:添加节点,按顺序
public void AddNode2(Node node) {
//因为头结点不能动,所以需要一个辅助节点遍历,找到添加新节点的位置
Node temp=Head;
boolean flag=false; //用于标识链表中是否已经存在新节点的顺序
while(true) {
//如果该节点是最后一个节点,则新节点添加到最后一个位置
if(temp.next==null) {
break;
}else if(temp.next.number>node.number) { //说明找到了添加新节点的位置
break;
}else if(temp.next.number==node.number) { //说明新节点的顺序已经存在在链表中
flag=true;
}
temp=temp.next;
}
if(flag) {
System.out.println("该节点的顺序已经存在,插入失败");
}else {
//则说明新节点在链表中不存在,插入新节点
//新节点的下一个节点=辅助节点的下一个节点
node.next=temp.next;
if(temp.next!=null) { //如果temp的下一个节点不为空,则temp的下一个节点的前一个节点为新节点
temp.next.pre=node;
}
//辅助节点的下一个节点=新节点
temp.next=node;
//新节点的前一个节点为辅助节点
node.pre=temp;
}
}
//删除节点
public void remove(Node node) {
if(Head.next==null) {
System.out.println("链表为空!");
return;
}
//创建辅助节点
Node temp=Head.next;
boolean flag=false; //标识是否找到了要删除的节点
while(true) {
if(temp==null) { //遍历完链表了
break;
}else if(temp.number==node.number) { //找到要删除的节点了
flag=true;
break;
}
temp=temp.next;
}
if(flag) { //链表中存在要删除的节点
temp.pre.next=temp.next; //令temp的前一个节点的下一个节点为temp的后一个节点
if(temp.next!=null) { //如果temp不为最后一个节点的话
temp.next.pre=temp.pre; //令temp的下一个节点的前一个节点为temp的前一个节点
}
}else {
System.out.printf("不存在编号为%d的节点",node.number);
}
}
//修改节点,按照节点的Number来修改
public void update(Node newNode) {
if(Head.next==null) {
System.out.println("链表为空!");
return;
}
//创建辅助节点,对链表遍历,知道找到等于修改节点的number的时候
Node temp=Head.next;
boolean flag=false; //用来标识是否找到了修改节点的Number
while(true) {
if(temp==null) { //则已经遍历完链表
break;
}
if(temp.number==newNode.number) {
flag=true;
break;
}
temp=temp.next;
}
if(flag) {
temp.name=newNode.name;
temp.nickName=newNode.nickName;
}else {
System.out.printf("没有找到编号为%d的节点",newNode.number);
}
}
//展示链表
public void show() {
if(Head.next==null) {
System.out.println("链表为空!");
return;
}
//因为头节点不能动,所以通过辅助节点遍历链表
Node temp=Head.next;
while(true) {
//判断是不是最后一个节点
if(temp.next==null) {
System.out.println(temp);
break;
}
System.out.println(temp);
//temp指向下一个节点
temp=temp.next;
}
}
}
//创建节点
class Node{
public int number;
public String name;
public String nickName;
public Node next; //指向下一个节点
public Node pre;//指向前一个节点
//构造器
public Node(int number,String name,String nickName) {
this.number=number;
this.name=name;
this.nickName=nickName;
}
@Override
public String toString() {
return "Node [number=" + number + ", name=" + name + ", nickName=" + nickName + "]";
}
}
测试代码:
public static void main(String[] args) {
// TODO 自动生成的方法存根
Node node1=new Node(1,"宋江","及时雨");
Node node2=new Node(2,"卢俊义","玉麒麟");
Node node3=new Node(3,"吴用","智多星");
Node node4=new Node(4,"林冲","豹子头");
Node node5=new Node(4,"linchong","豹子头");
//创建一个链表
DoubleLinkedList linkedList=new DoubleLinkedList();
linkedList.AddNode2(node1);
linkedList.AddNode2(node3);
linkedList.AddNode2(node4);
linkedList.AddNode2(node2);
linkedList.show();
System.out.println("------------");
linkedList.remove(node4);
linkedList.show();
}
结果:
Node [number=1, name=宋江, nickName=及时雨]
Node [number=2, name=卢俊义, nickName=玉麒麟]
Node [number=3, name=吴用, nickName=智多星]
Node [number=4, name=林冲, nickName=豹子头]
————————————————————————
Node [number=1, name=宋江, nickName=及时雨]
Node [number=2, name=卢俊义, nickName=玉麒麟]
Node [number=3, name=吴用, nickName=智多星]
来源:https://blog.csdn.net/weixin_43589025/article/details/105884616
猜你喜欢
- 一、作用和区别 break的作用是跳出当前循环块(for、while、do while)或程序块(switch)。在循环块中的作用
- 仅供学习交流,禁止商业用途。如侵害利益,联系必删!前言最近一位小伙伴钟爱二次元文化,于是找到半次元这个app,但是很快他就遇到了问题。一、案
- 一、创建web项目1、打开idea软件,点击界面上的Create New Project2、进入如下界面。选中 java Enterpris
- 了解YMP框架YMP于2014年10月25日正式发布1.0版本,在此之前就已在实际项目中得到广泛使用,从最初仅限团队内部使用,到合作伙伴的开
- 1. 继承1. 子类继承了父类,获得父类的全部Field和方法。子类Student类继承父类,将可以获得父类的全部Field和方法publi
- 引语:工作中有时候需要在普通的对象中去调用spring管理的对象,但是在普通的java对象直接使用@Autowired或者@Resource
- 什么是命名查询? Hibernate允许在映射文件中定义字符串形式的查询语句,这种查询方式成为命名查询 使用命名查询有什么好处? 由于使用H
- 程序如下:View Code /* * Hanoi塔游戏 问题描述: * 汉诺塔:汉诺塔(又称河内塔)问
- 近期,Apache SkyWalking 修复了一个隐藏了近4年的Bug - TTL timer 可能失效问题,这个 bug 在 SkyWa
- 后台生成验证码工具方法 /* * 设置图片的背景色 */ public static v
- ObjectMapper 忽略字段大小写核心代码:ObjectMapper mapper = new ObjectMapper();mapp
- 之前我们在使用vue进行 h5 表单录入的过程中,遇到了Android软键盘弹出,覆盖 h5页面 输入框 问题,在此进行回顾并分享给大家:系
- 整理文档,搜刮出一个spring boot实现过滤器和 * demo ,稍微整理精简一下做下分享。 * 定义:@WebServletpubl
- 文件上传是开发中十分常见的功能,在servlet3.0之前,实现文件上传需要使用一些插件技术,比如:commons-fileuploadsm
- 本文实例讲述了Java实现矩阵加减乘除及转制等运算功能。分享给大家供大家参考,具体如下:Java初学,编写矩阵预算程序,当做工具,以便以后写
- 背景数据之间两两趋势比较在数据分析应用中是非常常见的应用场景,如下所示:模拟考批次班级学生语文数学英语202302三年一班张小明130145
- 这几年都在搞前后端分离、RESTful风格,我们项目中也在这样用。前几天有人遇到了解析JSON格式的请求数据的问题,然后说了一下解析的方式,
- Android Studio 在引用外部依赖时,发现一直无法引用外部依赖。刚开始以为是墙的问题,尝试修改Gradle配置,未解决问题。最终发
- 老生常谈的配置 但是还是需要说明一下EurekaApplication @EnableEurekaServer指定为server端
- 一、链表1.1 概述链表是真正动态的数据结构,最简单的动态数据结构,基本用于辅助组成其他数据结构。数据存储在“节点”(Node)中优点:真正