【Java面试】十四、LinkedList相关

文章目录

  • 1、单向链表
    • 1.1 结构
    • 1.2 查询的时间复杂度
    • 1.3 插入删除的时间复杂度
  • 2、双向链表
    • 2.1 时间复杂度
  • 3、ArrayList和LinkedList的区别是什么

1、单向链表

1.1 结构

  • 存储空间上,非连续
  • 链表的每个元素称结点Node
  • 每个结点包括两块:存储数据的数据域data、存储下一个节点地址的指针域next(后继指针)

在这里插入图片描述

代码实现如下,假设链表中有个B结点,其下一个结点为C,则B.next == C

在这里插入图片描述

1.2 查询的时间复杂度

在这里插入图片描述

  • 只有在查询头节点的时候不需要遍历链表,时间复杂度是O(1)
  • 查询其他结点需要遍历链表,时间复杂度是 O(n)

1.3 插入删除的时间复杂度

在这里插入图片描述

  • 只有在添加和删除头节点的时候不需要遍历链表,时间复杂度是 O(1)
  • 添加或删除其他结点时,首先需要遍历链表找到对应节点后,才能完成新增或删除节点,因此时间复杂度是 O(n)

2、双向链表

每个结点有三部分:

  • 前驱指针prev
  • 数据域data
  • 后继指针next

因此,可以支持双向遍历
在这里插入图片描述
代码实现:

在这里插入图片描述

2.1 时间复杂度

查询时:

  • 查询头尾结点的时间复杂度是 O(1)
  • 平均的查询时间复杂度是 O(n)
  • 给定节点找前驱后继结点的时间复杂度为 O(1)

增删时:

  • 头尾结点增删的时间复杂度为 O(1)
  • 其他部分结点增删的时间复杂度是 O(n)
  • 给定节点增删前驱后继结点的时间复杂度为 O(1)

3、ArrayList和LinkedList的区别是什么

1)底层数据结构上来说:

  • ArrayList底层是一个数组
  • LinkedList底层是一个双向链表

在这里插入图片描述
2)操作数据的效率上来说:

  • ArrayList 按照下标査询的时间复杂度 O(1),因为内存是连续的,可根据寻址公式取。而LinkedList 不支持下标查询
  • 查找数据时(ArrayList未知索引): ArrayList需要遍历,链表也需要链表,时间复杂度都是 O(n)
  • 新增和删除:ArrayList 尾部插入和删除,时间复杂度是 O(1),其他部分增删需要挪动数组,时间复杂度是 O(n)。LinkedList 头尾节点增删时间复杂度是 O(1),其他都需要先遍历链表找数据,时间复杂度是 O(n)

3)空间上来说:

  • ArrayList底层是数组,内存连续,只存数据,节省内存空间
  • LinkedList底层是双向链表,内存不连续,除了存数据,还要存两个指针,不节省内存

4)线程安全上来说:

  • ArrayList 和 LinkedList 都不是线程安全的

PS:如果要保证线程安全,可考虑:

  • 在方法内部的局部变量中用,局部变量,每个线程一份,无安全问题
  • 使用Collections工具类,包装一下ArrayList 和 LinkedList(底层加了synchronized锁),就是线程安全的

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++11标准-详解

目录 1、列表初始化 2、隐式类型转换 1)概念理解 2)举例增进理解 3)隐式与显式区别? a、直接初始化 vs 拷贝初始化 b、构造函数调用 c、语义上的差异 d、性能差异 4)explicit 关键字 5)多参数的隐…

Python 组合序号

import pandas as pd # 创建一个示例数据框 data { group: [A, A, A, B, B, C, C, C, C], value: [3, 1, 2, 5, 4, 6, 9, 7, 8] } df pd.DataFrame(data) # 先按group分组,再按value列升序排序 df_sorted_asc df.sort_values(by[group, value]) # 使…

Ansible自动化运维工具 playbook 剧本

一、Playbooks 1. playbooks 介绍 Playbooks(剧本)是一种用于定义自动化任务的文件,通常与诸如Ansible等工具相关联。它们以YAML格式编写,包含了一系列有组织的任务,这些任务可以在远程计算机上执行。一个Playbook通…

如果小孩对什么也不感兴趣,只爱看手机和电脑 怎么办?怎样培养孩子兴趣?兴趣有哪些可以选择?如何快速找到定位小孩的兴趣?

自古到今,生存都很艰难!不论是动物还是人 得看小孩兴趣,有些爱读书,有些爱踢球,就怕啥也不爱,只看手机和电脑的,想卷都没个方向。 特长:是你从60亿人中不一样的地方。突出才易于生…

深度学习笔记:2.Jupyter Notebook

Jupyter Notebook 常用操作快捷键魔法指令_jupyter notebook快捷键调用函数-CSDN博客https://blog.csdn.net/qq_26917905/article/details/137211336?ops_request_misc%257B%2522request%255Fid%2522%253A%2522171748112816800182160793%2522%252C%2522scm%2522%253A%25222014…

模型测试优化

