Java: LinkedList的模拟实现

 一、双向链表简介

上一篇文章我介绍了单向链表的实现,单向链表的特点是:可以根据上一个节点访问下一个节点!但是,它有个缺点,无法通过下一个节点访问上一个节点!这也是它称为单向链表的原因。

  那么,可不可以实现这样一种链表,它既可以通过一个节点,访问其上一个节点和下一个节点,也是可以的!它就是我接下来要介绍的双向链表

  如图:与单向链表不同的是,双向链表的每个节点包含三个域:val、pre、next,分别代表当前节点的值、上一个节点的地址、下一个节点的地址。



 

二、双向链表的实现

双向链表实现的全部代码:

 类文件:

 异常类代码:(IndexNotLegalException)

//自定义异常类:
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String message) {super(message);}
}

双向链表实现代码:(MyLinkedList)

import javax.management.ListenerNotFoundException;
import java.util.List;public class MyLinkedList {//创建ListNode内部类class ListNode {public int val;public ListNode pre;//前驱public ListNode next;//后继public ListNode(int val) {this.val = val;}}public ListNode head;//标志头节点public ListNode last;//标志尾节点//返回链表长度的方法:public int size() {int count = 0;ListNode cur = head;while (cur != null) {cur = cur.next;count++;}return count;}//打印链表的方法;public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//查看是否波包含key关键字的方法:public boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}//头部插入的方法public void addFirst(int data) {ListNode node = new ListNode(data);//如果head为nullif (head == null) {head = last = node;} else {head.pre = node;node.next = head;head = node;}}//尾部插入的方法:public void addLast(int data) {ListNode node = new ListNode(data);//如果head==nullif (head == null) {head = last = node;} else {last.next = node;node.pre = last;last = node;}}//指定位置插入的方法:public void addIndex(int index, int data) {//1、判断index是否合法try {checkIndex(index);} catch (IndexNotLegalException e) {e.printStackTrace();}//index==0,相当于头部插入if (index == 0) {addFirst(data);return;}//index==size(),相当于尾部插入if (index == size()) {addLast(data);return;}//0<index<size()if (index > 0 && index < size()) {//找到下标为index的节点ListNode cur = findIndex(index);//连接节点ListNode node = new ListNode(data);node.next = cur;node.pre = cur.pre;cur.pre.next = node;cur.pre = node;return;}}//找到index节点的方法:public ListNode findIndex(int index) {int count = index;ListNode cur = head;while (count != 0) {cur = cur.next;count--;}return cur;}//检查index是否合法的方法private void checkIndex(int index) {if (index < 0 || index > size()) {throw new IndexNotLegalException("Index 不合法!" + index);}}//删除第一次出现关键字key的节点public void remove(int key) {//使用cur寻找关键字所在的节点ListNode cur = head;while (cur != null) {if (cur.val == key) {if (cur == head) {//关键字在头节点head = head.next;//判断链表是否只有一个节点!if(head!=null){head.pre = null;}else{last=null;}} else { //关键字在尾节点if (cur == last) {cur.pre.next = cur.next;last = last.pre;} else {  //关键字在中间节点cur.pre.next = cur.next;cur.next.pre = cur.pre;}}return;}cur = cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){//使用cur寻找关键字所在的节点ListNode cur = head;while (cur != null) {if (cur.val == key) {if (cur == head) {//关键字在头节点head = head.next;//判断链表是否只有一个节点!if(head!=null){head.pre = null;}else{last=null;}} else { //关键字在尾节点if (cur == last) {cur.pre.next = cur.next;last = last.pre;} else {  //关键字在中间节点cur.pre.next = cur.next;cur.next.pre = cur.pre;}}//return;注释该语句,使其多次删除关键字为key的节点}cur = cur.next;}}//删除列表public void clear(){ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.pre=null;cur.next=null;cur=curN;}head=last=null;}
}

 



详细讲解: 

 首先创建一个class文件:MyLinkedList类和一个Test类,前者用来实现双向链表,后者用来使用链表!

  在这个MyLinkedList类中,我们需要定义一个内部类:ListNode类,表示节点类!这个节点类应该包含val、pre、next三个成员变量和val的构造方法!

