Java中的链表

文章目录

  • 前言
  • 一、链表的概念及结构
  • 二、单向不带头非循坏链表的实现
    • 2.1打印链表
    • 2.2求链表的长度
    • 2.3头插法
    • 2.4尾插法
    • 2.5任意位置插入
    • 2.6查找是否包含某个元素的节点
    • 2.7删除第一次出现这个元素的节点
    • 2.8删除包含这个元素的所以节点
    • 2.9清空链表
    • 单向链表的测试
  • 三、双向不带头非循坏链表的实现
    • 3.1打印双向链表
    • 3.2求双向链表的长度
    • 3.3头插法
    • 3.4尾插法
    • 3.5任意位置插入
    • 3.6查找是否包含某个元素的节点
    • 3.7删除第一次出现这个元素的节点
    • 3.7删除包含这个元素的所有节点
    • 3.9清空双向链表
    • 双向链表的测试
    • LinkedList的遍历方式
    • 四、ArrayList和LinkedList的区别


前言

在前面我们已经学习了关于顺序表ArrayList的一些基本操作。通过源码知道,ArrayList底层使用数组来存储元素,由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java集合中又引入了LinkedList,即链表结构


一、链表的概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的
注意:
1.链式结构在逻辑上是连续的,但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能是连续,也可能不连续

链表的结构有8种样式:
单向带头循坏、单向带头非循坏、单向不带头循坏、单向不带头非循坏
双向带头循坏、双向带头非循坏、双向不带头循坏、双向不带头非循坏

这里我们主要学习以下两中结构:
单向不带头非循坏
在这里插入图片描述
LinkedList底层使用的就是双向不带头非循坏
在这里插入图片描述

二、单向不带头非循坏链表的实现

2.1打印链表

不带参数的打印

