【数据结构】链表与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.rhkb.cn/news/148216.html

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

相关文章

Ubuntu中启动HDFS后没有NameNode解决办法

关闭进程&#xff1a; stop-dfs.sh 格式化&#xff1a; hadoop namenode -format 出现报错信息&#xff1a; 23/10/03 22:27:04 WARN fs.FileUtil: Failed to delete file or dir [/usr/data/hadoop/tmp/dfs/name/current/fsimage_0000000000000000000.md5]: it still exi…

3种等待方式,让你学会Selenium设置自动化等待测试脚本!

一、Selenium脚本为什么要设置等待方式&#xff1f;——即他的应用背景到底是什么 应用Selenium时&#xff0c;浏览器加载过程中无法立即显示对应的页面元素从而无法进行元素操作&#xff0c;需设置一定的等待时间去等待元素的出现。&#xff08;简单来说&#xff0c;就是设置…

黑马mysql教程笔记(mysql8教程)基础篇——数据库相关概念、mysql安装及卸载、数据模型、SQL通用语法及分类(DDL、DML、DQL、DCL)

参考文章1&#xff1a;https://www.bilibili.com/video/BV1Kr4y1i7ru/ 参考文章2&#xff1a;https://dhc.pythonanywhere.com/article/public/1/ 文章目录 基础篇数据库相关概念&#xff08;数据库DataBase&#xff08;DB&#xff09;、数据库管理系统DataBase Management Sy…

正则表达式基本使用

文章目录 1. 基本介绍2. 元字符(Metacharacter)-转义号 \\3. 元字符-字符匹配符3.1 案例 4. 元字符-选择匹配符5. 元字符-限定符6. 元字符-定位符7. 分组7.1 捕获分组7.2 非捕获分组 8. 非贪婪匹配9. 应用实例10. 正则验证复杂URL 1. 基本介绍 如果要想灵活的运用正则表达式&a…

【算法学习】-【双指针】-【快乐数】

LeetCode原题链接&#xff1a;202. 快乐数 下面是题目描述&#xff1a; 「快乐数」 定义为&#xff1a; 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1&#xff0c;也可能是 无限循环 但始终变不到 1。 如果…

Linux:minishell

目录 1.实现逻辑 2.代码及效果展示 1.打印字符串提示用户输入指令 2.父进程拆解指令 3.子进程执行指令,父进程等待结果 4.效果 3.实现过程中遇到的问题 1.打印字符串的时候不显示 2.多换了一行 3.cd路径无效 4.优化 1.ll指令 2.给文件或目录加上颜色 代码链接 模…

Redis相关概念

1. 什么是Redis&#xff1f;它主要用来什么的&#xff1f; Redis&#xff0c;英文全称是Remote Dictionary Server&#xff08;远程字典服务&#xff09;&#xff0c;是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;并提…

IDT 一款自动化挖掘未授权访问漏洞的信息收集工具

IDT v1.0 IDT 意为 Interface detection&#xff08;接口探测) 项目地址: https://github.com/cikeroot/IDT/该工具主要的功能是对批量url或者接口进行存活探测&#xff0c;支持浏览器自动打开指定的url&#xff0c;避免手动重复打开网址。只需输入存在批量的url文件即可。 …

SpringBoot快速入门

搭建SpringBoot工程&#xff0c;定义hello方法&#xff0c;返回“Hello SpringBoot” ②导入springboot工程需要继承的父工程&#xff1b;以及web开发的起步依赖。 ③编写Controller ④引导类就是SpringBoot项目的一个入口。 写注解写main方法调用run方法 快速构建SpringBoo…

动态规划-状态机(188. 买卖股票的最佳时机 IV)

状态分类&#xff1a; f[i,j,0]考虑前i只股票&#xff0c;进行了j笔交易&#xff0c;目前未持有股票 所能获得最大利润 f[i,j,1]考虑前i只股票&#xff0c;进行了j笔交易&#xff0c;目前持有股票 所能获得最大利润 状态转移&#xff1a; f[i][j][0] Math.max(f[i-1][j][0],f[…