创建好内部类后,就可以定义MyLinkedList类中的成员变量!它应该包括头节点head和尾节点last!



1、一些简单的方法: 

通过前面单向链表的学习,一些简单的方法就不再过多详细介绍,大家看着代码就能懂其中的意思。

  //返回链表长度的方法:public int size(){int count =0;ListNode cur=head;while(cur!=null){cur=cur.next;count++;}return count;}//打印链表的方法;public void display(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}//查看是否包含key关键字的方法:public boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}


2、头部插入的方法: 

头部插入前,首先需要实例化应该ListNode类的节点! 

头部插入的时候,需要分为两种情况:head==null 或 head!=null

i>当head==null时:

此时链表没有节点,此时head和last应该指向同一个节点node

ii>当head!=null时:

第一步:将head.next的null修改为新节点的地址0x78

第二步:将node.next修改为head的地址0x12

第三步:  修改头节点,head=node

修改前:

修改后: 

代码实现:

//头部插入的方法public void addFirst(int data){ListNode node=new ListNode(data);//如果head为nullif(head==null){head=last=node;}else{head.pre=node;node.next=head;head=node;}}



3、尾部插入的方法:

尾部插入的方法与头部插入的方法逻辑上是一样的,也分为两种情况:head==null 或 head!=null

//尾部插入的方法:public void addLast(int data){ListNode node=new ListNode(data);//如果head==nullif(head==null){head=last=node;}else{last.next=node;node.pre=last;last=node;}}


4、指定位置插入的方法:

指定位置插入方法全部代码:

   //指定位置插入的方法:public void addIndex(int index, int data) {//1、判断index是否合法try {checkIndex(index);//调用了checkIndex方法,方法实现在下面} catch (IndexNotLegalException e) {e.printStackTrace();}//index==0,相当于头部插入if (index == 0) {addFirst(data);return;}//index==size(),相当于尾部插入if(index==size()){addLast(data);return;}//0<index<size()if(index>0&&index<size()){//找到下标为index的节点ListNode cur=findIndex(index);//调用了findIndex方法,方法实现在下面//连接节点ListNode node=new ListNode(data);node.next=cur;node.pre=cur.pre;cur.pre.next=node;cur.pre=node;return;}}//调用方法的实现://找到index节点的方法:public ListNode findIndex(int index){int count=index;ListNode cur=head;while(count!=0){cur=cur.next;count--;}return  cur;}//检查index是否合法的方法private void checkIndex(int index){if(index<0||index>size()){throw new IndexNotLegalException("Index 不合法!"+index);}}

详细介绍; 

指定插入的方法需要传入一个下标,在指定下标的节点之前插入一个节点!

那么,根据下标的值可以分为四种情况:
i>下标不合法

此时先自定义一个异常类:

另外,需要在MyLinkedList类中创建一个方法,用来判断下标是否合法,如果不合法,抛出该异常类

//检查index是否合法的方法private void checkIndex(int index){if(index<0||index>size()){throw new IndexNotLegalException("Index 不合法!"+index);}}

 此时,就可以在指定位置插入的方法中写下标不合法的代码:

ii>index==0

当index==0,相当于头插,此时调用头部插入的方法即可

iii>index==size()

当index==size(),相当于尾部插入,此时调用尾部插入的方法即可

iiii>index>0&&index<size() 

这种情况属于指定位置插入的正常情况,它既不是头部插入,也不是尾部插入,而是在两个节点中间插入!

首先,需要使用创建cur找到下标为index的节点,以图为例子:我们要在下标为2的节点前插入node新节点!

那么,实例化node之后,我们就得根据如图中的箭头将新节点连接到链表中。可以看到,要修改四个引用的内容!

node.pre=cur.pre;

node.next=cur;

cur.pre.next=node;

cur.pre=node;

修改后:

代码实现:

//0<index<size()if(index>0&&index<size()){//找到下标为index的节点ListNode cur=findIndex(index);//调用findIndex方法//连接节点ListNode node=new ListNode(data);node.next=cur;node.pre=cur.pre;cur.pre.next=node;cur.pre=node;return;}

 调用的findIndex方法:

也是写在MyLinkedList类内部:

 //找到index节点的方法:public ListNode findIndex(int index){int count=index;ListNode cur=head;while(count!=0){cur=cur.next;count--;}return  cur;}


