Collection与数据结构 链表与LinkedList(四):双向无头非循环链表的实现与LinkedList的使用

news/2024/6/24 8:49:31/文章来源:https://blog.csdn.net/2301_80050796/article/details/137263738

1. 双向无头非循环链表的实现

在这里插入图片描述
下面我们给出一个接口,接口中的这些方法就是待实现的方法

public interface ILinkedList_2 {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void display();void clear();}

下面实现这些方法:

/*** 双向链表的实现*/
public class MyLinkedList_2 implements ILinkedList_2 {class ListNode{public ListNode pre;//比单向链表多出来的地方,和前一个结点也是连起来的public ListNode next;public int val;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//有末结点/*** 头插法* @param data*/@Overridepublic void addFirst(int data) {ListNode listNode = new ListNode(data);if (head == null){//注意为空的情况head = listNode;last = listNode;}else{//注意加上else,否则在一开始的时候,listnode.next为head,next就会被置为head//就会永远在头结点处死循环listNode.next = head;head.pre = listNode;head = listNode;}}/*** 尾插法* @param data*/@Overridepublic void addLast(int data) {ListNode listNode = new ListNode(data);if (head == null){head = listNode;last = listNode;}else {listNode.pre = last;last.next = listNode;last = last.next;}}private boolean checkIndex(int index){//检查index是否合法if (index > size() ||index < 0){return false;}return true;}private ListNode findNode(int index) {//找到对应下标的结点ListNode cur = head;int count = 0;while (count != index){count ++;cur = cur.next;}return cur;}/*** 在指定位置插入结点* @param index* @param data*/@Overridepublic void addIndex(int index, int data) {if (!checkIndex(index)){throw new IndexExecption("下标输入有误");}if (index == 0){addFirst(data);return;//记得返回,不然下面的代码也会执行}if (index == size()){addLast(data);return;}ListNode listNode = new ListNode(data);ListNode cur = findNode(index);listNode.next = cur;listNode.pre = cur.pre;cur.pre.next = listNode;cur.pre = listNode;}/*** 查看链表中是否包含指定元素* @param key* @return*/@Overridepublic boolean contains(int key) {if (head == null){return false;}ListNode cur = head;while (cur != null){//先遍历链表if (cur.val == key){return true;//找到相等的值直接返回true}cur = cur.next;}return false;//跳出来就证明已经走到了终点,没找到}/*** 删除第一个值为key的结点* @param key*/@Overridepublic void remove(int key) {ListNode cur = head;while(cur != null){//cur向下遍历if (cur.val == key){//cur找到的清空if (cur == head){//如果cur为头结点head = head.next;//head向后移动if (head != null){head.pre = null;}else {//如果cur为头结点且只有一个结点last = null;//last也置为空}}else {//cur不为头结点if (cur.next != null){//cur为中间结点cur.pre.next = cur.next;cur.next.pre = cur.pre;}else {//cur为尾结点cur.pre.next = null;last = last.pre;}}return;//删完返回}cur = cur.next;//cur向下走}}/*** 删除所有值为key结点* @param key*/@Overridepublic void removeAllKey(int key) {ListNode cur = head;while(cur != null){//cur向下遍历if (cur.val == key){//cur找到的清空if (cur == head){//如果cur为头结点head = head.next;//head向后移动if (head != null){head.pre = null;}else {//如果cur为头结点且只有一个结点last = null;//last也置为空}}else {//cur不为头结点if (cur.next != null){//cur为中间结点cur.pre.next = cur.next;cur.next.pre = cur.pre;}else {//cur为尾结点cur.pre.next = null;last = last.pre;}}//直接把return去掉,删完不返回,继续删}cur = cur.next;//cur向下走}}/*** 计算链表大小* @return*/@Overridepublic int size() {int count = 0;ListNode cur = head;while (cur != null){cur = cur.next;count++;}return count;}/*** 打印链表*/@Overridepublic void display() {ListNode cur = head;while (cur != null){System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}/*** 清空链表*/@Overridepublic void clear() {ListNode cur = head;while (cur != null){ListNode curNext = cur.next;//记录下一个结点cur.next = null;cur.pre = null;//每一个结点的next和pre都置空cur = curNext;}head = null;last = null;//head和last指向的仍然是原来的地址,cur只是修改了节点内的值,//所以head和last需要手动置空}
}

[注意事项]

