java双向链表解析实现双向链表的创建含代码

双向链表

  • 一.双向链表
  • 二.创建MyListCode类实现双向链表创建
    • 一.AddFirst创建(头插法)
    • 二.AddLast创建(尾叉法)
    • 三.size
    • 四.remove(指定任意节点的首位删除)
    • 五.removeAll(包含任意属性值的所有删除)
    • 六.AddIndex(给任意位置添加一个节点)
    • 七.contains(无)
    • 八.partition(区分链表的大小范围)
    • 九.display(打印)
  • 接口类
  • MyListNode整体代码
  • Test测试类代码

一.双向链表

单向链表从头部开始我们的每一个节点指向后驱的节点。
此处为单向链表

单向链表

双向链表是相互指向前驱以及后驱的链表
前驱链表我们需要在我们的MyListCode内部类中在定义一个previous来接收每一个前驱的地址

在这里插入图片描述想要删除任意节点可以直接通过访问下一个节点使其prev获取想要删除的上一个节点,然后将想要删除的上一个节点.next获取到被删除对象下一个节点的指向
在这里插入图片描述
这里我们可以模拟实现MyListCode类中的一些方法,入头插法、尾叉法、任意位置插入节点、指定元素删除含有该元素的第一个节点、指定元素删除含有该元素的所有节点等…

二.创建MyListCode类实现双向链表创建

public class MyListNode implements IList {static class Node{public int val;//获取的后一个节点public Node next;//获取的前一个节点public Node prev;public Node(int val) {this.val = val;}}//始终在第一个节点public Node head;//指向最后一个节点public Node last;}

一.AddFirst创建(头插法)

这里当头部为null,没有头部和尾巴,我们将新节点作为头和尾,如果不为null,将每次产生的新节点对象放到头部,头部的pre与新节点相连,头部更新最新节点