5、删除第一次出现关键字key的节点的方法:

删除第一次出现关键字key的节点,首先,先实例化一个cur帮助我们找到想要删除的节点

然后再执行删除操作,cur所在节点的位置不同,所要执行的操作也不同,这里分为三种情况:

1、cur所在节点为中间节点

2、cur==head

3、cur==last

先来说说第一种情况:cur所在节点为中间节点

首先,我们使用cur找到了关键字为12所在的节点!然后,执行删除操作!

这里只需要将cur所在的前后节点依照如图箭头方向连接即可!

cur.pre.next=cur.next;

cur.next.pre=cur.pre;

第二种情况:cur==head

这种情况下,我们会发现,如果照搬第一种情况的代码

cur.pre.next=cur.next;//由于head.pre==null,因此会报错

cur.next.pre=cur.pre;

所以,此时,我们只需要将这么写

head=head.next;  //头节点换到下一个节点

head.pre=null;     //将新的头节点的pre修改为null

特殊情况:

如果链表中只有一个节点!

那么执行完语句head=head.next后,head==null,因此语句head.pre=null(相当于null.pre=null)会报错!

所以,在cur==head的情况下,我们还要解决链表只有一个节点的特殊情况:

if (cur == head) {//关键字在头节点head = head.next;//判断链表是否只有一个节点!if(head!=null){head.pre = null;}else{//只有一个节点的情况:last=null;}}

第三种情况:cur==last

此时,这种情况下,代码这么写:

cur.pre.next=cur.next;  //将前一个节点的next置为null(cur.next==null)

last=last.pre;                //last向前移动一个节点

代码实现:

//删除第一次出现关键字key的节点public void remove(int key) {//使用cur寻找关键字所在的节点ListNode cur = head;while (cur != null) {if (cur.val == key) {if (cur == head) {//关键字在头节点head = head.next;//判断链表是否只有一个节点!if(head!=null){head.pre = null;}else{last=null;}} else { //关键字在尾节点if (cur == last) {cur.pre.next = cur.next;last = last.pre;} else {  //关键字在中间节点cur.pre.next = cur.next;cur.next.pre = cur.pre;}}return;//删完一个就走}cur = cur.next;}}


6、删除所有值为key的节点的方法:

有了上一个方法的学习,这个方法那就很简单了,只需要注释掉return语句即可,我们可以回头看看上述代码,它的整体逻辑是删除第一个关键字为key的节点就结束循环,那么,我们是不是就可以在删除完一个节点后选择不结束该方法,让它继续删除呢。当然可以!

//删除所有值为key的节点public void removeAllKey(int key){//使用cur寻找关键字所在的节点ListNode cur = head;while (cur != null) {if (cur.val == key) {if (cur == head) {//关键字在头节点head = head.next;//判断链表是否只有一个节点!if(head!=null){head.pre = null;}else{last=null;}} else { //关键字在尾节点if (cur == last) {cur.pre.next = cur.next;last = last.pre;} else {  //关键字在中间节点cur.pre.next = cur.next;cur.next.pre = cur.pre;}}//return;注释该语句,使其多次删除关键字为key的节点}cur = cur.next;}}


7、清空链表方法:

这里清空链表的主要逻辑是将每一个节点的pre和next置为null,最后将head和last置为null 

//删除列表public void clear(){ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.pre=null;cur.next=null;cur=curN;}head=last=null;}

 



三、LinkedList的使用

  上面我们讲解了如何实现双向链表,这其实是Java自带的LinkedList的底层实现,接下来让我们来学习Java自带的LinkedList吧!

1、LinkedList的构造

LinkedList有两个构造方法,在使用LinkedList之前,我们需要调用构造方法实例化一个对象。

方法:                                                解释:
LinkedList()                                       无参构造
public LinkedList(Collection<? extends E> c)         使用其他集合容器中元素构造List

第一个无参构造就不多解释了,因为比较好懂,那么我们来解释一下第二个构造方法可以传入那些参数?

首先,我们需要知道的是:

1、Collection是传入参数的类型

2、?表示:Collection<>中传入的类型

3、<? extends E>表示:?代表的这个类型要么继承E这个类型,要么继承E这个类型的子类

可以看到,第二个构造方法可以传入参数list,此时可能有以下疑问:

1、传入的参数类型是Collection类型的,那么为什么可以传入LinkedList类型的list呢?

答:LinkedList类型实现了Collection接口!

2、如何解释list符合<? extends E>

答:在实例化list的时候,LinkedList传入的参数类型是Integer,此时这个Integer代表  ?

      在实例化list2的时候,LinkedList传入的参数类型是Integer,此时这个Integr代表   E

      也即是说:? 继承了  E  这个类型,所以这个传入参数list是符合<? extends E>的

 

另外在实例化LinkedList的时候,因为LinkedList实现了List接口,因此在实例化的时候有两种写法:



 

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

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

相关文章

Tomcat的安装

Tomcat的网址https://tomcat.apache.org/ 点击进去之后的左边可以选择要下载的版本 可以通过下面的which version来进行确定你当前的jdk版本适配的Tomact版本 点进去之后 我的Tomcat适配8版本 点击Core的ZIP进行下载。 下载之后会给一个压缩文件将其进行解压随 最终呈现出这…

c++20协程详解(四)

前言 到这就是协程的最后一节了。希望能帮到大家 代码 到这里我们整合下之前二、三节的代码 #include <coroutine> #include <functional> #include <chrono> #include <iostream> #include <thread> #include <mutex> #include <me…

配置vscode用于STM32编译,Debug

配置环境参考&#xff1a; Docs 用cubemx配置工程文件&#xff0c;用VScode打开工程文件。 编译的时候会有如下报错&#xff1a; vscode出现process_begin :CreateProcess failed 系统找不到指定文件 解决方案&#xff1a;在你的makefile中加上SHELLcmd.exe就可以了 参考…

nest.js + sms 实现短信验证码登录

文章目录 一、前言1、方案概述 二、教程1、阿里云配置&#xff08;1&#xff09;购买短信服务&#xff08;2&#xff09;、短信测试&#xff08;3&#xff09;、资质申请&#xff08;4&#xff09;、通用设置 2、获取API代码示例3、运行工程代码 一、前言 最近做些网站的时候&…

蓝桥杯刷题-12-公因数匹配-数论(分解质因数)不是很理解❓❓

蓝桥杯2023年第十四届省赛真题-公因数匹配 给定 n 个正整数 Ai&#xff0c;请找出两个数 i, j 使得 i < j 且 Ai 和 Aj 存在大于 1 的公因数。 如果存在多组 i, j&#xff0c;请输出 i 最小的那组。如果仍然存在多组 i, j&#xff0c;请输出 i 最小的所有方案中 j 最小的那…

Java | Leetcode Java题解之第16题最接近的三数之和

题目&#xff1a; 题解&#xff1a; class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int n nums.length;int best 10000000;// 枚举 afor (int i 0; i < n; i) {// 保证和上一次枚举的元素不相等if (i > 0 && nums…

Mac安装Docker提示Another application changed your Desktop configuration解决方案

1. 问题描述 Mac安装Docker后&#xff0c;提示Another application changed your Desktop configuration&#xff0c;Re-apply configurations无效 2. 解决方案 在终端执行下述命令即可解决&#xff1a; sudo ln -sf /Applications/Docker.app/Contents/Resources/bin/docke…

springCloud-LoadBalancer负载均衡微服务负载均衡器LoadBalancer

2020年前SpringCloud是采用Ribbon作为负载均衡实现&#xff0c;但是在2020后采用了LoadBalancer替代 LoadBalancer默认提供了两种负载均衡策略&#xff08;只能通过配置类来修改负载均衡策略&#xff09; 1.RandomLoadBalancer-随机分配策略 2.RoundRobinLoadBalancer-轮询分配…

使用pytorch构建有监督的条件GAN(conditional GAN)网络模型

本文为此系列的第四篇conditional GAN&#xff0c;上一篇为WGAN-GP。文中在无监督的基础上重点讲解作为有监督对比无监督的差异&#xff0c;若有不懂的无监督知识点可以看本系列第一篇。 原理 有条件与无条件 如图投进硬币随机得到一个乒乓球的例子可以看成是一个无监督的GAN&…

服务器主机安全受到危害的严重性

为了让小伙伴们了解到服务器主机安全受到危害的严重性&#xff0c;以下详细说明一下&#xff1a;1. 数据泄露&#xff1a;如果服务器主机遭受攻击&#xff0c;攻击者可能会窃取敏感数据&#xff0c;如用户数据、商业秘密、机密文件等&#xff0c;导致数据泄露和商业机密的泄漏。…

Mac怎么调大音频音量?

Mac怎么调大音频音量&#xff1f;在使用 Mac 电脑时&#xff0c;有时可能会发现音频的音量不够大&#xff0c;特别是在观看视频、听音乐或进行视频会议时。不过&#xff0c;幸运的是&#xff0c;Mac 提供了多种方法来调大音频音量&#xff0c;让您更好地享受音乐和视频的乐趣。…

如何在 Node.js 中使用 bcrypt 对密码进行哈希处理

在网页开发领域中&#xff0c;安全性至关重要&#xff0c;特别是涉及到用户凭据如密码时。在网页开发中至关重要的一个安全程序是密码哈希处理。 密码哈希处理确保明文密码在数据库受到攻击时也难以被攻击者找到。但并非所有的哈希方法都是一样的&#xff0c;这就是 bcrypt 突…

34470A是德科技34470A数字万用表

181/2461/8938产品概述&#xff1a; Truevolt数字万用表&#xff08;34460A、34461A、34465A、34470A&#xff09;利用是德科技的新专利技术&#xff0c;使您能够快速获得见解、测量低功耗设备并保持校准的测量结果。Truevolt提供全方位的测量能力&#xff0c;具有更高的精度、…

15-1-Flex布局

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 Flex布局1 Flex容器和Flex项目2 Flex 容器属性2.1 主轴的方向2.2 主轴对齐方式…

亚马逊店铺引流:海外云手机的利用方法

在电商业务蓬勃发展的当下&#xff0c;亚马逊已经成为全球最大的电商平台之一&#xff0c;拥有庞大的用户群和交易量。在激烈的市场竞争中&#xff0c;如何有效地吸引流量成为亚马逊店铺经营者所关注的重点。海外云手机作为一项新兴技术工具&#xff0c;为亚马逊店铺的流量引导…

基于SSM的周边乡村旅游小程序

系统实现 游客注册通过注册窗口&#xff0c;进行在线填写自己的账号、密码、姓名、年龄、手机、邮箱等&#xff0c;信息编辑完成后核对信息无误后进行选择注册&#xff0c;系统核对游客所输入的账号信息是否准确&#xff0c;核对信息准确无误后系统进入到操作界面。 游客登录通…

Node.js进阶——Express

文章目录 一、初识Express1、概念2、安装3、使用3、托管静态资源4、nodemon 二、Express路由1、概念2、使用1&#xff09;简单使用2&#xff09;模块化路由 三、Express中间件1、介绍2、语法1&#xff09;基本语法2&#xff09;next函数作用3&#xff09;定义中间件函数4&#…

4.7学习总结

java学习 一.Stream流 (一.)概念: Stream将要处理的元素集合看作一种流&#xff0c;在流的过程中&#xff0c;借助Stream API对流中的元素进行操作&#xff0c;比如&#xff1a;筛选、排序、聚合等。Stream流是对集合&#xff08;Collection&#xff09;对象功能的增强&…

在python爬虫中如何处理cookie和session

使用python开发爬虫的过程中&#xff0c;遇到需要登录鉴权的一些页面&#xff0c;必不可少的会接触到cookie和session的使用。本文结合自己最近一次爬虫爬坑的经历&#xff0c;介绍在python爬虫中如何使用Cookie和Session Cookie和Session的介绍 Cookie Cookie 是一种用于跟…

脱单微信群|相亲脱单支招|手把手教你脱单

群里有太多优质单身男女生&#xff0c;你的脱单困惑&#xff0c;TA可能也遇到过。抬手在群里滴滴&#xff0c;即刻拥有一群有过相同问题的友友和运营客服帮忙。 点我进脱单群 点击 情感脱单问题&#xff0c;直接私信给樱桃情感老师&#xff0c;保护个人隐私和提升问题解决效率…