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.rhkb.cn/news/351561.html

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

相关文章

梯度提升决策树（GBDT）

梯度提升决策树（GBDT）

GBDT&#xff08;Gradient Boosting Decision Tree&#xff09;&#xff0c;全名叫梯度提升决策树&#xff0c;是一种迭代的决策树算法&#xff0c;又叫 MART&#xff08;Multiple Additive Regression Tree&#xff09;&#xff0c;它通过构造一组弱的学习器&#xff08;树&am…
阅读更多...
OpenCV绘制直线

OpenCV绘制直线

一 绘制图形 画线 画矩形 画圆 画椭圆 画多边形 绘制字体 二 画线 line(img,开始点&#xff0c;结束点&#xff0c;颜色…) 参数结束 img&#xff1a;在那个图像上画线 开始点,结束点&#xff1a;指定线的开始与结束位置&#xff1b; 颜色&#xff0c;线宽&#xff0c;线体…
阅读更多...
图解 Twitter 架构图

图解 Twitter 架构图

写在前面 两年前&#xff0c;马老板收购了twitter&#xff0c;并且做了一系列的大动作。那么今天我们来看一下这个全球最火的软件之一的架构。 Twitter解析 开始之前&#xff0c;我先提前说明一下&#xff0c;我之前不是做搜推广的&#xff0c;所以对这些了解不是很深&…
阅读更多...
力扣 SQL题目

力扣 SQL题目

185.部门工资前三高的所有员工 公司的主管们感兴趣的是公司每个部门中谁赚的钱最多。一个部门的 高收入者 是指一个员工的工资在该部门的 不同 工资中 排名前三 。 编写解决方案&#xff0c;找出每个部门中 收入高的员工 。 以 任意顺序 返回结果表。 返回结果格式如下所示。 …
阅读更多...
CSS 字体颜色渐变

CSS 字体颜色渐变

CSS 字体颜色渐变 css 代码: 注意&#xff1a;background: linear-gradient&#xff08;属性&#xff09;&#xff0c;属性可以调整方向 例如&#xff1a;to bottom 上下结构&#xff0c;to right 左右结构font-family: DIN, DIN;font-weight: normal;font-size: 22px;color:…
阅读更多...
基于WPF技术的换热站智能监控系统09--封装水泵对象

基于WPF技术的换热站智能监控系统09--封装水泵对象

1、添加用户控件 2、编写水泵UI 控件中用到了Viewbox控件&#xff0c;Viewbox控件是WPF中一个简单的缩放工具&#xff0c;它可以帮助你放大或缩小单个元素&#xff0c;同时保持其宽高比。通过样式和属性设置&#xff0c;你可以创建出既美观又功能丰富的用户界面。在实际开发中…
阅读更多...
uniapp原生插件开发实战——集成Android端的Twitter登陆

uniapp原生插件开发实战——集成Android端的Twitter登陆

Android集成Twitter登陆的官方教程：https://github.com/twitter-archive/twitter-kit-android/wiki 项目创建 首先可以先看下uniapp原生插件开发教程 uniapp原生插件类型分为两种： Module模式：能力扩展，无嵌入窗体的UI控件，类似于功能插件。Component模式：在窗体中内嵌…
阅读更多...
【2024亲测无坑】Oracle--19C在Centos7上的静默安装（rpm版）

【2024亲测无坑】Oracle--19C在Centos7上的静默安装（rpm版）

一、Oracle 19c Linux安装&#xff08;Centos 7&#xff09; 1.查看磁盘可用空间及配置ip地址 [rootlocalhost /]# df -h 文件系统 容量 已用 可用 已用% 挂载点 devtmpfs 1.4G 0 1.4G 0% /dev tmpfs 1.4G …
阅读更多...
C#——值类型和引用类型的区别详情

C#——值类型和引用类型的区别详情

值类型和引用类型的区别 值类型 值类型&#xff1a; 常用的基本数据类型都是值类型&#xff1a;bool 、char、int、 double、 float、long 、 byte 、ulong、uint、枚举类型、 结构体类型等特点: 在赋值的过程当中&#xff0c;把值的本身赋值给另一个变量&#xff0c;再修改…
阅读更多...
【python】OpenCV—Histogram Matching（9.2）

【python】OpenCV—Histogram Matching（9.2）

学习来自OpenCV基础&#xff08;17&#xff09;基于OpenCV、scikit-image和Python的直方图匹配 文章目录 直方图匹配介绍scikit-image 中的直方图匹配小试牛刀风格迁移 直方图匹配介绍 直方图匹配&#xff08;Histogram Matching&#xff09;是一种图像处理技术&#xff0c;旨…
阅读更多...
【图论应用】使用多路图（multigraph）对上海地铁站点图建模，并解决最短路径问题

【图论应用】使用多路图（multigraph）对上海地铁站点图建模，并解决最短路径问题

文章目录 1 前言2 导包导入数据集3 创建多路图&#xff0c;导入节点和边信息3 绘制线路图4 计算最短路径 1 前言 最近正在学习图神经网络&#xff0c;先pick up了一些最基础的图论知识并学习了一些好玩的应用。 本文启发于B站视频&#xff08;BV1LY411R7HJ&#xff09;&#…
阅读更多...
经验分享，如何去除文本中的空格

经验分享，如何去除文本中的空格

有时候我们需要去掉一窜文本中的空格&#xff0c;这里分享一个好用的免费网站&#xff0c;可实现在线去除 网址&#xff1a;http://www.txttool.com/t/?idMzM4 使用截图&#xff1a;
阅读更多...
redis 笔记2之哨兵

redis 笔记2之哨兵

文章目录 一、哨兵1.1 简介1.2 实操1.2.1 sentinel.conf1.2.2 问题1.2.3 哨兵执行流程和选举原理1.2.4 使用建议 一、哨兵 1.1 简介 上篇说了复制&#xff0c;有个缺点就是主机宕机之后&#xff0c;从机只会原地待命&#xff0c;并不能升级为主机&#xff0c;这就不能保证对外…
阅读更多...
牛客网华为机试java版

牛客网华为机试java版

目录 HJ1 字符串最后一个单词的长度HJ2 计算某字符出现次数HJ3 明明的随机数HJ4 字符串分隔HJ5 进制转换HJ6 质数因子HJ7 取近似值HJ8 合并表记录HJ9 提取不重复的整数HJ26 字符串排序HJ80 整型数组合并HJ101 输入整型数组和排序标识&#xff0c;对其元素按照升序或降序进行排序…
阅读更多...
困惑度作为nlp指标的理解示例

困惑度作为nlp指标的理解示例

为了更清晰地说明困惑度的计算过程以及如何通过困惑度判断模型的优劣&#xff0c;我们可以通过一个简单的例子来演示。假设我们有一个非常简单的文本语料库和两个基础的语言模型进行比较。 示例文本 假设我们的文本数据包括以下两个句子&#xff1a; “cat sits on the mat”…
阅读更多...
贷款投资决策和常用财务函数

贷款投资决策和常用财务函数

前段时间上了一门excel操作的课&#xff0c;本文结合其中介绍财务函数以及投资决策分析相关的部分&#xff0c;对贷款中的现金流计算进行深入的分析。 以等额本息产品为例进行实操计算&#xff0c;假设某产品本金12000元&#xff0c;期限12&#xff0c;IRR利率24%。每期还款113…
阅读更多...
VScode中连接并使用docker容器

VScode中连接并使用docker容器

前提条件&#xff1a; 1.在windows下安装Docker Desktop(方法可见下面的教程) Docker Desktop 安装使用教程-CSDN博客 2.在vscode安装3个必备的插件 3.先在ubuntu中把docker构建然后运行 4.打开vscode&#xff0c;按下图顺序操作 调试好之后上传到git上&#xff0c;然后后面…
阅读更多...
实验12 路由重分布

实验12 路由重分布

实验12 路由重分布 一、 原理描述二、 实验目的三、 实验内容四、 实验配置五、 实验步骤 一、 原理描述 在大型网络的组建过程中&#xff0c;隶属不同机构的网络部分往往会根据自身的实际情况来选用路由协议。例如&#xff0c;有些网络规模很小&#xff0c;为了管理简单&…
阅读更多...
《大数据分析》期末考试整理

《大数据分析》期末考试整理

一、单项选择题&#xff08;1*9&#xff09; 1.大数据发展历程&#xff1a;出现阶段、热门阶段和应用阶段 P2 2.大数据影响 P3 1&#xff09;大数据对科学活动的影响 2&#xff09;大数据对思维方式的影响 3&#xff09;大数据对社会发展的影响 4&#xff09;大数…
阅读更多...
华为云EI生态

华为云EI生态

1、人工智能技术趋势 2、华为AI发展思路 3、华为云EI&#xff1a;让企业更智能 4、华为云服务全景图 5、基础平台类服务 6、MLS:解决特性到模型应用的完整过程 7.DLS 8.GES超大规模一体化图分析与查询 9、EI视觉认知 10、EI语音语义 11、OCR&#xff1a;提供高精度光学文字自动…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023