  1. 在头插法和尾插法的过程中,如果该链表为空,在把该链表的头结点和尾结点都指向添加结点之后,记得后面不符合条件的语句用else括起来,否者在头插或尾插之后,还会执行head!=null的代码
  2. 在中间插入节点的时候,如果插入的结点为头插或者是尾插的时候,记得返回,否者和上面的一条一样,执行完头插和尾插之后,又会执行中间插入的代码.
  3. 删除代码的逻辑较为复杂,我们通过一张图来表示
    在这里插入图片描述
    测试上面实现的方法:
/*** 开始测试*/
public class Test {public static void main(String[] args) {MyLinkedList_2 myLinkedList_2 = new MyLinkedList_2();myLinkedList_2.addFirst(1);myLinkedList_2.addFirst(2);myLinkedList_2.addFirst(3);myLinkedList_2.addFirst(4);myLinkedList_2.display();MyLinkedList_2 myLinkedList_21 = new MyLinkedList_2();myLinkedList_21.addLast(1);myLinkedList_21.addLast(2);myLinkedList_21.addLast(3);myLinkedList_21.addLast(4);myLinkedList_21.display();myLinkedList_21.addIndex(1,34);myLinkedList_21.addIndex(2,45);myLinkedList_21.display();MyLinkedList_2 myLinkedList_22 = new MyLinkedList_2();myLinkedList_22.addIndex(0,1);myLinkedList_22.addIndex(1,2);myLinkedList_22.addIndex(2,3);myLinkedList_22.display();System.out.println(myLinkedList_22.contains(2));System.out.println(myLinkedList_22.contains(4));myLinkedList_21.remove(2);myLinkedList_21.display();MyLinkedList_2 myLinkedList_23 = new MyLinkedList_2();MyLinkedList_2 myLinkedList_24 = new MyLinkedList_2();myLinkedList_23.addFirst(1);myLinkedList_23.remove(1);myLinkedList_23.display();myLinkedList_24.remove(1);MyLinkedList_2 myLinkedList_25 = new MyLinkedList_2();myLinkedList_25.addFirst(2);myLinkedList_25.remove(1);MyLinkedList_2 myLinkedList_26 = new MyLinkedList_2();myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(2);myLinkedList_26.removeAllKey(1);myLinkedList_26.display();}
}

测试结果:

在这里插入图片描述

2. LinkedList的使用

LinkedList的底层是双向无头非循环链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高.

2.1 构造方法

方法说明
public LinkedList()无参构造方法
public LinkedList(Collection<? extends E> c)使用容器中的其他容器来构造,传入的容器中的数据类型必须是E的子类,以便兼容
public class LinkedList1 {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);List<Integer> list1 = new ArrayList<>();list1.add(1);list1.add(2);list1.add(3);LinkedList<Number> list2 = new LinkedList<>(list1);}
}

2.2 常用方法

方法说明
boolean add(E e)尾插 e
void add(int index, E element)将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)尾插 c 中的元素
E remove(int index)删除 index 位置元素
boolean remove(Object o)删除遇到的第一个 o
E get(int index)获取下标 index 位置元素
E set(int index, E element)将下标 index 位置元素设置为 element
void clear()清空
boolean contains(Object o)判断 o 是否在线性表中
int indexOf(Object o)返回第一个 o 所在下标
int lastIndexOf(Object o)返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)截取部分 list
public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素,内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在,如果存在返回true,否则返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem = list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list.subList(0, 3); System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());
}

2.3 LinkedList的遍历

import java.util.*;public class LinkedList1 {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);//通过sout遍历for (int x: list) {//通过for_each遍历System.out.print(x+" ");}ListIterator<Integer> iterator = list.listIterator();while (iterator.hasNext()){//通过迭代器向后遍历System.out.println(iterator.next());}ListIterator<Integer> iterator1 = list.listIterator(list.size());while (iterator1.hasPrevious()){//通过迭代器向前遍历System.out.println(iterator1.previous());}}
}

