【数据结构】LinkedList与链表

文章目录

  • 1. ArrayList的缺陷
  • 2. 链表
    • 2.1 链表的概念及结构
    • 2.2 链表的实现
      • 1.链表的功能
      • 2.初始化链表
      • 3.实现功能接口
        • 3.1头插添加元素
        • 3.2尾插法添加新元素
        • 3.3找到下标的前驱节点
        • 3.4指定位置插入元素
        • 3.5指定元素是否存在
        • 3.6找到指定元素的前驱节点
        • 3.7删除指定节点
        • 3.8删除所有元素为key的节点
        • 3.9链表的长度
        • 3.9清空链表
  • 完整代码

1. ArrayList的缺陷

上节课已经熟悉了ArrayList的使用，并且进行了简单模拟实现。通过源码知道，ArrayList底层使用数组来存储元素：

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{// ...// 默认容量是10private static final int DEFAULT_CAPACITY = 10;//...// 数组：用来存储元素transient Object[] elementData; // non-private to simplify nested class access// 有效元素个数private int size;public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
//
}

由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

2. 链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
在这里插入图片描述
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

  1. 单向或者双向
    在这里插入图片描述
  2. 带头或者不带头
    在这里插入图片描述
  3. 循环或者非循环
    在这里插入图片描述
    虽然有这么多的链表的结构，但是我们重点掌握两种:
    无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
    在这里插入图片描述
    无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

2.2 链表的实现

1.链表的功能

package mysingleList;public interface IList {void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}

2.初始化链表

public class MySingleList implements IList{static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val = val;}}public ListNode head;public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}

开辟了内存空间
在这里插入图片描述
使每个node的next域指向下一个节点的地址，连接成链表
head指向第一个节点的地址
在这里插入图片描述

3.实现功能接口

3.1头插添加元素

 public void addFirst(int data) {ListNode node = new ListNode(data);if(this.head == null){this.head = node;}else {node.next = this.head;this.head = node;}}

对 node.next = this.head;
this.head = node;
进行解释，node的next域指向下一个节点的地址
head继续为头节点在这里插入图片描述

3.2尾插法添加新元素

public void addLast(int data) {ListNode node = new ListNode(data);ListNode cur = head;if (this.head == null){this.head = node;}else {while(cur.next != null){cur = cur.next;}cur.next = node;}}

找到最后一个元素cur，cur的next指向要插入元素的地址
在这里插入图片描述

3.3找到下标的前驱节点

 private ListNode searchPrev(int index){ListNode cur = this.head;int count = 0;while(count != index-1){cur = cur.next;count++;}return cur;}

3.4指定位置插入元素

