【数据结构】链表与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的区别

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

小程序编译器性能优化之路

小程序编译器性能优化之路

作者 | 马可 导读 小程序编译器是百度开发者工具中的编译构建模块&#xff0c;用来将小程序代码转换成运行时代码。旧版编译器由于业务发展&#xff0c;存在编译慢、内存占用高的问题&#xff0c;我们对编译器做了一次大规模的重构&#xff0c;采用自研架构&#xff0c;做了多线…
阅读更多...
链表经典面试题(一)

链表经典面试题(一)

面试题 1.反转链表的题目2.反转链表的图文分析3.反转链表的代码实现 1.反转链表的题目 2.反转链表的图文分析 我们在实现反转链表的时候,是将后面的元素变前面&#xff0c;前面的元素变后面&#xff0c;那么我们是否可以理解为&#xff0c;用头插法的思想来完成反转链表呢&…
阅读更多...
Cannot download sources：IDEA源码无法下载

Cannot download sources：IDEA源码无法下载

问题 Swagger的相关包&#xff0c;无法看到注释&#xff1b; 在class文件的页面&#xff0c;点击下载源码&#xff0c;源码下载不了&#xff0c;IDEA报下面的错误。 报错 Cannot download sources Sources not found for: io.swagger.core.v3:swagger-annotations:2.2.9 解决…
阅读更多...
读者写者问题—内含408真题

读者写者问题—内含408真题

读者写者问题—含408 一、问题描述 一个数据问价或记录可以被多个进程共享&#xff0c;我们把只读该文件的进程称为“读者进程”&#xff0c;其他进程为“写者进程”。允许多个进程同时读一个共享对象&#xff0c;但不允许一个写者进程和其他写者进程或读者进程同时访问共享对…
阅读更多...
点亮一个LED+LED闪烁+LED流水灯——“51单片机”

点亮一个LED+LED闪烁+LED流水灯——“51单片机”

各位CSDN的uu们好呀&#xff0c;这是小雅兰的最新专栏噢&#xff0c;最近小雅兰学习了51单片机的知识&#xff0c;所以就想迫不及待地分享出来呢&#xff01;&#xff01;&#xff01;下面&#xff0c;让我们进入51单片机的世界吧&#xff01;&#xff01;&#xff01; 点亮一个…
阅读更多...
Linux基础命令汇总

Linux基础命令汇总

用户管理 su 切换用户&#xff1a;su 用户名 logname 显示当前用户的登录用户名&#xff1a;logname useradd 创建用户&#xff1a;useradd 用户名创建用户时指定用户的主组&#xff1a;useradd -g 组名 用户名 usermod 添加附属组&#xff1a;usermod -G 组…
阅读更多...
2023年8月嵌入式项目开发专题总汇

2023年8月嵌入式项目开发专题总汇

一、前言 本文介绍基于嵌入式系统和C语言开发的系列项目。这些项目涵盖了多个领域&#xff0c;从自动化控制到游戏开发&#xff0c;从计算机网络到物联网应用。通过这些项目的开发过程&#xff0c;将深入探讨各种技术和解决方案&#xff0c;并分享相关经验和知识。 在本文中&…
阅读更多...
cesium 雷达扫描 （线行扩散效果）

cesium 雷达扫描 （线行扩散效果）

cesium 雷达扫描 （线行扩散效果） 1、实现方法 使用ellipse方法加载圆型，修改ellipse中material方法来实现效果 2、示例代码 2.1、 <!DOCTYPE html> <html lang="en"><head><<
阅读更多...
分类预测 | Matlab实现BES-ELM秃鹰搜索算法优化极限学习机分类预测

分类预测 | Matlab实现BES-ELM秃鹰搜索算法优化极限学习机分类预测

分类预测 | Matlab实现BES-ELM秃鹰搜索算法优化极限学习机分类预测 目录 分类预测 | Matlab实现BES-ELM秃鹰搜索算法优化极限学习机分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 Matlab实现BES-ELM秃鹰搜索算法优化极限学习机分类预测&#xff08;完整源码和数…
阅读更多...
【CVPR 2023】DSVT: Dynamic Sparse Voxel Transformer with Rotated Sets

【CVPR 2023】DSVT: Dynamic Sparse Voxel Transformer with Rotated Sets

文章目录 开场白效果意图 重点VoxelNet: End-to-End Learning for Point Cloud Based 3D Object DetectionX-Axis DSVT LayerY-Axis DSVT Layer Dynamic Sparse Window AttentionDynamic set partitionRotated set attention for intra-window feature propagation.Hybrid wind…
阅读更多...
优维低代码实践：应用级配置

