【数据结构】链表与LinkedList
作者主页:paper jie 的博客
本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。
本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。
其他专栏:《算法详解》《C语言》《javaSE》等
内容分享:本期将会分享数据结构中的链表知识
目录
链表
链表的概念与结构
单向链表的模拟实现
具体实现代码
MyLinkedList
indexillgality
LinkedList
LinkedList的模拟实现
MyLinkedList
Indexexception
java中的LinkedList
LinkedList的使用
LinkedList的多种遍历
ArrayList与LinkedList的区别
链表
链表的概念与结构
链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。大家可以把它理解为现实中的绿皮火车
这里要注意:
链式在逻辑上是连续的,但是在物理上不一定是连续的
现实中的结点一般都是从堆上申请出来的
从堆上申请的空间,是按照一定的策略来分配的,所以两次申请的空间可能连续,也可能不连续
链表中的结构是多样的,根据情况来使用,一般使用一下结构:
单向或双向
带头和不带头
循环和非循环
这些结构中,我们需要重点掌握两种:
无头单向非循环链表:结构简单,一般不会单独来存数据,实际上更多的是作为其他数据结构的子结构,如哈希桶,图的邻接表等。
无头双向链表:在我们java的集合框架中LinkedList低层实现的就是无头双向循环链表。
单向链表的模拟实现
下面是单向链表需要实现的一些基本功能:
// 1、无头单向非循环链表实现
public class SingleLinkedList {
//头插法
public void addFirst(int data){
}
//尾插法
public void addLast(int data){
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
}
//删除所有值为key的节点
public void removeAllKey(int key){
}
//得到单链表的长度
public int size(){
return -1;
}
public void clear() {
}
public void display() {}
}
具体实现代码
MyLinkedList
package myLinkedList;import sun.awt.image.ImageWatched;import java.util.List;/*** Created with IntelliJ IDEA.* Description:* User: sun杰* Date: 2023-09-14* Time: 10:38*/
public class MyLinkedList implements IList{static class LinkNode {public int value;public LinkNode next;public LinkNode(int data) {this.value = data;}}LinkNode head;public void createNode() {LinkNode linkNode1 = new LinkNode(12);LinkNode linkNode2 = new LinkNode(23);LinkNode linkNode3 = new LinkNode(34);LinkNode linkNode4 = new LinkNode(56);LinkNode linkNode5 = new LinkNode(78);linkNode1.next = linkNode2;linkNode2.next = linkNode3;linkNode3.next = linkNode4;linkNode4.next = linkNode5;this.head = linkNode1;}@Overridepublic void addFirst(int data) {//实例化一个节点LinkNode firstNode = new LinkNode(data);if(this.head == null) {this.head = firstNode;return;}//将原第一个对象的地址给新节点的next,也就是将head给新nextfirstNode.next = this.head;//将新的对象的地址给head头this.head = firstNode;}@Overridepublic void addLast(int data) {//实例化一个节点LinkNode lastNode = new LinkNode(data);//找到最后一个节点LinkNode cur = this.head;while(cur.next!= null) {cur = cur.next;}cur.next = lastNode;//将最后一个节点的next记录插入节点的地址}@Overridepublic void addIndex(int index, int data) throws indexillgality {if(index < 0 || index > size()) {throw new indexillgality("index不合法");}LinkNode linkNode = new LinkNode(data);if(this.head == null) {addFirst(data);return;}if(size() == index ) {addLast(data);return;}LinkNode cur = this.head;int count = 0;while(count != index - 1) {cur = cur.next;count++;}linkNode.next = cur.next;cur.next = linkNode;}@Overridepublic boolean contains(int key) {LinkNode cur = this.head;while(cur != null) {if(cur.value == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(this.head.value == key) {this.head = this.head.next;return ;}//找前驱LinkNode cur = findprev(key);//判断返回值if(cur != null) {//删除LinkNode del = cur.next;cur.next = del.next;//cur.next = cur.next.next;}}//找删除的前驱private LinkNode findprev(int key) {LinkNode cur = head;while(cur.next != null) {if(cur.next.value == key) {return cur;}cur = cur.next;}return null;}@Overridepublic void removeAllKey(int key) {if(size() == 0) {return ;}if(head.value == key) {head = head.next;}LinkNode cur = head.next;LinkNode prev = head;while(cur != null) {if(cur.value == key) {prev.next = cur.next;}prev = cur;cur = cur.next;}}@Overridepublic int size() {LinkNode cur = head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void display() {LinkNode x = head;while(x != null) {System.out.print(x.value + " ");x = x.next;}System.out.println();}@Overridepublic void clear() {LinkNode cur = head;while(cur != null) {LinkNode curNext = cur.next;cur.next = null;cur = curNext;}head = null;}
}
indexillgality
这时一个自定义异常
package myLinkedList;/*** Created with IntelliJ IDEA.* Description:* User: sun杰* Date: 2023-09-14* Time: 12:55*/
public class indexillgality extends RuntimeException {public indexillgality(String message) {super(message);}
}
LinkedList
LinkedList的模拟实现
这相当于无头双向链表的实现,下面是它需要的基本功能:
// 2、无头双向链表实现
public class MyLinkedList {
//头插法
public void addFirst(int data){ }
//尾插法
public void addLast(int data){}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){}
//删除第一次出现关键字为key的节点
public void remove(int key){}
//删除所有值为key的节点
public void removeAllKey(int key){}
//得到单链表的长度
public int size(){}
public void display(){}
public void clear(){}
}
MyLinkedList
package myLinkedList;import java.util.List;/*** Created with IntelliJ IDEA.* Description:* User: sun杰* Date: 2023-09-20* Time: 18:49*/
public class MyLinkedList implements IList {//单个节点public static class ListNode {private int val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;ListNode last;@Overridepublic void addFirst(int data) {ListNode cur = new ListNode(data);if(head == null) {cur.next = head;head = cur;last = cur;}else {cur.next = head;head.prev = cur;head = cur;}}@Overridepublic void addLast(int data) {ListNode cur = new ListNode(data);if(head == null) {head = cur;last = cur;} else {last.next = cur;cur.prev = last;last = cur;}}@Overridepublic void addIndex(int index, int data) throws Indexexception {ListNode cur = new ListNode(data);if(index < 0 || index > size()) {throw new Indexexception("下标越界");}//数组为空时if(head == null) {head = cur;last = cur;return ;}//数组只有一个节点的时候if(head.next == null || index == 0) {head.prev = cur;cur.next = head;head = cur;return;}if(index == size()) {last.next = cur;cur.prev = last;return ;}//找到对应下标的节点ListNode x = head;while(index != 0) {x = x.next;index--;}//头插法cur.next = x;cur.prev = x.prev;x.prev.next = cur;x.prev = cur;}@Overridepublic boolean contains(int key) {ListNode cur = head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(head == null) {return;}ListNode cur = head;while(cur != null) {if(cur.val == key) {if(cur.next == null && cur.prev == null) {head = null;last = null;return;}else if(cur.next == null){cur.prev.next = null;last = cur.prev;return;}else if(cur.prev == null) {head = cur.next;cur.next.prev = null;return ;}else {ListNode frone = cur.prev;ListNode curnext = cur.next;frone.next = curnext;curnext.prev = frone;return ;}}cur = cur.next;}}@Overridepublic void removeAllKey(int key) {if(head == null) {return;}ListNode cur = head;while(cur != null) {if(cur.val == key) {if(cur.next == null && cur.prev == null) {head = null;last = null;} else if(cur.next == null){cur.prev.next = null;last = cur.prev;}else if(cur.prev == null) {head = cur.next;cur.next.prev = null;}else {ListNode frone = cur.prev;ListNode curnext = cur.next;frone.next = curnext;curnext.prev = frone;}}cur = cur.next;}}@Overridepublic int size() {int count = 0;ListNode cur = head;while(cur != null) {count++;cur = cur.next;}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() {if(head == null) {return;}ListNode cur = head.next;while(cur != null) {head = null;head = cur;cur = cur.next;}head = null;}
}
Indexexception
这也是一个自定义异常
package myLinkedList;/*** Created with IntelliJ IDEA.* Description:* User: sun杰* Date: 2023-09-21* Time: 9:47*/
public class Indexexception extends RuntimeException{public Indexexception(String message) {super(message);}
}
java中的LinkedList
LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来。因为这样,在任意位置插入和删除元素时,是不需要搬移元素,效率比较高。
在集合框架中,LinkedList也实现了List接口:
注意:
LinkedList实现了List接口
LinkedList的底层使用的是双向链表
Linked没有实现RandomAccess接口,因此LinkedList不支持随机访问
LinkedList的随机位置插入和删除元素时效率较高,复杂度为O(1)
LinkedList比较适合任意位置插入的场景
LinkedList的使用
LinkedList的构造:
一般来说有两种方法:
无参构造:
List<Integer> list = new LinkedList<>();
使用其他集合容器中的元素构造List:
public LinkedList(Collection<? extends E> c)
栗子:
public static void main(String[] args) {
// 构造一个空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>();list2.add("JavaSE");list2.add("JavaWeb");list2.add("JavaEE");
// 使用ArrayList构造LinkedListList<String> list3 = new LinkedList<>(list2);}
LinkedList的基本方法:
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);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.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,否则返回false
if(!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位置的元素设置为elem
System.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());
}
LinkedList的多种遍历
foreach:
public static void main(String[] args) {List<Integer> list = new LinkedList<>();list.add(1);list.add(3);list.add(5);list.add(2);list.remove(1);for (int x:list) {System.out.print(x + " ");}}
使用迭代器遍历:
ListIterator<Integer> it = list.listIterator();while(it.hasNext()) {System.out.println(it.next() + " ");}}
ArrayList与LinkedList的区别
相关文章:
【数据结构】链表与LinkedList
作者主页:paper jie 的博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精…...
Flink RoaringBitmap去重
1、RoaringBitmap的依赖 <!-- 去重大哥--> <dependency><groupId>org.roaringbitmap</groupId><artifactId>RoaringBitmap</artifactId><version>0.9.21</version> </dependency> 2、Demo去重 package com.gwm.driver…...
Elasticsearch—(MacOs)
1⃣️环境准备 准备 Java 环境:终端输入 java -version 命令来确认版本是否符合 Elasticsearch 要求下载并解压 Elasticsearch:前往(https://www.elastic.co/downloads/elasticsearch)选择适合你的 Mac 系统的 Elasticsearch 版本…...
插入排序与希尔排序
个人主页:Lei宝啊 愿所有美好如期而遇 前言: 这两个排序在思路上有些相似,所以有人觉得插入排序和希尔排序差别不大,事实上,他们之间的差别不小,插入排序只是希尔排序的最后一步。 目录 前言:…...
C# OpenCvSharp 基于直线检测的文本图像倾斜校正
效果 项目 代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using OpenCvSharp;namespace OpenCvSharp_基于直线检测的文…...
“智慧时代的引领者:探索人工智能的无限可能性“
目录 一.背景 二.应用 2.1金融领域 2.2医疗领域 2.3教育领域 三.发展 四.总结: 一.背景 人工智能(Artificial Intelligence,简称AI),是指通过计算机程序模拟人类智能的一种技术。它是计算机科学、工程学、语言学、哲学等多…...
PMSM——转子位置估算基于QPLL
文章目录 前言仿真模型观测器速度观测位置观测转矩波形电流波形 前言 今后是电机控制方向的研究生的啦,期待有同行互相交流。 仿真模型 观测器 速度观测 位置观测 转矩波形 电流波形...
Android Studio之Gradle和Gradle插件的区别
解释的很详细 Android Studio之Gradle和Gradle插件的区别...
DataExcel控件读取和保存excel xlsx 格式文件
需要引用NPOI库 https://github.com/dotnetcore/NPOI 调用Read 函数将excel读取到dataexcel控件 调用Save 函数将dataexcel控件文件保存为excel文件 using NPOI.HSSF.UserModel; using NPOI.HSSF.Util; using NPOI.SS.UserModel; using NPOI.SS.Util; using System; using …...
【JavaEE】CAS(Compare And Swap)操作
文章目录 什么是 CASCAS 的应用如何使用 CAS 操作实现自旋锁CAS 的 ABA 问题CAS 相关面试题 什么是 CAS CAS(Compare and Swap)是一种原子操作,用于在无锁情况下保证数据一致性的问题。它包含三个操作数——内存位置、预期原值及更新值。在执…...
第三章:最新版零基础学习 PYTHON 教程(第三节 - Python 运算符—Python 中的关系运算符)
关系运算符用于比较值。它根据条件返回 True 或 False。这些运算符也称为比较运算符。 操作员描述 句法> 大于:如果左操作数大于右操作数,则为 Truex > y...
【GDB】使用 GDB 自动画红黑树
阅读本文前需要的基础知识 用 python 扩展 gdb python 绘制 graphviz 使用 GDB 画红黑树 前面几节中介绍了 gdb 的 python 扩展,参考 用 python 扩展 gdb 并且 python 有 graphviz 模块,那么可以用 gdb 调用 python,在 python 中使用 grap…...
使用Vue3+elementPlus的Tree组件实现一个拖拽文件夹管理
文章目录 1、前言2、分析3、实现4、踩坑4.1、拖拽辅助线的坑4.2、数据的坑4.3、限制拖拽4.4、样式调整 1、前言 最近在做一个文件夹管理的功能,要实现一个树状的文件夹面板。里面包含两种元素,文件夹以及文件。交互要求如下: 创建、删除&am…...
小谈设计模式(7)—装饰模式
小谈设计模式(7)—装饰模式 专栏介绍专栏地址专栏介绍 装饰模式装饰模式角色Component(抽象组件)ConcreteComponent(具体组件)Decorator(抽象装饰器)ConcreteDecorator(具…...
nginx 多层代理 + k8s ingress 后端服务获取客户真实ip 配置
1.nginx http 七层代理 修改命令空间: namespace: nginx-ingress : configmap:nginx-configuration kubectl get cm nginx-configuration -n ingress-nginx -o yaml添加如上配置 compute-full-forwarded-for: “true” forwarded-for-header: X-Forwa…...
6种最常用的3D点云语义分割AI模型对比
由于增强现实/虚拟现实的发展及其在计算机视觉、自动驾驶和机器人领域的广泛应用,点云学习最近引起了人们的关注。 深度学习已成功用于解决 2D 视觉问题,然而,由于其处理面临独特的挑战,深度学习技术在点云上的使用仍处于起步阶段…...
UG NX二次开发(C#)-获取UI中选择对象的handle值
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1、前言2、设计一个简单的UI界面3、创建工程项目4、测试结果1、前言 我在哔哩哔哩的视频中看到有人问我如何获取UI选择对象的Handle,本来想把Tag、Taggedobject、Handle三者的关系讲一下,然后看…...
win10,WSL的Ubuntu配python3.7手记
1.装linux 先在windows上安装WSL版本的Ubuntu Windows10系统安装Ubuntu子系统_哔哩哔哩_bilibili (WSL2什么的一直没搞清楚) 图形界面会出一些问题,注意勾选ccsm出的界面设置 win10安装Ubuntu16.04子系统,并开启桌面环境_win…...
02-Zookeeper实战
上一篇:01-Zookeeper特性与节点数据类型详解 1. zookeeper安装 Step1: 配置JAVA环境,检验环境: java -versionStep2: 下载解压 zookeeper wget https://mirror.bit.edu.cn/apache/zookeeper/zookeeper-3.5.8/apache-zookeepe…...
【C语言深入理解指针(1)】
1.内存和地址 1.1内存 在讲内存和地址之前,我们想有个⽣活中的案例: 假设有⼀栋宿舍楼,把你放在楼⾥,楼上有100个房间,但是房间没有编号,你的⼀个朋友来找你玩,如果想找到你,就得挨…...
模拟实现简单的通讯录
前言:生活中处处都会看到或是用到通讯录,今天我们就通过C语言来简单的模拟实现一下通讯录。 鸡汤:跨越山海,终见曙光! 链接:gitee仓库:代码链接 目录 主函数声明部分初始化通讯录实现扩容的函数增加通讯录所…...
rabbitMQ死信队列快速编写记录
文章目录 1.介绍1.1 什么是死信队列1.2 死信队列有什么用 2. 如何编码2.1 架构分析2.2 maven坐标2.3 工具类编写2.4 consumer1编写2.5 consumer2编写2.6 producer编写 3.整合springboot3.1 架构图3.2 maven坐标3.3 构建配置类,创建exchange,queue&#x…...
数位dp,338. 计数问题
338. 计数问题 - AcWing题库 给定两个整数 a 和 b,求 a 和 b 之间的所有数字中 0∼90∼9 的出现次数。 例如,a1024,b1032,则 a 和 b 之间共有 9 个数如下: 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出…...
如何解决git clone http/https仓库失败(403错误)
本来不打算写这篇文章,但是后来又遇到这个问题忘了之前是怎么解决的了。 一般情况下,个人使用 GitHub 等平台时是使用 SSH 协议的,这样不光方便管理可访问用户,也保证了安全性。但是 GitHub 上仓库的 SSH 地址是要登陆才能看到&a…...
华为云云耀云服务器L实例评测 | 实例评测使用之硬件性能评测:华为云云耀云服务器下的硬件运行评测
华为云云耀云服务器L实例评测 | 实例评测使用之硬件性能评测:华为云云耀云服务器下的硬件运行评测 介绍华为云云耀云服务器 华为云云耀云服务器 (目前已经全新升级为 华为云云耀云服务器L实例) 华为云云耀云服务器是什么华为云云耀…...
Elasticsearch:使用 Elasticsearch 进行语义搜索
在数字时代,搜索引擎在通过浏览互联网上的大量可用信息来检索数据方面发挥着重要作用。 此方法涉及用户在搜索栏中输入特定术语或短语,期望搜索引擎返回与这些确切关键字匹配的结果。 虽然关键字搜索对于简化信息检索非常有价值,但它也有其局…...
JVM的主要组成及其作用
jvm主要组成部分有: 类加载器、运行时数据区 (内存结构)、执行引擎、本地接口库、垃圾回收机制 Java程序运行的时候,首先会通过类加载器把Java 代码转换成字节码。然后运行时数据区再将字节码加载到内存中,但字节码文件只是JVM 的一套指令集规范…...
会议AISTATS(Artificial Intelligence and Statistics) Latex模板参考文献引用问题
前言 在看AISTATS2024模板的时候,发现模板里面根本没有教怎么引用,要被气死了。 如下,引用(Cheesman, 1985)的时候,模板是自己手打上去的?而且模板提供的那三个引用,根本也没有Cheesman这个人,…...
2023最新外贸建站:WordPress搭建外贸独立站零基础小白保姆级教程
想从零开始建立一个外贸自建站,那么你来对地方了。 如果你还在找外贸建站或者是WordPress建站教程,不妨看看这篇文章,本教程涵盖了2023最新的外贸建站教程,你将学会使用WordPress自建外贸独立站,步骤包括购买域名主机…...
HTTP请求交互基础(基于GPT3.5,持续更新)
HTTP交互基础 目的HTTP定义详解HTTP协议(规范)1. 主要组成部分1.1 请求行(Request Line):包含请求方法、请求URI(Uniform Resource Identifier)和HTTP协议版本。1.2 请求头部(Reques…...
网站 ip pv/seo查询seo优化
from keras.datasets import cifar10(x_train, y_train), (x_test, y_test) cifar10.load_data()# 如果不处理的话,每张图的每个通道都是 (0-255) 之间的取值 x_train[0]array([[[ 59, 62, 63],[ 43, 46, 45],[ 50, 48, 43],...,[158, 132, 108],[152, 125, …...
专门做钣金的网站/温州高端网站建设
我需要合并/加入包含数组的多个json字符串(也需要合并),但是我不知道实现此目的的最佳方法是什么:JSON字符串的初始数组(在下面的示例中称为$ rrDatas):Array([0] > {"asset":[1],"person":[1]}[1] > {"asset…...
怎么用视频做网站背景/品牌网络推广外包
一、精灵创建及初始化 1、从图片文件创建: CCSprite *sprite [CCSprite spriteWithFile:"ImageFileName.png"]; 默认锚点 ccp(0.5,0.5), 默认位置 ccp(0,0), CCSprite尺寸(contentSize)为图片尺寸 2、从帧缓存创建: [[CCSpriteFrameCache sh…...
专属头像制作素材图片/seo关键词优化外包公司
Visual Studio 11,具备 并行模式库和 代理库、 更轻松地开发多核处理器上运行的并行代码。 这些库的主要范例是根据任务 和并发运行库,自定义的调度程序 进行处理的。到目前为止,处理任务的的概念原型,就使用task_handle ●类型 如…...
pc网站转换成微网站/百度seo推广怎么做
多态性 (polymorphism) 是面向对象编程的基本特征之一。而在 C 中,多态性通过虚函数 (virtual function) 来实现。我们来看一段简单的代码: #include <iostream>using namespace std;class Base{int a;public:virtual void fun1() { co…...