DevExpress WinForms图表组件 - 直观的数据信息呈现方式!(二)

在上文中&#xff08;点击这里回顾>>&#xff09;&#xff0c;我们为大家介绍了DevExpress WinForms图表控件的互动图表、图标设计器及可定制功能等&#xff0c;本文将继续介绍DevExpress WinForms图表控件的数据分析、大数据功能等&#xff0c;欢迎持续关注我们哦~ Dev…

力扣-350.两个数组的交集||

Idea 首先遍历第一个数组&#xff0c;用哈希表存储每个数字及其出现的次数。 然后遍历第二个数组&#xff0c;每出现重复的数字&#xff0c;并判断该数字在哈希表的次数是不是大于0&#xff0c;如果大于则存入答案数组&#xff0c;并将哈希表次数减1&#xff0c;直接遍历结束。…

pycharm中个人编程时常用到的快捷键

pycharm中个人编程时常用到的快捷键&#xff1a; 仅个人经验总结&#xff0c;不为其他&#xff01; 1.CTRLShiftAlt鼠标选择多个位置 可以同时在多个位置进行编辑同样的内容 2. Ctrel Alt L快速将代码格式标准化 3. Ctrl F 在当前py文件中查找 4. Ctrl R快速替换当前…

接口自动化中如何完成接口加密与解密?

加密是一种限制对网络上传输数据的访问权的技术。将密文还原为原始明文的过程称为解密&#xff0c;它是加密的反向处理。在接口开发中使用加密、解密技术&#xff0c;可以防止机密数据被泄露或篡改。在接口自动化测试过程中&#xff0c;如果要验证加密接口响应值正确性的话&…

JUC第十四讲:JUC锁: ReentrantReadWriteLock详解

JUC第十四讲&#xff1a;JUC锁: ReentrantReadWriteLock详解 本文是JUC第十四讲&#xff1a;JUC锁 - ReentrantReadWriteLock详解。ReentrantReadWriteLock表示可重入读写锁&#xff0c;ReentrantReadWriteLock中包含了两种锁&#xff0c;读锁ReadLock和写锁WriteLock&#xff…

C/C++字符函数和字符串函数详解————内存函数详解与模拟

个人主页&#xff1a;点我进入主页 专栏分类&#xff1a;C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 欢迎大家点赞&#xff0c;评论&#xff0c;收藏。 一起努力&#xff0c;一起奔赴大厂。 目录 1.前言 2 .memcpy函数 3.memmove函…

【Office】超简单,Excel快速完成不规则合并单元格排序

演示效果&#xff1a;将下图已经合并了的单元格按照单位名称排序并将同一个单位的数据合并在了一起。 Step 1&#xff1a;取消合并 选中所有的数据后&#xff0c;点击 “开始”-“合并单元格” &#xff0c;并且取消数据源的合并。 Step 2&#xff1a;填充数据 选中需要填…

【Go】go-es统计接口被刷数和ip访问来源

go-es模块统计日志中接口被刷数和ip访问来源 以下是使用go的web框架gin作为后端&#xff0c;展示的统计页面 背景 上面的数据来自elk日志统计。因为elk通过kibana进行展示&#xff0c;但是kibana有一定学习成本且不太能满足定制化的需求&#xff0c;所以考虑用编程的方式…

lv7 嵌入式开发-网络编程开发 07 TCP服务器实现

目录 1 函数介绍 1.1 socket函数 与 通信域 1.2 bind函数 与 通信结构体 1.3 listen函数 与 accept函数 2 TCP服务端代码实现 3 TCP客户端代码实现 4 代码优化 5 练习 1 函数介绍 其中read、write、close在IO中已经介绍过&#xff0c;只需了解socket、bind、listen、acc…

国庆假期day5

作业&#xff1a;请写出七层模型及每一层的功能&#xff0c;请绘制三次握手四次挥手的流程图 1.OSI七层模型&#xff1a; 应用层--------提供函 表示层--------表密缩 会话层--------会话 传输层--------进程的接收和发送 网络层--------寻主机 数据链路层----相邻节点的可靠传…