public void addIndex(int index, int data) {//判断index的位置是否合法if(index < 0 || index >size()){return;}//插入到第一个节点位置if(index == 0){addFirst(data);}//插入到最后一个节点的位置if (index == size()){addLast(data);}//中间位置else {ListNode node = new ListNode(data);ListNode cur = searchPrev(index);node.next = cur.next;cur.next = node;}}

在这里插入图片描述

3.5指定元素是否存在

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

遍历一遍链表寻找是否有key元素

3.6找到指定元素的前驱节点

private ListNode findPrev(int key){ListNode cur = this.head;while(cur.next != null){if (cur.next.val == key){return cur;}cur = cur.next;}return null;}

3.7删除指定节点

public void remove(int key) {if (this.head == null){System.out.println("没有节点，无法删除");return;}//指定元素在头节点if (this.head.val == key){this.head = this.head.next;}else {ListNode cur = findPrev(key);//没有找到指定元素if (cur == null){System.out.println("没有找到要删除的节点");return;}//找到了指定元素ListNode del = cur.next;cur.next = del.next;}}

在这里插入图片描述

3.8删除所有元素为key的节点

public void removeAllKey(int key) {if(this.head == null){return;}ListNode prev = this.head;ListNode cur = this.head.next;while(cur != null){if(cur.val == key){prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}//删除的节点为头节点if(this.head.val == key){this.head = this.head.next;}}

3.9链表的长度

public int size() {ListNode cur = this.head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}

3.9清空链表

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

完整代码

package mysingleList;public class MySingleList implements IList{static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val = val;}}public ListNode head;public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);if(this.head == null){this.head = node;}else {node.next = this.head;this.head = node;}}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);ListNode cur = head;if (this.head == null){this.head = node;}else {while(cur.next != null){cur = cur.next;}cur.next = node;}}@Overridepublic void addIndex(int index, int data) {if(index < 0 || index >size()){return;}if(index == 0){addFirst(data);}if (index == size()){addLast(data);}else {ListNode node = new ListNode(data);ListNode cur = searchPrev(index);node.next = cur.next;cur.next = node;}}private ListNode searchPrev(int index){ListNode cur = this.head;int count = 0;while(count != index-1){cur = cur.next;count++;}return cur;}@Overridepublic boolean contains(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){return true;}}return false;}@Overridepublic void remove(int key) {if (this.head == null){System.out.println("没有节点，无法删除");return;}if (this.head.val == key){this.head = this.head.next;}else {ListNode cur = findPrev(key);if (cur == null){System.out.println("没有找到要删除的节点");return;}ListNode del = cur.next;cur.next = del.next;}}private ListNode findPrev(int key){ListNode cur = this.head;while(cur.next != null){if (cur.next.val == key){return cur;}cur = cur.next;}return null;}@Overridepublic void removeAllKey(int key) {if(this.head == null){return;}ListNode prev = this.head;ListNode cur = this.head.next;while(cur != null){if(cur.val == key){prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(this.head.val == key){this.head = this.head.next;}}@Overridepublic int size() {ListNode cur = this.head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {ListNode cur = this.head;while(cur != null){ListNode curNext = cur.next;cur.next = null;cur = curNext;}head = null;}@Overridepublic void display() {ListNode cur = this.head;while (cur != null){System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}
}

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

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

相关文章

Flutter图标

Flutter图标

https://fluttericon.cn/ Flutter 内置了丰富的图标。 Icon(Icons.ac_unit)
阅读更多...
linux内核分析：线程和进程创建，内存管理

linux内核分析：线程和进程创建，内存管理

lec18-19:进程与线程创建 lec20-21虚拟内存管理 内核代码，全局变量这些只有一份，但是内核栈有多份，这可能就是linux线程模型1对1模式的由来。通过栈来做的 x86 CPU支持分段和分页（平坦内存模式）两种 分段，选择子那里就有特权标记了
阅读更多...
高速DSP系统设计参考指南（一）高速DSP设计面临的挑战

高速DSP系统设计参考指南（一）高速DSP设计面临的挑战

&#xff08;一&#xff09;高速DSP设计面临的挑战 1. 概述2. 一般挑战3. DSP音频系统的挑战4. 视频系统的挑战5. DSP通信系统面临的挑战 资料参考来自TI官网和网络。 1. 概述 DSP芯片&#xff0c;也称数字信号处理器&#xff0c;是一种具有特殊结构的微处理器。DSP芯片的内部…
阅读更多...
【开发】视频监控平台EasyCVR分组批量绑定/取消通道功能的后端代码设计逻辑介绍

【开发】视频监控平台EasyCVR分组批量绑定/取消通道功能的后端代码设计逻辑介绍

视频监控平台/视频存储/视频分析平台EasyCVR基于云边端一体化管理&#xff0c;可支持视频实时监控、云端录像、云存储、磁盘阵列存储、回放与检索、智能告警、平台级联等功能。安防监控平台在线下场景中应用广泛&#xff0c;包括智慧工地、智慧工厂、智慧校园、智慧社区等等。 …
阅读更多...
二进制 Deploy Kubernetes v1.23.17 超级详细部署

二进制 Deploy Kubernetes v1.23.17 超级详细部署

文章目录 1. 预备条件2. 基础配置2.1 配置root远程登录2.2 配置主机名2.3 安装 ansible2.4 配置互信2.5 配置hosts文件2.6 关闭防firewalld火墙2.7 关闭 selinux2.8 关闭交换分区swap2.9 修改内核参数2.10 安装iptables2.11 开启ipvs2.12 配置limits参数2.13 配置 yum2.14 配置…
阅读更多...
浅析AI视频智能分析系统人脸检测算法的应用与特点

浅析AI视频智能分析系统人脸检测算法的应用与特点

AI人脸检测算法可以提取人脸和服装的特征&#xff0c;并将其分类为有用的类别&#xff0c;例如性别、年龄和服装颜色。通过搜索这些丰富的属性信息&#xff0c;可以帮助我们轻松找到目标人物&#xff0c;比如通过人脸以图搜图、人脸布控等等。 如何搭建重点部位人脸识别动态布控…
阅读更多...
Fuxploider：一款针对文件上传漏洞的安全检测与研究工具

Fuxploider：一款针对文件上传漏洞的安全检测与研究工具

Fuxploider：一款针对文件上传漏洞的安全检测与研究工具 1.概述2. 工具使用1.概述 Fuxploider是一款功能强大的开源渗透测试工具，该工具专门针对文件上传漏洞而设计，可以帮助广大研究人员以自动化的方式检测和利用目标站点文件上传表单中的安全问题 由于该工具基于Python 3…
阅读更多...
elasticsearch18-自动补全实战

elasticsearch18-自动补全实战

个人名片&#xff1a; 博主&#xff1a;酒徒ᝰ. 个人简介&#xff1a;沉醉在酒中&#xff0c;借着一股酒劲&#xff0c;去拼搏一个未来。 本篇励志&#xff1a;三人行&#xff0c;必有我师焉。 本项目基于B站黑马程序员Java《SpringCloud微服务技术栈》&#xff0c;SpringCloud…
阅读更多...
HUAWEI华为MateBook X Pro 2021款 i7 集显(MACHD-WFE9Q)原装出厂Win10系统20H2

HUAWEI华为MateBook X Pro 2021款 i7 集显(MACHD-WFE9Q)原装出厂Win10系统20H2

华为笔记本电脑原厂系统自带指纹驱动、显卡驱动、声卡驱动、网卡驱动等所有驱动、出厂主题壁纸、系统属性华为专属LOGO标志、Office办公软件、华为电脑管家等预装程序 链接&#xff1a;https://pan.baidu.com/s/1oeSM0ciwyyRIKms5tR4SNA?pwdo2gq 提取码&#xff1a;o2gq
阅读更多...
上海长宁来福士P2.5直径4米无边圆形屏圆饼屏圆面屏圆盘屏平面圆屏异形创意LED显示屏案例

上海长宁来福士P2.5直径4米无边圆形屏圆饼屏圆面屏圆盘屏平面圆屏异形创意LED显示屏案例

长宁来福士广场是一个大型广场&#xff0c;坐落于上海中山公园商圈的核心区域&#xff0c;占地逾6万平方米&#xff0c;其中地上总建筑面积近24万平方米&#xff0c;总投资额约为96亿人民币。 LED圆形屏是根据现场和客户要求定制的一款异形创意LED显示屏&#xff0c;进行文字、…
阅读更多...
SkyWalking快速上手（一）——安装单机版SkyWalking、使用SkyWalking

SkyWalking快速上手（一）——安装单机版SkyWalking、使用SkyWalking

文章目录 什么是SkyWalking为什么选择SkyWalking安装步骤前置条件环境要求下载 SkyWalking 配置 SkyWalkingSkywalking 使用Agent 配置Collector 配置 启动 SkyWalking配置SkyWalking代理 SkyWalking的监控功能分布式调用链追踪性能指标监控告警和报警 总结 什么是SkyWalking …
阅读更多...
vue3中使用el-upload + tui-image-editor进行图片处理

vue3中使用el-upload + tui-image-editor进行图片处理

效果如下 看之前请先看上一篇《vue3中使用组件tui-image-editor进行图片处理》中的 1、第一步安装 2、第二部封装组件 本篇只是在这基础上结合el-upload使用组件 3、第三步结合el-upload使用组件 <template><el-dialog:title"dialogTitle":modelValue&qu…
阅读更多...
常见的API

常见的API

常见的 API Math 从 JDK 版本 1 开始的, 用来计算的一些方法 这里面定义了两个常量的 PI 和 E 这两个是最接近 pi 的值和最接近对数的值 Abs (int a ) 取绝对值Ceil (double a)向上取整Floor (double a )向下取整Round (float a)四舍五入Max (int a, int b) 取最大值Pow (dou…
阅读更多...
【微信小程序】文章设置

【微信小程序】文章设置

设置基本字体样式&#xff1a;行高、首行缩进 font-size: 32rpx;line-height: 1.6em;text-indent: 2em;padding: 20rpx 0;border-bottom: 1px dashed var(--themColor); 两端对齐 text-align: justify; css文字两行或者几行显示省略号 css文字两行或者几行显示省略号_css…
阅读更多...
【C进阶】指针和数组笔试题解析

【C进阶】指针和数组笔试题解析

做题之前我们先来回顾一下 对于数组名的理解&#xff1a;除了以下两种情况&#xff0c;数组名表示的都是数组首元素的地址 &#xff08;1&#xff09;sizeof&#xff08;数组名&#xff09;&#xff1a;这里的数组名表示整个数组 &#xff08;2&#xff09;&&#xff08;数…
阅读更多...
Kakfa - Producer机制原理与调优

Kakfa - Producer机制原理与调优

Producer是Kakfa模型中生产者组件&#xff0c;也就是Kafka架构中数据的生产来源&#xff0c;虽然其整体是比较简单的组件&#xff0c;但依然有很多细节需要细品一番。比如Kafka的Producer实现原理是什么&#xff0c;怎么发送的消息&#xff1f;IO通讯模型是什么&#xff1f;在实…
阅读更多...
Prometheus黑盒测试模块，监控TCP端口+ HTTP/HTTPS路由状态

Prometheus黑盒测试模块，监控TCP端口+ HTTP/HTTPS路由状态

文章目录 一、黑盒测试使用场景二、安装blackbox-exporter三、监控TCP端口四、监控HTTP/HTTPS路由五、最后分享几款Grafana模板 一、黑盒测试使用场景 官方下载地址 blackbox-exporter是Prometheus官方提供的一个黑盒测试的解决方案&#xff0c;可用于以下使用场景&#xff1a…
阅读更多...
大数据-玩转数据-Flink恶意登录监控

大数据-玩转数据-Flink恶意登录监控

一、恶意登录 对于网站而言&#xff0c;用户登录并不是频繁的业务操作。如果一个用户短时间内频繁登录失败&#xff0c;就有可能是出现了程序的恶意攻击&#xff0c;比如密码暴力破解。 因此我们考虑&#xff0c;应该对用户的登录失败动作进行统计&#xff0c;具体来说&#x…
阅读更多...
SpringBoot启动方式

SpringBoot启动方式

SpringBoot启动方式 springboot的启动经过了一些一系列的处理&#xff0c;我们先看看整体过程的流程图 SpringBoot的启动方式 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><…
阅读更多...
线性代数基础-矩阵

线性代数基础-矩阵

八、矩阵的基础概念 1.矩阵 我们忘掉之前行列式的一切&#xff0c;列一种全新的数表&#xff0c;虽然长得很像&#xff0c;但是大不相同&#xff0c;首先一个区别就是矩阵不能展开成一个值&#xff0c;这里不讨论矩阵的空间意义 { a 11 x 1 a 12 x 2 a 13 x 3 . . . a 1…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023