public void display() {ListNode cur = head;if(cur != null) {//遍历完所以节点System.out.print(cur.val+" ");cur = cur.next;}System.out.println();
}

带参数的打印

public void display(ListNode newHead) {ListNode cur = newHead;if(cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();
}    

2.2求链表的长度

public int size(){ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;
}    

2.3头插法

public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;
}

2.4尾插法

public void addLast(int data){ListNode node = new ListNode(data);if(head == null) {head = node;}else {ListNode cur = head;while (cur.next != null) {//走到最后一个节点的位置cur = cur.next;}cur.next = node;}
}

2.5任意位置插入

在任意位置插入时我们要判断该位置是否合法,不合法的时候要抛一个异常

  public void addIndex(int index,int data){if(index < 0 || index > size()) {throw new IndexException("index位置不合法:"+index);}ListNode node = new ListNode(data);if(head == null) {head = node;return;}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//中间插入ListNode cur = serchIndex(index);node.next = cur.next;cur.next = node;
}    

找要添加节点位置的前一个节点

public ListNode serchIndex(int index) {ListNode cur = head;int count = 0;while (count != index-1) {cur = cur.next;count++;}return cur;
}    

2.6查找是否包含某个元素的节点

遍历这个链表找是否与这个元素相同

public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;
}    

2.7删除第一次出现这个元素的节点

public void remove(int key){if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode cur = findKey(key);if(cur == null) {return;//没有要删除的元素}ListNode del = cur.next;cur.next = del.next;
}    

要删除节点的前一个节点

public ListNode findKey(int key) {ListNode cur = head;while (cur.next != null) {if(cur.next.val == key) {return cur;}else {cur = cur.next;}}return null;
}    

2.8删除包含这个元素的所以节点

public void removeAllKey(int key){if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while (cur != null){if(cur.val == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}//除了头节点外,其余都删完了if(head.val == key) {head = head.next;}
}    

2.9清空链表

清空链表只需要把头节点置为空

public void clear() {head = null;
}    

单向链表的测试

public class Test {public static void main(String[] args) {MySingleList list = new MySingleList();list.addLast(30);//尾插list.addLast(20);list.addLast(30);list.addLast(40);list.addLast(50);list.addFirst(100);//头插list.addIndex(2,15);//任意位置插入list.display();System.out.println("*****");System.out.println(list.contains(20));//查看是否包含某个节点System.out.println("*****");System.out.println(list.size());//求链表长度System.out.println("*****");list.remove(30);//删除第一个出现的节点list.display();list.removeAllKey(30);//删除包含这个元素的所以节点System.out.println("*****");list.display();System.out.println("*****");list.clear();//清空链表list.display();}
}

在这里插入图片描述

三、双向不带头非循坏链表的实现

3.1打印双向链表

public void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();
}    

3.2求双向链表的长度

public int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;
}    

3.3头插法

public void addFist(int data) {ListNode node = new ListNode(data);if(head == null) {//一个节点都没有的情况head = node;last = node;}else {node.next = head;head.prev = node;head = node;}
}    

3.4尾插法

public void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {//一个节点都没有的情况head = node;last = node;}else {last.next = node;node.prev = last;last = node;}
}    

3.5任意位置插入

这里的插入与单向链表一样也需要判断该位置的合法性,不合法时抛一个异常

public void addIndex(int index,int data) {if(index < 0 || index > size()) {throw new IndexException("双向链表中index的位置不合法:"+index);}if(index == 0) {addFist(data);}if(index == size()) {addLast(data);}ListNode cur = findIndex(index);ListNode node = new ListNode(data);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;
}    

要添加节点的位置

public ListNode findIndex(int index) {ListNode cur = head;if(index != 0) {cur = cur.next;index --;}return cur;
}    

3.6查找是否包含某个元素的节点

public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;
}    

3.7删除第一次出现这个元素的节点

因为数据结构是一门逻辑性非常严谨的学科,所以这里的删除需要考虑多种因素

public void remove(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;if (head != null) {head.prev = null;}else {//只有一个节点,而且是需要删除的节点last = null;}}else {//删除中间节点if(cur.next != null) {cur.next.prev = cur.prev;cur.prev.next = cur.next;}else {//删除尾巴节点cur.prev.next = cur.next;last = last.prev;}}return;}cur = cur.next;}
}    

3.7删除包含这个元素的所有节点

public void remove(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;if (head != null) {head.prev = null;}else {//只有一个节点,而且是需要删除的节点last = null;}}else {//删除中间节点if(cur.next != null) {cur.next.prev = cur.prev;cur.prev.next = cur.next;}else {//删除尾巴节点cur.prev.next = cur.next;last = last.prev;}}}cur = cur.next;}
}    

3.9清空双向链表

public void clear(){ListNode cur = head;while (cur != null) {ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = cur.next;}head = null;//头节点置空last = null;//尾巴节点置空
}    

双向链表的测试

public class Test {public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.addLast(12);//尾插法myLinkedList.addLast(45);myLinkedList.addLast(34);myLinkedList.addLast(45);myLinkedList.addFist(56);//头插法myLinkedList.addIndex(2,15);//任意位置插入myLinkedList.display();System.out.println(myLinkedList.size());//求双向链表的长度System.out.println("******");System.out.println(myLinkedList.contains(23));//查找是否包含某个元素的节点System.out.println("******");myLinkedList.remove(45);//删除第一次出现这个元素的节点myLinkedList.display();System.out.println("******");myLinkedList.removeAllKey(45);//删除包含这个元素的所以节点myLinkedList.display();System.out.println("******");myLinkedList.clear();//清空链表myLinkedList.display();}
}

在这里插入图片描述

LinkedList的遍历方式

关于LinkedList的遍历方式有四种:

public class Test {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);System.out.println(list);//for循坏遍历for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();System.out.println("*******");//foreach遍历for (int m : list) {System.out.print(m +" ");}System.out.println();System.out.println("*******");//使用迭代器——正向遍历ListIterator<Integer> it = list.listIterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();System.out.println("*******");//使用迭代器——反向遍历ListIterator<Integer> it2 = list.listIterator(list.size());while (it2.hasPrevious()) {System.out.print(it2.previous()+" ");}System.out.println();}
}    

在这里插入图片描述

四、ArrayList和LinkedList的区别

1.ArrayList在物理上是连续的,LinkedList在逻辑上连续,但在物理上不一定连续
2.ArrayList和LinkedList是两种不同的数据结构。ArrayList是基于动态数组的,而LinkedList则是基于链表的
3.当需要随机访问元素(如get和set操作)时,ArrayList效率更高,因为LinkedList需要逐个查找。但当进行数据的增加和删除操作(如add和remove操作)时,LinkedList效率更高,因为ArrayList在进行这些操作时需要移动大量数据
4.ArrayList需要手动设置固定大小的容量,使用方便但自由性低;而LinkedList能够随数据量变化而动态调整,自由性较高但使用较为复杂

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

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

相关文章

RNN介绍及Pytorch源码解析

介绍一下RNN模型的结构以及源码&#xff0c;用作自己复习的材料。 RNN模型所对应的源码在&#xff1a;\PyTorch\Lib\site-packages\torch\nn\modules\RNN.py文件中。 RNN的模型图如下&#xff1a; 源码注释中写道&#xff0c;RNN的数学公式&#xff1a; 表示在时刻的隐藏状态…

可替代LM5145,5.5V-100V Vin同步降压控制器_SCT82A30

SCT82A30是一款100V电压模式控制同步降压控制器&#xff0c;具有线路前馈。40ns受控高压侧MOSFET的最小导通时间支持高转换比&#xff0c;实现从48V输入到低压轨的直接降压转换&#xff0c;降低了系统复杂性和解决方案成本。如果需要&#xff0c;在低至6V的输入电压下降期间&am…

C语言之文件操作(下)

C语言之文件操作&#xff08;下&#xff09; 文章目录 C语言之文件操作&#xff08;下&#xff09;1. 文件的顺序读写1.1 文件的顺序读写函数1.1.1 字符输入/输出函数&#xff08;fgetc/fputc&#xff09;1.1.2 ⽂本⾏输⼊/输出函数&#xff08;fgets/fputs&#xff09;1.1.3 格…

Spring Boot之自定义starter

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Spring Boot的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一. starter是什么 二.为什么要使…

大模型应用_PrivateGPT

https://github.com/imartinez/privateGPT 1 功能 整体功能&#xff0c;想解决什么问题 搭建完整的 RAG 系统&#xff0c;与 FastGPT相比&#xff0c;界面比较简单。但是底层支持比较丰富&#xff0c;可用于知识库的完全本地部署&#xff0c;包含大模型和向量库。适用于保密级…

SWPU NSS新生赛

&#x1f60b;大家好&#xff0c;我是YAy_17&#xff0c;是一枚爱好网安的小白&#xff0c;正在自学ing。 本人水平有限&#xff0c;欢迎各位大佬指点&#xff0c;一起学习&#x1f497;&#xff0c;一起进步⭐️。 ⭐️此后如竟没有炬火&#xff0c;我便是唯一的光。⭐️ 最近…

万界星空科技AI低代码云MES系统

在企业生产管理过程中&#xff0c;从市场、生产现场到产品交付&#xff0c;生产制造行业都面临着诸多挑战&#xff0c;比如&#xff1a; 订单排产难度大&#xff1a;订单混乱&#xff0c;常漏排产、错排产&#xff1b;产能不明晰&#xff0c;无法承诺交期&#xff0c;常丢单&a…

流程控制之条件判断

目录 流程控制之条件判断 2.1.if语句语法 2.1.1单分支结构 2.1.2双分支结构 2.1.3多分支结构 2.2.案例 例一: 例2: 例3: 例4: 例5: 例6: 例7: 例8: 例9: 2.3.case多条件判断 2.3.1.格式 2.3.2.执行过程 例10: 流程控制之条件判断 2.1.if语句语法 2.1.1单分…

ArcGIS for Android开发引入arcgis100.15.2

最后再点击同步即可&#xff01;&#xff01;&#xff01;

oracle aq java jms使用(数据类型为XMLTYPE)

记录一次冷门技术oracle aq的使用 版本 oracle 11g 创建用户 -- 创建用户 create user testaq identified by 123456; grant connect, resource to testaq;-- 创建aq所需要的权限 grant execute on dbms_aq to testaq; grant execute on dbms_aqadm to testaq; begindbms_a…

基于Spring Boot、Mybatis、Redis和Layui的企业电子招投标系统源码实现与立项流程

招投标管理系统是一款适用于招标代理、政府采购、企业采购和工程交易等领域的企业级应用平台。该平台以项目为主线&#xff0c;从项目立项到项目归档&#xff0c;实现了全流程的高效沟通和协作。通过该平台&#xff0c;用户可以实时共享项目数据信息&#xff0c;实现规范化管理…

【数据结构入门精讲 | 第一篇】打开数据结构之门

数据结构与算法是计算机科学中的核心概念&#xff0c;也与现实生活如算法岗息息相关。鉴于全网数据结构文章良莠不齐且集成度不高&#xff0c;故开设本专栏&#xff0c;为初学者提供指引。 目录 基本概念数据结构为何面世算法基本数据类型抽象数据类型使用抽象数据类型的好处 数…

微信小程序:模态框(弹窗)的实现

效果 wxml <!--新增&#xff08;点击按钮&#xff09;--> <image classimg src"{{add}}" bindtapadd_mode></image> <!-- 弹窗 --> <view class"modal" wx:if"{{showModal}}"><view class"modal-conten…

消息队列(MQ)

对于 MQ 来说&#xff0c;不管是 RocketMQ、Kafka 还是其他消息队列&#xff0c;它们的本质都是&#xff1a;一发一存一消费。下面我们以这个本质作为根&#xff0c;一起由浅入深地聊聊 MQ。 01 从 MQ 的本质说起 将 MQ 掰开了揉碎了来看&#xff0c;都是「一发一存一消费」&…

java实现冒泡排序及其动图演示

冒泡排序是一种简单的排序算法&#xff0c;它重复地遍历要排序的数列&#xff0c;一次比较两个元素&#xff0c;如果它们的顺序错误就把它们交换过来。重复这个过程直到整个数列都是按照从小到大的顺序排列。 具体步骤如下&#xff1a; 比较相邻的两个元素&#xff0c;如果前…

世界5G大会

会议名称:世界 5G 大会 时间:2023 年 12 月 5 日-12 月 8 日 地点:河南郑州 一、会议简介 世界 5G 大会,是由国务院批准,国家发展改革委、科技部、工 信部与地方政府共同主办,未来移动通信论坛联合属地主管厅局联合 承办,邀请全球友好伙伴共同打造的全球首个 5G 领域…

Spring Boot 3 整合 WebSocket (STOMP协议) 和 Vue 3 实现实时通信

&#x1f680; 作者主页&#xff1a; 有来技术 &#x1f525; 开源项目&#xff1a; youlai-mall &#x1f343; vue3-element-admin &#x1f343; youlai-boot &#x1f33a; 仓库主页&#xff1a; Gitee &#x1f4ab; Github &#x1f4ab; GitCode &#x1f496; 欢迎点赞…

家政服务小程序预约上门,让服务更便捷

随着人们生活节奏的加快&#xff0c;家政服务行业越来越受到人们的欢迎。为了满足市场需求&#xff0c;提高服务质量&#xff0c;家政公司需要开发一款预约上门的家政服务小程序。本文将详细介绍如何制作一个预约上门的家政服务小程序。 一、登录乔拓云网后台 首先&#xff0c…

基于vue实现的疫情数据可视化分析及预测系统-计算机毕业设计推荐django

目 录 摘 要 I ABSTRACT II 目 录 II 第1章 绪论 1 1.1背景及意义 1 1.2 国内外研究概况 1 1.3 研究的内容 1 第2章 相关技术 3 2.1 nodejs简介 4 2.2 express框架介绍 6 2.4 MySQL数据库 4 第3章 系统分析 5 3.1 需求分析 5 3.2 系统可行性分析 5 3.2.1技术可行性&#xff1a;…

Appium自动化常用adb操作封装

一、前置说明 在Appium自动化中&#xff0c;经常需要使用adb命令与设备进行交互&#xff0c;所以有必要把常用的adb操作封装成一个类 二、代码实现 import os import platform import re import subprocessfrom common import path from common.exception import AndroidSDK…