Java——LinkedList

1、链表

1.1 链表的概念及结构

链表在逻辑层面上是连续的，在物理层面上不一定是连续的

链表结构可分为，单向或双向、带头或不带头、循环或非循环，组合共计8种

重点：无头单向非循环链表、无头双向链表

1.2 模拟实现无头单向非循环链表

一个链表由若干节点组成，结合 内部类 知识，可将节点类定义在链表类中，成为内部类

public class MySingleLinkedList {static class ListNode {//该内部类中定义的是节点的属性public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//链表的头节点，定义在MySingleLinkedList类中}

下面以穷举的方式创建链表方便理解（真正创建链表并非如此）

//MySingleLinkedList类//该方法创建一个链表，头节点为node1，当该方法结束后，变量node1...都会销毁，只剩下头节点为head的链表public void createdList(){ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);ListNode node5 = new ListNode(5);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}

打印链表

//MySingleLinkedList 类public void display() {ListNode cur = head; //若直接使用head进行遍历打印，将只能打印一次，再次调用该函数，头节点就不在原来的位置了while(cur != null) { //注意！此处若写成 cur.next != null 则不会打印最后一个节点System.out.print(cur.val + " ");cur = cur.next;}}

求链表长度：

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

头插法：

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

尾插法：

    public void addLast(int data) {ListNode newNode = new ListNode(data);//不要忘记：判空！if(head == null) {head = newNode;return;}ListNode cur = head;while(cur.next != null) { //此处若写成 cur.next != null 则不会打印最后一个节点cur = cur.next;}cur.next = newNode;}

在index位置插入

// IndexNotLegalException 异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}// MySingleLinkedList 类public void addIndex(int index, int data) {//1、判断index合法性try{checkIndex(index);}catch(IndexNotLegalException e) {e.printStackTrace();}//2、index == 0 || index == size()if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//3、找到index的前一个位置ListNode cur = findIndexSubOne(index);//4、进行连接ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}private void checkIndex(int index) throws IndexNotLegalException{if(index < 0 || index > size()) {throw new IndexNotLegalException("index不合法！");}}private ListNode findIndexSubOne(int index) {int count = 0;ListNode cur = head;while(count < index-1) {cur = cur.next;count++;}return cur;}

查找关键字key是否包含在链表中

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

删除第一次出现关键字key的节点

    public void remove(int key) {//判空if(head == null) {return;}//若头节点为keywhile(head.val == key) {head = head.next;return;}ListNode cur = head;//遍历找到值为key的节点while(cur.next != null) {if(cur.next.val == key) {cur.next = cur.next.next;return;}cur = cur.next;}System.out.println("没有找到要删除的数字！");}

删除所有值为key的节点

    public void removeAllKey(int key) {//判空if (this.head == null) {return;}//快慢指针ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//处理头节点，当上述操作完成后，只剩下头节点没有判断//该方法优于一上来就判断头节点if(head.val == key) {head =head.next;}}

清空链表

    public void clear() {ListNode cur = head;while(cur != null) {ListNode curN = cur.next;cur.next = null;cur = curN;}head = null;}

1.3 模拟实现无头双向非循环链表

public class MyLinkedList {static class ListNode {public int data;public ListNode prev;//前驱节点public ListNode next;//后继节点public ListNode(int data){this.data = data;}}public ListNode head;//头节点public ListNode last;//尾节点//得到单链表的长度public int size(){int count = 0;ListNode cur = head;while(cur != null) {count++;cur = cur.next;}return count;}public void display(){ListNode cur = head;while(cur != null) {System.out.print(cur.data + " ");cur = cur.next;}System.out.println();}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while(cur != null) {if(cur.data == key) {return true;}cur = cur.next;}return false;}//头插法public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {head = last = node;}else {head.prev = node;node.next = head;head = node;}}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if(head == null) {head = last = node;}else {last.next = node;node.prev = last;last = node;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){try{checkIndex(index);}catch(IndexIllegalException e) {e.printStackTrace();}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode node = new ListNode(data);ListNode cur = findIndex(index);node.next = cur;node.prev = cur.prev;cur.prev.next = node;cur.prev = node;}private ListNode findIndex(int index) {ListNode cur = head;while(index != 0) {cur = cur.next;index--;}return cur;}private void checkIndex(int index) throws IndexIllegalException{if(index < 0 || index > size()) {throw new IndexIllegalException("双向链表index不合法！");}}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;while(cur != null) {if(cur.data == key) {if(cur == head) {head = head.next;if(head != null) {head.prev = null;}else {last = null;}}else if(cur == last) {cur.prev.next = null;last = cur.prev;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}return;}cur = cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur = head;while(cur != null) {if(cur.data == key) {if(cur == head) {head = head.next;if(head != null) {head.prev = null;}else {last = null;}}else if(cur == last) {cur.prev.next = null;last = cur.prev;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}}cur = cur.next;}}public void clear(){ListNode cur = head.next;while(cur != null) {cur = head.next;head.prev = null;head.next = null;head = cur;}head = last = null;}
}

链表遍历方式：

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);//直接sout打印System.out.println(list);System.out.println("======");//foreatch循环打印for(Integer x : list) {System.out.print(x + " ");}System.out.println();System.out.println("======");//for循环打印for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();System.out.println("======");//Iterator打印Iterator<Integer> it = list.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();System.out.println("======");//ListIterator可以倒着打印ListIterator<Integer> it3 = list.listIterator(list.size());while(it3.hasPrevious()) {System.out.print(it3.previous() + " ");}}

运行结果：

2、ArrayList 和 LinkedList 的区别

不同点ArrayListLinkedList
存储空间上逻辑&物理均连续逻辑上连续，物理上不一定连续
随机访问支持，时间复杂度为O(1)不支持，时间复杂度为O(N)
头插需要搬运元素，O(N)只需修改引用的指向，O(1)
插入空间不够时需要扩容没有容量概念
应用场景元素高效存储+频繁访问频繁在任意位置插入删除操作

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

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

相关文章

【代码随想录】【算法训练营】【第35天】[134]加油站 [135]分发糖果 [860]柠檬水找零 [406]根据身高重建队列

【代码随想录】【算法训练营】【第35天】[134]加油站 [135]分发糖果 [860]柠檬水找零 [406]根据身高重建队列

前言 思路及算法思维&#xff0c;指路 代码随想录。 题目来自 LeetCode。 day 35&#xff0c;连休两天~ 题目详情 [134] 加油站 题目描述 134 加油站 解题思路 前提&#xff1a;数组 思路&#xff1a;全局贪心算法&#xff1a;最小累加剩余汽油为负数&#xff0c;说明…
阅读更多...
面向对象编程重载

面向对象编程重载

系列文章目录 文章目录 系列文章目录前言一、重载&#xff08;overload&#xff09; 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了…
阅读更多...
【C++】C++参考手册 网址

【C++】C++参考手册 网址

C参考手册
阅读更多...
Antd 自定义列表全选功能

Antd 自定义列表全选功能

背景 需要为List组件自定义全选功能&#xff0c;如下图所示&#xff1a; 全选checkbox需要与下面每一项的checkbox联动&#xff1b;当从第一页翻页到第二页的时候&#xff0c;第一页已选的内容保持&#xff0c;可以对第二页勾选&#xff0c;同时保证全选checkbox的状态是正确的…
阅读更多...
在自己的电脑上搭建我的世界Java版服务器

在自己的电脑上搭建我的世界Java版服务器

很多朋友&#xff0c;喜欢玩Minecraft&#xff0c;也希望搭建一个服务器&#xff0c;用于和小伙伴联机&#xff1b; 并且&#xff0c;拥有服务器后&#xff0c;即使所有玩家都下线&#xff0c;“世界”依旧在运行&#xff0c;玩家可以随时参与其中&#xff0c;说不定一上线&am…
阅读更多...
【Da-SimaRPN】《Distractor-aware Siamese Networks for Visual Object Tracking》

【Da-SimaRPN】《Distractor-aware Siamese Networks for Visual Object Tracking》

ECCV-2018 中科大 文章目录 1 Background and Motivation2 Related Work3 Advantages / Contributions4 Method4.1 Features and Drawbacks in Traditional Siamese Networks4.2 Distractor-aware Training4.3 Distractor-aware Incremental Learning4.4 DaSiamRPN for Long-t…
阅读更多...
mmap引起的内存泄漏分析

mmap引起的内存泄漏分析

最近遇到一个内存泄漏问题&#xff0c;由于问题出现在客户端&#xff0c;只能通过客户提供的Log来分析。 根据客户提供的/proc/meminfo数据发现&#xff0c;MemAvailable 由294072kB减小至18128kB&#xff0c;减小约269MB&#xff0c;引起该变化的最直接原因是PageTables由614…
阅读更多...
49.Chome浏览器有三种清缓存方式

49.Chome浏览器有三种清缓存方式

49.Chome浏览器有三种清缓存方式&#xff1a;正常重新加载、硬件重新加载、清空缓存并硬性重新加载 1、【正常重新加载】 触发方式&#xff1a;①F5　　②CtrlR　　③在地址栏上回车　　④点击链接 如果缓存不过期会使用缓存。这样浏览器可以避免重新下载JavaScript文件、图像、…
阅读更多...
kettle从入门到精通 第六十九课 ETL之kettle kettle cdc mysql，轻松实现增量同步

kettle从入门到精通 第六十九课 ETL之kettle kettle cdc mysql，轻松实现增量同步

1、之前kettle cdc mysql的时候使用的方案是canalkafkakettle&#xff0c;今天我们一起学习下使用kettle的插件Debezium直接cdc mysql。 注&#xff1a;CDC (Change Data Capture) 是一种技术&#xff0c;用于捕获和同步数据库中的更改。 1&#xff09;Debezium步骤解析mysql b…
阅读更多...
反贿赂管理体系认证：提升企业诚信与防范风险的双重利器

反贿赂管理体系认证：提升企业诚信与防范风险的双重利器

反贿赂管理体系认证在当今商业环境中发挥着至关重要的作用。这一认证不仅有助于提高企业的道德标准和社会责任感&#xff0c;还能有效防范商业风险&#xff0c;并提升内部管理水平和工作效率。 反贿赂管理体系认证要求企业制定和执行严格的反贿赂政策和程序&#xff0c;从而在…
阅读更多...
计算机网络原理实验（7）：分析IP报文结构

计算机网络原理实验（7）：分析IP报文结构

一、实验名称 分析IP报文结构 二、实验目的&#xff1a; 1.掌握使用Wireshark分析俘获trace文件的基本技能&#xff1b; 2.深刻理解IP报文结构和工作原理。 三、实验内容和要求 1.分析俘获的分组&#xff1b; 2.分析IP报文结构。 3.记录每一字段的值&#xff0c;分析它的作…
阅读更多...
FL Studio（FL 21）软件下载-详细安装教程视频

FL Studio（FL 21）软件下载-详细安装教程视频

​fl studio 编曲软件即,简称FL,是音乐人熟知的水果编曲软件.可以完成完整的音乐制作环境或数字音频工作站(DAW)就是大家熟悉的水果 编曲软件&#xff0c;一个全能的音乐制作软件&#xff0c;包括编曲、录音、剪辑和混音等诸多功能&#xff0c;让你的电脑编程一个全能的录音室。…
阅读更多...
基坑监测：关键环节与深入剖析，保障施工安全与质量新标准

基坑监测：关键环节与深入剖析，保障施工安全与质量新标准

在建筑工程中&#xff0c;基坑监测是一项至关重要的工作&#xff0c;它涉及对基坑施工现场的实时监测数据进行分析和评估&#xff0c;以确保基坑施工活动的稳定、安全和高效进行。基坑监测涵盖地质勘探、基坑开挖、加固、支护、周边环境以及工程质量验收等多个环节&#xff0c;…
阅读更多...
通信原理抽样定理和PAM调制解调硬件实验

通信原理抽样定理和PAM调制解调硬件实验

一、实验目的 1. 加深理解抽样定理&#xff1b; 2. 加深理解脉冲幅度调制的原理。 二、实验内容 1. 观测PAM平顶抽样波形&#xff1b; 2. 观测PAM自然抽样波形及解码后波形。 三、实验器材 1. 双踪示波器&#xff1b; 2. 通信原理实验箱信号源模块、①号模块。 四、实…
阅读更多...
文章解读与仿真程序复现思路——电工技术学报EI\CSCD\北大核心《基于广义目标级联法的多牵引变电站 光伏-储能协同规划配置》

文章解读与仿真程序复现思路——电工技术学报EI\CSCD\北大核心《基于广义目标级联法的多牵引变电站 光伏-储能协同规划配置》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…
阅读更多...
java写一个验证码

java写一个验证码

生成验证码 内容&#xff1a;可以是小写字母&#xff0c;也可以是大写字母&#xff0c;还可以是数字 规则 长度为5 内容中是四位字母&#xff0c;1位数字。 其中数字只有1位&#xff0c;但是可以出现在任意的位置。 package User;import java.util.ArrayList; import jav…
阅读更多...
FlashDB的TS数据库的标准ANSI C移植验证

FlashDB的TS数据库的标准ANSI C移植验证

本文目录 1、引言2、环境准备3、修改驱动4、验证 文章对应视频教程&#xff1a; 暂无&#xff0c;可以关注我的B站账号等待更新。 点击图片或链接访问我的B站主页~~~ 1、引言 在当今数据驱动的时代&#xff0c;高效可靠的数据存储与管理对于嵌入式系统及物联网(IoT)应用至关重…
阅读更多...
【Unity每日一记】FairyGUI为什么能自动生成代码，它的好处是什么

【Unity每日一记】FairyGUI为什么能自动生成代码，它的好处是什么

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;uni…
阅读更多...
kali中安装zsteg教程

kali中安装zsteg教程

1、下载文件 git clone http://www.github.com/zed-0xff/zsteg 2、第一步需要保证虚拟机是有网络的&#xff0c;不然无法克隆 3、可以将网络设置成如下后重启&#xff0c;访问百度看看能不能访问&#xff0c;若可以访问&#xff0c;则进行下一步 4、查看源&#xff0c;删除源&…
阅读更多...
OpenAI把GPT-4原始版给了他们：研究不微调只靠提示词能走多远

OpenAI把GPT-4原始版给了他们：研究不微调只靠提示词能走多远

除了OpenAI自己&#xff0c;居然还有别人能用上GPT-4-Base版&#xff1f;&#xff1f; 也就是未经微调的预训练版&#xff0c;还不会对话聊天&#xff0c;只会补全句子的模型。 EPFL&#xff08;瑞士洛桑联邦理工&#xff09;团队申请到了访问权限&#xff0c;用于研究**“上…
阅读更多...
最新文章

Copyright @ 2022~2023