针对怼螺丝孔场景交叉测试 文章目录 修改一:修改二: 基于训练场景,进行修改,用以验证泛化性 模型说明:训练所用的物体模型上,有两个孔位,其中左侧为1号孔位,右侧为2号孔位 现状&…

Scalable Diffusion Models with Transformers

Metahttps://github.com/facebookresearch/DiT/tree/main?tabreadme-ov-file 问题引入 transformer架构的latent diffusion model,有较好的延展性并是sota; methods patchify:原图片 I ∈ R H W 3 I\in\mathbb{R}^{H\times W\times 3…

python运算符和表达式

目录 算数运算符 赋值运算符 关系运算符 逻辑运算符 位运算符 成员运算符 运算符优先级 易错点: 算数运算符 赋值运算符 关系运算符 int可以转换成float 逻辑运算符 可以是一个运算也可以是一个字符串 左边为空格,为假,输出为空 优…

Nacos注册中心 --学习笔记

Nacos注册中心是什么? 想象一下一个繁忙的购物中心,里面有很多商店,每个商店都在某个位置提供不同的商品或服务。这个购物中心有一个信息台,人们可以在这里查询任何商店的位置和提供的服务。等到有新的商店开张,或者现…

海南聚广众达电子商务咨询有限公司靠谱吗?

在数字经济的浪潮中,抖音电商作为新兴业态,正以其独特的魅力和强大的势能,改变着传统商业模式,引领着新一轮的消费潮流。海南聚广众达电子商务咨询有限公司,作为抖音电商服务领域的佼佼者,凭借其专业的团队…

Linux 多线程 生产者消费者 问题

在 Linux 系统中,生产者和消费者问题是一个经典的多线程同步问题,用于描述如何在多线程环境中协调多个线程对共享资源的访问。这个问题通常涉及两个类型的线程:生产者线程和消费者线程。生产者线程负责生成数据并将其放入缓冲区,而…

大数据之Schedule调度错误(一)

当我们在利用ooize发起整个任务的调度过程中,如果多个调度任务同时运行并且多个调度任务操作了相同的表,那么就会出现如下的错误关系: Invalid path hdfs://iZh5w01l7f8lnog055cpXXX:8000/user/admin/xxx: No files matching path hdfs://iZh5w01l7f8lnog055cpXXX:8000/user/ad…

VS2017配置OpenCV4.5.1

VS2017配置OpenCV 一、下载OpenCV二、配置OpenCV的电脑环境变量三、配置visual Studio添加路径复制文件到C盘 四、如何使用注意运行时选择Debug x64 五、报错:VSOpencv出现:xxx处有未经处理的异常: Microsoft C 异常: cv::Exception,位于内存…

iLogtail 2.0 重大升级,端上支持 SPL

作者:太业 流式处理语言发展 早期流式处理概念: 20 世纪 70 年代,编程语言如 APL 提供了对数组的流式操作,这可以看作是流式处理语法的早期形式。管道(Pipes)概念在 UNIX 系统中的引进使得可以通过命令行将…

opencv进阶 ——(十)图像处理之基于dlib人脸检测与识别

Dlib是一个功能丰富的C库,设计用于构建复杂的软件系统,尤其在机器学习、计算机视觉和数值计算等领域有着广泛的应用。以下是对Dlib的简要介绍: 特性: 机器学习算法:Dlib包含了各种机器学习算法,如支持向量机…

友思特应用 | 慧眼识珠:如何实现无障碍高光谱成像?

导读 近红外相机可帮助人眼捕捉不同材料之间光谱特征的微小差异。友思特 Monarch 微型可调近红外相机以其小体积、低成本、高性能,3步即可快速实现各种材料的分类应用。 多光谱成像 每个物品都是由不同的化学物质组成的,这些化学物质的反射随光谱带的不…

机器学习18个核心算法模型

1. 线性回归(Linear Regression) 用于建立自变量(特征)和因变量(目标)之间的线性关系。 核心公式: 简单线性回归的公式为: , 其中 是预测值, 是截距, 是斜…

ASCE(美国土木工程师学会)文献校外去哪里查找下载

今天要讲的数据库是ASCE(美国土木工程师学会),该数据库每年出版5万多页的专业期刊、杂志、会议录、专著、技术报告、实践手册和标准等。目前,ASCE数据库中包含35种期刊(1983年至今)、近700卷会议录( 1996年至今)、Civil Engineeri…

10分钟了解KEDA高效弹性伸缩方案

文章目录 为什么需要 KEDA ?KEDA 的原理哪些场景适合使用 KEDA ?微服务多级调用任务执行(生产者与消费者)周期性规律 配置实践KEDA安装helm 方式安装 策略配置scaledobject 对象说明 问题记录 为什么需要 KEDA ? HPA …

五、nodejs存储图片

nodejs存储图片 // 静态托管和数据库创建 创建数据库 新建Public进行静态托管 新建个img的文件夹 在index.js里 // 托管静态 app.use(/public, express.static(./Public))//托管静态资源 /*** 1.引入一个express框架* 2.在加载所有服务模块前,要先连接数据库* …