面试题 ArrayList与LinkedList的区别
从插入,修改,删除,查找这几方面来说

  1. 插入:顺序表在插入的时候必须把插入点之后的元素全部后移,而链表不需要
  2. 修改:顺序表可以直接根据下标找到要修改的元素,而链表需要遍历
  3. 删除:顺序表删除点之后的元素必须向前移动,而链表不需要
  4. 查找: 顺序表可以直接根据下标查找,而链表需要遍历

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

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

相关文章

Python框架下的qt设计之JSON格式化转换小程序

JSON转换小程序 代码展示&#xff1a; 主程序代码&#xff1a; from PyQt6.QtWidgets import (QApplication, QDialog, QMessageBox )import sys import jsonclass MyJsonFormatter(jsonui.Ui_jsonFormatter,QDialog): # jsonui是我qt界面py文件名def __init__(self):super()…

在Arduino IDE中使用文件夹组织源文件和头文件

在Arduino IDE中使用文件夹组织源文件和头文件 如果你是一名Arduino爱好者&#xff0c;你可能会发现随着项目的复杂度增加&#xff0c;代码的管理变得越来越困难。在Arduino IDE中&#xff0c;你可以通过使用文件夹来更好地组织你的源文件和头文件&#xff0c;使得代码更加清晰…

【PyTorch][chapter 25][李宏毅深度学习][ CycleGAN]【实战】

前言&#xff1a; 论文中直接提供了GitHub 的代码下载地址 GitHub - junyanz/pytorch-CycleGAN-and-pix2pix: Image-to-Image Translation in PyTorch 这里面简单的解读一下. 目录&#xff1a; 1. 模型参数配置 2&#xff1a; 生成器模型 3&#xff1a; 鉴别器模型 4&#…

[计算机效率] 文本编辑工具:Notepad++

3.12 文本编辑工具&#xff1a;Notepad Notepad是一款免费的文本编辑器&#xff0c;适用于Windows操作系统。它具有轻量级、高效、可定制性强等特点&#xff0c;并且支持多种语言。以下是关于Notepad的详细介绍&#xff1a; 功能特点&#xff1a; 多语言支持&#xff1a;Note…

Flutter 开发学习笔记(4):widget布局容器学习

文章目录 前言相关链接Widget 有状态和无状态Flutter 代码风格去掉烦人的括号后缀提示代码缩进 Flutter 布局最简单的布局widgets和Material widgets Dark语法习惯Flutter 布局默认布局Center居中Padding 填充Align对齐默认居中顶部底部右上角 通用 WidgetContainer处于性能原因…

Matlab|计及需求侧响应日前—日内两阶段鲁棒备用优化

目录 1 主要内容 日前计划模型 日内调整模型 不确定集建模 2 部分代码 3 程序结果 4 下载链接 1 主要内容 该程序复现文章《计及需求侧响应日前—日内两阶段鲁棒备用优化》&#xff0c;以6节点系统为例&#xff0c;综合考虑风电出力不确定性与电力设备 N-k强迫停运&…

小剧场短剧影视小程序源码,附带系统搭建教程

安装教程 linux/win任选 PHP版本&#xff1a;7.3/7.2&#xff08;测试时我用的7.2要安装sg扩展 不会的加QQ295526639&#xff09; 批量替换域名http://video.owoii.com更换为你的 批量替换域名http://120.79.77.163:1更换为你的 这两个都替换你的 /extend/yzf/lib/epay.config.…

Android获取连接到手机热点上的设备信息

主题&#xff1a;在手机开启热点网络的情况下&#xff0c;想要获取是哪个设备已经连接上了当前开启的热点。 实现思路&#xff1a;Android通过读取 /proc/net/arp 文件可以得到连接当前热点的设备信息&#xff0c;包括Mac地址、IP地址等信息。 一. 方法逻辑&#xff1a; /*** …

springboot读取绝对路径如何处理

我的需求是springboot集成kafka需要读取证书文件&#xff0c;然后进行消费工厂的创建和监听&#xff0c;当然这里需要用到绝对路径文件的读取&#xff0c;相对路径是不支持的。 开始之前我们使用常用的几种方式获取路径文件的方式&#xff1a; getClass().getClassLoader().ge…