  @Overridepublic void addFirst(int data) {Node node=new Node(data);if(this.head==null){//head指向头部,last指向尾巴this.head=node;this.last=node;}else{//不为空将新节点插入头部并将头部的pre置为新节点,最后更新头部位置node.next=this.head;this.head.prev=node;this.head=node;}}

二.AddLast创建(尾叉法)

这里考虑的是当head为空时,我们的头和尾巴都将获取新的节点,如果不为空,我们只需要移动last,将last的下一个节点获取到新的节点,新的节点pre指向last,最后last走向新节点,得到尾巴

 @Overridepublic void addLast(int data) {Node node=new Node(data);if(this.head==null){this.head=node;this.last=node;}else {this.last.next = node;node.prev = last;last=node;}}

三.size

从头部开始遍历或者尾部开始遍历

 @Overridepublic int size() {if(this.head==null){return 0;}Node cur=this.head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}@Overridepublic void display() {Node cur=this.head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}

四.remove(指定任意节点的首位删除)

首先判断如果头部值为空,说明没有节点,头部的下一个节点如果为key值则直接返回key(因为这里只是删除一个,所以不考虑多个带key的节点),然后遍历如果最后一个节点为key,它的下一个节点为null,则将双向节点置为null,如果不为null,就删除这个节点

  @Overridepublic void remove(int key) {if (this.head == null) {return;}if(this.head.val==key){//头节点为key将其更换为后驱节点,将后驱节点的prev置空this.head=this.head.next;this.head.prev=null;return;}Node cur=this.head.next;while(cur!=null){if(cur.val==key){//最后一个节点为key将前驱的下一项置空并将cur的pre置空if(cur.next==null){cur.prev.next=null;cur.prev=null;return;}else{//不是最后一个节点将前驱节的下一节点为当前节点下一项//当前节点的下一项的前驱为当前项的前驱cur.prev.next=cur.next;cur.next.prev=cur.prev;return;}}cur=cur.next;}}

五.removeAll(包含任意属性值的所有删除)

首先判断是否头部为空
判断最后一个last值是否时key,是key将双节点置空
然后判断key值,将key值在节点中删除
最后判断头节点是否为key,并将头节点置空

@Overridepublic void removeAll(int key) {if(this.head==null){return;}if(this.last.val==key) {//如果最后一项的值为key,将last前一项保留下来,最后赋值给last使其尾部更新Node pre=this.last.prev;this.last.prev.next = null;this.last.prev = null;this.last=pre;}Node cur=this.head.next;while(cur!=null){//cur的值如果为key清理该节点指向if(cur.val==key){cur.prev.next=cur.next;cur.next.prev=cur.prev;}cur=cur.next;}//最后判断head的值是否是keyif(this.head.val==key){this.head=this.head.next;}//如果head有数据将head头的前节点置空if(this.head!=null){this.head.prev=null;}}

六.AddIndex(给任意位置添加一个节点)

首先判断头部是否为空
判断该坐标是否合法,如果该坐标在0或者在尾巴,则头插法和尾叉法
将给的坐标作为循环条件节点开始走,跳出循环后改节点位置就是要添加的位置
首先要把改节点的坐标向后移动一位,插入其中间
单链表的话将cur先指向后一个节点在指向前一个节点

 @Overridepublic void addIndex(int index,int data)throws RuntimeException {if(this.head==null){return;}try {if(index<0||index>size()){throw new RuntimeException("错误范围"+size());}}catch (RuntimeException e){e.printStackTrace();}if(index==0){addFirst(data);return;}if(index==size()){addLast(data);return;}Node node=new Node(data);Node cur=this.head;while(index>0){//出来后就是要插入的范围cur=cur.next;index--;}//在任意位置新增一个节点node.next=cur;node.prev=cur.prev;cur.prev=node;node.prev.next=node;return ;}

七.contains(无)

 @Overridepublic boolean contains(int key) {if(this.head==null){return false;}Node cur=this.head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}

八.partition(区分链表的大小范围)

    @Overridepublic Node partition(Node node,int x) {if (node == null) {return null;}Node cur = node;Node min=null;Node minEnd=null;Node max=null;Node maxEnd=null;while (cur != null) {if(cur.val<x){if(min==null){min=cur;minEnd=cur;}else{minEnd.next=cur;minEnd=minEnd.next;}}else{if(max==null){max=cur;maxEnd=cur;}else{maxEnd.next=cur;maxEnd=maxEnd.next;}}cur = cur.next;}if(min==null){return max;}if(maxEnd!=null){maxEnd.next=null;}minEnd.next=max;return min;}
}

九.display(打印)

@Overridepublic void display() {Node cur=this.head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}

接口类

public interface IList {public void display();public int size();public void addFirst(int data);//新增一个节点放到头部public void addLast(int data);//新增一个节点放到尾部public void remove(int key);//删除第一个val值为key的节点public void removeAll(int key);//删除所有val值的节点public void addIndex(int index,int data);//在任意一个位置放入一个节点public boolean contains(int key);//是否包含key数值这个节点public MyListNode.Node partition(MyListNode.Node node,int x);//指定一个值,将数值小的放在前,将数值大的放在后
}

MyListNode整体代码

import java.util.List;public class MyListNode implements IList {static class Node{public int val;public Node next;public Node prev;public Node(int val) {this.val = val;}}//始终在第一个节点public Node head;//指向最后一个节点public Node last;@Overridepublic void addFirst(int data) {Node node=new Node(data);if(this.head==null){this.head=node;this.last=node;}else{node.next=this.head;this.head.prev=node;this.head=node;}}@Overridepublic void addLast(int data) {Node node=new Node(data);if(this.head==null){this.head=node;this.last=node;}else {this.last.next = node;node.prev = last;last=node;}}@Overridepublic int size() {if(this.head==null){return 0;}Node cur=this.head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}public int size2(){if(this.head==null){return 0;}Node end=this.last;int count=0;while(end!=null){count++;end=end.prev;}return count;}@Overridepublic void display() {Node cur=this.head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}public void display2(){Node cur=this.last;while(cur!=null){System.out.print(cur.val+" ");cur=cur.prev;}System.out.println();}@Overridepublic void remove(int key) {if (this.head == null) {return;}if(this.head.val==key){//头节点为key将其更换为后驱节点,将后驱节点的prev置空this.head=this.head.next;this.head.prev=null;return;}Node cur=this.head.next;while(cur!=null){if(cur.val==key){//最后一个节点为key将前驱的下一项置空并将cur的pre置空if(cur.next==null){cur.prev.next=null;cur.prev=null;return;}else{//不是最后一个节点将前驱节的下一节点为当前节点下一项//当前节点的下一项的前驱为当前项的前驱cur.prev.next=cur.next;cur.next.prev=cur.prev;return;}}cur=cur.next;}}@Overridepublic void removeAll(int key) {if(this.head==null){return;}if(this.last.val==key) {//如果最后一项的值为key,将last前一项保留下来,最后赋值给last使其尾部更新Node pre=this.last.prev;this.last.prev.next = null;this.last.prev = null;this.last=pre;}Node cur=this.head.next;while(cur!=null){//cur的值如果为key清理该节点指向if(cur.val==key){cur.prev.next=cur.next;cur.next.prev=cur.prev;}cur=cur.next;}//最后判断head的值是否是keyif(this.head.val==key){this.head=this.head.next;}//如果head有数据将head头的前节点置空if(this.head!=null){this.head.prev=null;}}@Overridepublic void addIndex(int index,int data)throws RuntimeException {if(this.head==null){return;}if(index==0){addFirst(data);return;}if(index==size()){addLast(data);return;}try {if(index<0||index>size()){throw new RuntimeException("错误范围"+size());}}catch (RuntimeException e){e.printStackTrace();}Node node=new Node(data);Node cur=this.head;while(index>0){//出来后就是要插入的范围cur=cur.next;index--;}//在任意位置新增一个节点node.next=cur;node.prev=cur.prev;cur.prev=node;node.prev.next=node;return ;}@Overridepublic boolean contains(int key) {if(this.head==null){return false;}Node cur=this.head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}@Overridepublic Node partition(Node node,int x) {if (node == null) {return null;}Node cur = node;Node min=null;Node minEnd=null;Node max=null;Node maxEnd=null;while (cur != null) {if(cur.val<x){if(min==null){min=cur;minEnd=cur;}else{minEnd.next=cur;minEnd=minEnd.next;}}else{if(max==null){max=cur;maxEnd=cur;}else{maxEnd.next=cur;maxEnd=maxEnd.next;}}cur = cur.next;}if(min==null){return max;}if(maxEnd!=null){maxEnd.next=null;}minEnd.next=max;return min;}
}

Test测试类代码

public class Test {public static void main(String[] args) {MyListNode myListNode=new MyListNode();myListNode.addLast(3);myListNode.addLast(5);myListNode.addLast(7);myListNode.removeAll(6);
//        System.out.println(myListNode.last.val);
//        myListNode.display();myListNode.addIndex(1,9);System.out.println(myListNode.contains(3));myListNode.display();int len1 =  myListNode.size();int len2 =  myListNode.size();System.out.println(len1+"size");System.out.println(len2+"size1");MyListNode myListNode1=new MyListNode();myListNode1.addLast(3);myListNode1.addLast(3);myListNode1.addLast(8);myListNode1.addLast(9);myListNode1.addLast(19);myListNode1.addLast(3);myListNode1.display();myListNode1.display2();myListNode1.partition(myListNode1.head,5);myListNode1.display();myListNode1.display2();}
}

写的也有很多不好的地方,希望大佬们多多指点,谢谢!!祝大家开心快乐

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

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

相关文章

flink 同步oracle11g数据表到pg库

1. 关闭防火墙和selinux systemctl stop firewalld systemctl disable firewalld systemctl status firewalldvi /etc/selinux/config 修改为disabled2.安装java8 yum list java-1.8* yum install java-1.8.0-openjdk* -yjava -version3.下载和部署postgresql 看需求安装pg库…

用接地气的例子趣谈 WWDC 24 全新的 Swift Testing 入门(三)

概述 从 WWDC 24 开始&#xff0c;苹果推出了全新的测试机制&#xff1a;Swift Testing。利用它我们可以大幅度简化之前“老态龙钟”的 XCTest 编码范式&#xff0c;并且使得单元测试更加灵动自由&#xff0c;更符合 Swift 语言的优雅品味。 在这里我们会和大家一起初涉并领略…

Vue 2 —Vue Router 页面导航和参数传递

当从A页面跳转到B页面的时候把数据也一起传递过去&#xff0c;可用Vue Router 功能&#xff1a; 一、. this.$router.push 方法 Vue Router 是 Vue.js 的官方路由管理器&#xff0c;允许你在应用中进行页面导航&#xff08;即跳转到不同的 URL 路径&#xff09;。 this.$rout…

【AI声音克隆整合包及教程】第二代GPT-SoVITS V2:技术、应用与伦理思考

一、引言 在当今科技迅速发展的时代&#xff0c;声音克隆技术成为人工智能领域的一个备受瞩目的分支。GPT-SoVITS V2作为一种声音克隆工具&#xff0c;正逐渐进入人们的视野&#xff0c;它在多个领域展现出巨大的潜力&#xff0c;同时也引发了一系列值得深入探讨的问题。本文旨…

ssm092基于Tomcat技术的车库智能管理平台+jsp(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;车库智能管理平台设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本车库智能管理平台…

11 Oracle Golden Gate 高可用解决方案:Golden Gate 助力企业保障业务连续性

文章目录 Oracle Golden Gate 高可用解决方案&#xff1a;Golden Gate 助力企业保障业务连续性一、Oracle Golden Gate基本概念二、设计异地灾备策略2.1 需求分析2.2 网络规划2.3 部署架构 三、实施异地灾备策略3.1 环境准备3.2 配置Golden Gate3.3 验证与测试 四、数据保护策略…

【NLP】使用 PyTorch 从头构建自己的大型语言模型 (LLM)

读完这篇文章后&#xff0c;你会取得什么成就&#xff1f;你将能够自己构建和训练大型语言模型 (LLM)&#xff0c;同时与我一起编写代码。虽然我们正在构建一个将任何给定文本从英语翻译成马来语的 LLM&#xff0c;但你可以轻松地修改此 LLM 架构以用于其他语言翻译任务。 LLM…

绘制3D图

一个 3D 函数的表面图&#xff0c;其中包含向量场。 Python 代码示例&#xff0c;使用 matplotlib 和 numpy 库来绘制类似的图。 python 复制代码 import numpy as np import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D# 生成网格 x np.linspace(-…

MATLAB实战 利用1D-DCGAN生成光谱或信号数据

0.前言 在光谱学或信号处理领域&#xff0c;获取大量高质量的数据可能是一项挑战。利用DCGAN迁移对抗生成光谱或信号数据&#xff0c;可以有效地增加数据集的多样性&#xff0c;提高模型的泛化能力。 该实战项目提供了所有源代码与测试数据&#xff0c;旨在帮助学者快速地掌握了…

华为:hcia综合实验

一、拓扑图 二、实验要求 1. pc地址请自行规划&#xff0c;vlan已给出 2. 服务器地址自行规划&#xff0c;vlan&#xff0c;网段已给出 3. 交换机互联链路捆绑保证冗余性 4. 内网pc网关集中于核心交换机&#xff0c;交换机vlan 40互联路由器 ,地址网段已给出 5.配置静态路由实…

jenkins流水线pipeline

创建项目 1. 新建item 并选择pipeline 1.1 和普通项目配置的区别 普通项目配置目录&#xff1a; pipeline项目目录&#xff1a; pipeline的两种语法 声明式语法 2. 配置 2.1 流水线配置 2.2 选择声明式 声明式需要添加一个名为Jenkinsfile的文件实现流水线 Jenkinsfile的…

微信小程序自定义tabbar;禁用某个tab;修改某个tab的样式

微信小程序自定义tabbar&#xff1b;禁用某个tab&#xff1b;修改某个tab的样式 原本使用本身的tabBar就已经很舒服了&#xff0c;很合适了的&#xff0c;但是总有一些脑洞大开的产品和客户&#xff0c;给你搞点多样式&#xff0c;没办法牛马就得去做咯&#xff0c;现在就给大…

深入浅出rust内存对齐

在 Rust 中&#xff0c;内存对齐是一个重要的概念&#xff0c;它涉及到数据在内存中的存储方式&#xff0c;以及如何优化内存访问的效率。往往一门语言的内存布局以及对齐方式决定了一门语言的性能&#xff0c;因此学会并深入理解rust中内存布局会让我们写出高性能的rust代码&a…

闯关leetcode——3206. Alternating Groups I

大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/alternating-groups-i/description/ 内容 There is a circle of red and blue tiles. You are given an array of integers colors. The color of tile i is represented by colors[i]: colors[i…

HTML5和CSS3的进阶_HTML5和CSS3的新增特性

目录 HTML5的新特性 1. HTML5 的新特性 1.1 HTML5 新增的语义化标签 1.2 HTML5 新增的多媒体标签 1. 视频 2. 音频 3. 多媒体标签总结 1.3 HTML5 新增的 input 类型 1.4 HTML5 新增的表单属性 required 必须输入信息&#xff0c;不能为空&#xff1b; 重点&#xf…

小马识途营销顾问谈百科词条建立的注意事项

百度百科是百度旗下的产品&#xff0c;它就好比是一本网络百科全书&#xff0c;当我们在网络上搜索某个人物或是企业的时候&#xff0c;如果他们有创建百度百科的话就可以搜出来百度百科词条。词条上展示的荣誉、贡献、社会评价或是企业组织架构等方面可以在无形之中提升人物或…

6、If、While、For、Switch

6、If、While、For、Switch 一、If 1、if-else if (boolean) {代码块 } else if (boolean) {代码块 } else if (boolean) {代码块 } else { // 默认情况代码块 }关于IDEA单元测试控制台不能输入数据的问题&#xff1a; https://blog.csdn.net/m0_72900498/article/details/…

华为路由器DHCP配置

一、单臂路由结构的DHCP 1.启动设备 2.将pc设为DHCP获取IP地址 3.交换机创建vlan并设置模式 [SW1]vlan batch 10 20 [SW1]int g0/0/1 [SW1-GigabitEthernet0/0/1]port link-type trunk [SW1-GigabitEthernet0/0/1]port trunk allow-pass vlan all [SW1-GigabitEthernet0…

【Vue】Vue3.0(十七)Vue 3.0中Pinia的深度使用指南(基于setup语法糖)

上篇文章&#xff1a; 【Vue】Vue3.0&#xff08;十一&#xff09;Vue 3.0 中 computed 计算属性概念、使用及示例 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;Vue专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月10日15点23分 文章…

element plus el-form自定义验证输入框为纯数字函数

element plus 的el-form 使用自定义验证器&#xff0c;验证纯数字&#xff0c;禁止输入小数、中文、字母、特殊符号。input的maxlength为最大输入多少位长度 效果图 <el-form ref"dataFormRef" :model"dataForm" :rules"dataRules" label-w…