优维低代码实践：应用级配置

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 优维…
阅读更多...
[NOIP2012 提高组] 开车旅行

[NOIP2012 提高组] 开车旅行

[NOIP2012 提高组] 开车旅行 题目描述 小 A \text{A} A 和小 B \text{B} B 决定利用假期外出旅行&#xff0c;他们将想去的城市从 $1 $ 到 n n n 编号&#xff0c;且编号较小的城市在编号较大的城市的西边&#xff0c;已知各个城市的海拔高度互不相同&#xff0c;记城市 …
阅读更多...
亚信科技AntDB数据库 高并发、低延迟、无死锁，深入了解AntDB-M元数据锁的实现

亚信科技AntDB数据库 高并发、低延迟、无死锁，深入了解AntDB-M元数据锁的实现

AntDB-M在架构上分为两层&#xff0c;服务层和存储引擎层。元数据的并发管理集中在服务层&#xff0c;数据的存储访问在存储引擎层。为了保证DDL操作与DML操作之间的一致性&#xff0c;引入了元数据锁&#xff08;MDL&#xff09;。 AntDB-M提供了丰富的元数据锁功能&#xff0…
阅读更多...
Koa处理请求数据

Koa处理请求数据

在开发中&#xff0c;后端接收到请求参数后&#xff0c;需要解析参数。请求分为很多种类型&#xff0c;比如常见的get和post。 请求参数 Koa本身可以解析get请求参数&#xff0c;不能解析post请求参数。例如&#xff1a; router.get(/api/get/userInfo, async (context) >…
阅读更多...
新手--安装好Quartus II13.0（带modelsim集成包）并用Quartus II搭建一个工程

新手--安装好Quartus II13.0（带modelsim集成包）并用Quartus II搭建一个工程

前言 今天是国庆节&#xff0c;我们正式来学习Quartus II13.0软件的安装与使用。学习verilog与学习C语言都是学习一门语言&#xff0c;那么学习一门语言&#xff0c;光看理论不敲代码绝对是学习不好的。要用verilog语言敲代码&#xff0c;就要像C语言那样搭建起语言的编译环境&…
阅读更多...
C语言 Cortex-A7核 IIC实验

C语言 Cortex-A7核 IIC实验

iic.h #ifndef __IIC_H__ #define __IIC_H__ #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_rcc.h" /* 通过程序模拟实现I2C总线的时序和协议* GPIOF ---> AHB4* I2C1_SCL ---> PF14* I2C1_SDA ---> PF15** */#define SET_SDA_OUT do{…
阅读更多...
B. Comparison String

B. Comparison String

题目&#xff1a; 样例&#xff1a; 输入 4 4 <<>> 4 >><< 5 >>>>> 7 <><><><输出 3 3 6 2 思路&#xff1a; 由题意&#xff0c;条件是 又因为要使用尽可能少的数字&#xff0c;这是一道贪心题&#xff0c;所以…
阅读更多...
Linux CentOS7 vim临时文件

Linux CentOS7 vim临时文件

在vim中&#xff0c;由于断网、停电、故意退出、不小心关闭终端等多种原因&#xff0c;正在编辑的文件没有保存&#xff0c;系统将会为文件保存一个交换文件&#xff0c;或称临时文件&#xff0c;或备份文件。 如果因某种原因产生了交换文件&#xff0c;每次打开文件时&#x…
阅读更多...
详解分布式搜索技术之elasticsearch

详解分布式搜索技术之elasticsearch

目录 一、初识elasticsearch 1.1什么是elasticsearch 1.2elasticsearch的发展 1.3为什么学习elasticsearch？ 1.4正向索引和倒排索引 1.4.1传统数据库采用正向索引 1.4.2elasticsearch采用倒排索引 1.4.3posting list ​1.4.4总结 1.5 es的一些概念 1.5.1文档和字段 …
阅读更多...
鞋类 整鞋试验方法 剥离强度

鞋类 整鞋试验方法 剥离强度

声明 本文是学习GB-T 3903.3-2011 鞋类 整鞋试验方法 剥离强度. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 GB/T 3903 的本部分规定了整鞋鞋底与鞋帮或外底与外中底之间剥离强度的试验方法。 本部分适用于采用模压、硫化、注塑、灌注、胶…
阅读更多...
最新文章

Copyright @ 2022~2023