网络安全应急响应:保护网络安全的最后一道防线

网络安全应急响应&#xff1a;保护网络安全的最后一道防线 网络安全是当今信息社会中至关重要的问题&#xff0c;网络攻击的频繁发生使得企业、政府和个人面临着越来越大的安全威胁。为了及时有效地应对网络安全事件&#xff0c;网络安全应急响应成为了必不可少的一环。 小德将…

【WSN覆盖】基于灰狼优化算法的三维无线传感器网络覆盖优化 三维WSN覆盖优化【Matlab代码#72】

文章目录 【可更换其他算法&#xff0c;获取资源请见文章第5节&#xff1a;资源获取】1. 基础灰狼算法2. 三维覆盖模型3. 部分代码展示4. 仿真结果展示5. 资源获取 【可更换其他算法&#xff0c;获取资源请见文章第5节&#xff1a;资源获取】 1. 基础灰狼算法 比较常见&#x…

硬件-1、体系架构

cpu 处理器 arm处理器的七种工作模式 arm寄存器 两张图是一样的&#xff0c;r0---r12是通用寄存器。其他寄存器可参考图一&#xff0c;cpu架构。 程序状态寄存器psr&#xff08;cpsr/spsr&#xff09; 程序异常处理 理解示例 当使用swi&#xff08;软中断指令&#xff09;指令…

Android仿高德首页三段式滑动

最近发现很多app都使用了三段式滑动&#xff0c;比如说高德的首页和某宝等物流信息都是使用的三段式滑动方式&#xff0c;谷歌其实给了我们很好的2段式滑动&#xff0c;就是BottomSheet&#xff0c;所以这次我也是在这个原理基础上做了一个小小的修改来实现我们今天想要的效果。…

010_documentation_in_Matlab中的帮助与文档

Matlab中的帮助与文档 1. 前言 一眨眼已经写了十篇文章。 000在Matlab中使用Python包CoolProp001Matlab运行时间测试与时间复杂度分析002避免使用for循环003Matlab中的向量约定004Matlab中的矩阵约定005Matlab中的数组索引006Matlab中的逻辑数组索引007Matlab学习的启动与加…

研发图纸管理软件,研发图纸管理软件解决方案

研发图纸管理软件行业的排名因市场变化和技术发展而不断变化&#xff0c;因此很难给出一个确切的排名。不过&#xff0c;以下是一些在研发图纸管理软件领域具有较高知名度和影响力的品牌&#xff0c;它们提供了丰富的功能和解决方案&#xff0c;帮助企业更好地管理和利用研发图…

uniapp创建opendb-city-china Schema文件后,如何导入城市的数据?

1.点击opendb-city-china后面的详情&#xff0c;进入到gitee代码仓库 2.下载如下图所示的data.json文件 3.将本地创建的opendb-city-china.schema.json上传到云端 4.点击导入json 如果直接将data.json导入会报错&#xff0c;如下图所示: 5.将data.json本来的数组对象&#…

游戏引擎架构01__引擎架构图

根据游戏引擎架构预设的引擎架构来构建运行时引擎架构 ​

idea端口占用

报错&#xff1a;Verify the connector‘s configuration, identify and stop any process that‘s listening on port XXXX 翻译&#xff1a; 原因&#xff1a; 解决&#xff1a; 一、重启大法 二、手动关闭 启动spring项目是控制台报错&#xff0c;详细信息如下&#xff…

【机器学习300问】61、逻辑回归与线性回归的异同?

本文讲述两个经典机器学习逻辑回归&#xff08;Logistic Regression&#xff09;和线性回归&#xff08;Linear Regression&#xff09;算法的异同&#xff0c;有助于我们在面对实际问题时更好的进行模型选择。也能帮助我们加深对两者的理解&#xff0c;掌握这两类基础模型有助…

kubernetes-dashboard 安装配置

k8s 1.23以上的版本 https://raw.githubusercontent.com/kubernetes/dashboard/v2.7.0/aio/deploy/recommended.yaml 执行命令&#xff1a; kubectl apply -f https://raw.githubusercontent.com/kubernetes/dashboard/v2.7.0/aio/deploy/recommended.yaml 安装完成后&#x…