Java 集合List相关面试题


在这里插入图片描述

📕作者简介: 过去日记,致力于Java、GoLang,Rust等多种编程语言,热爱技术,喜欢游戏的博主。
📗本文收录于java面试题系列,大家有兴趣的可以看一看
📘相关专栏Rust初阶教程、go语言基础系列、spring教程等,大家有兴趣的可以看一看
📙Java并发编程系列,设计模式系列、go web开发框架 系列正在发展中,喜欢Java,GoLang,Rust,的朋友们可以关注一下哦!

文章目录

    • List相关面试题
      • 数组
        • 数组概述
        • 寻址公式
        • 操作数组的时间复杂度
      • ArrayList源码分析
        • 成员变量
        • 构造方法
        • ArrayList源码分析
        • 面试题-ArrayList list=new ArrayList(10)中的list扩容几次
        • 面试题-如何实现数组和List之间的转换
      • 链表
        • 单向链表
        • 单向链表时间复杂度分析
        • 双向链表
        • 双向链表时间复杂度分析
        • 面试题-ArrayList和LinkedList的区别是什么?

List相关面试题

数组

数组概述

数组(Array)是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

int[] array = {22,33,88,66,55,25};

在这里插入图片描述

我们定义了这么一个数组之后,在内存的表示是这样的:

在这里插入图片描述

现在假如,我们通过arrar[1],想要获得下标为1这个元素,但是现在栈内存中指向的堆内存数组的首地址,它是如何获取下标为1这个数据的?

在这里插入图片描述

寻址公式

为了方便大家理解,我们把数组的内存地址稍微改了一下,都改成了数字,如下图

在这里插入图片描述

在数组在内存中查找元素的时候,是有一个寻址公式的,如下:

arr[i] = baseAddress + i * dataTypeSize

baseAddress:数组的首地址,目前是10

dataTypeSize:代表数组中元素类型的大小,目前数组重存储的是int型的数据,dataTypeSize=4个字节

arr:指的是数组

i:指的是数组的下标

有了寻址公式以后,我们再来获取一下下标为1的元素,这个是原来的数组

int[] array = {22,33,88,66,55,25};

套入公式:

array[1] =10 + i * 4 = 14

获取到14这个地址,就能获取到下标为1的这个元素了。

操作数组的时间复杂度

1.随机查询(根据索引查询)

数组元素的访问是通过下标来访问的,计算机通过数组的首地址寻址公式能够很快速的找到想要访问的元素

public int test01(int[] a,int i){return a[i];// a[i] = baseAddress + i \* dataSize
}

代码的执行次数并不会随着数组的数据规模大小变化而变化,是常数级的,所以查询数据操作的时间复杂度是O(1)

2. 未知索引查询O(n)或O(log2n)

情况一:查找数组内的元素,查找55号数据,遍历数组时间复杂度为O(n)

在这里插入图片描述

情况二:查找排序后数组内的元素,通过二分查找算法查找55号数据时间复杂度为O(logn)

在这里插入图片描述

3.插入O(n)

数组是一段连续的内存空间,因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低。

假设数组的长度为 n,现在如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。如下图所示:

在这里插入图片描述

新增之后的数据变化,如下

在这里插入图片描述

所以:

插入操作,最好情况下是O(1)的,最坏情况下是O(n)的,平均情况下的时间复杂度是O(n)

4.删除O(n)

同理可得:如果我们要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了,时间复杂度仍然是O(n)。

ArrayList源码分析

分析ArrayList源码主要从三个方面去翻阅:成员变量,构造函数,关键方法

以下源码都来源于jdk1.8

成员变量

在这里插入图片描述

DEFAULT_CAPACITY = 10; 默认初始的容量**(CAPACITY)

EMPTY_ELEMENTDATA = {}; 用于空实例的共享空数组实例

DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};用于默认大小的空实例的共享空数组实例

Object[] elementData; 存储元素的数组缓冲区

int size; ArrayList的大小(它包含的元素数量)

构造方法

在这里插入图片描述

  • 第一个构造是带初始化容量的构造函数,可以按照指定的容量初始化数组

  • 第二个是无参构造函数,默认创建一个空集合

在这里插入图片描述

将collection对象转换成数组,然后将数组的地址的赋给elementData

ArrayList源码分析

添加数据的流程

在这里插入图片描述

结论:

  • 底层数据结构

ArrayList底层是用动态的数组实现的

  • 初始容量

ArrayList初始容量为0,当第一次添加数据的时候才会初始化容量为10

  • 扩容逻辑

ArrayList在进行扩容的时候是原来容量的1.5倍,每次扩容都需要拷贝数组

  • 添加逻辑

    • 确保数组已使用长度(size)加1之后足够存下下一个数据

    • 计算数组的容量,如果当前数组已使用长度+1后的大于当前的数组长度,则调用grow方法扩容(原来的1.5倍)

    • 确保新增的数据有地方存储之后,则将新元素添加到位于size的位置上。

    • 返回添加成功布尔值。

面试题-ArrayList list=new ArrayList(10)中的list扩容几次

难易程度:☆☆☆

出现频率:☆☆

在这里插入图片描述

参考回答:

该语句只是声明和实例了一个 ArrayList,指定了容量为 10,未扩容

面试题-如何实现数组和List之间的转换

难易程度:☆☆☆

出现频率:☆☆

如下代码:

在这里插入图片描述

参考回答:

  • 数组转List ,使用JDK中java.util.Arrays工具类的asList方法

  • List转数组,使用List的toArray方法。无参toArray方法返回 Object数组,传入初始化长度的数组对象,返回该对象数组

面试官再问:

1,用Arrays.asList转List后,如果修改了数组内容,list受影响吗

2,List用toArray转数组后,如果修改了List内容,数组受影响吗

在这里插入图片描述
)

数组转List受影响

List转数组不受影响

再答:

1,用Arrays.asList转List后,如果修改了数组内容,list受影响吗

Arrays.asList转换list之后,如果修改了数组的内容,list会受影响,因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合,在这个集合的构造器中,把我们传入的这个集合进行了包装而已,最终指向的都是同一个内存地址

2,List用toArray转数组后,如果修改了List内容,数组受影响吗

list用了toArray转数组后,如果修改了list内容,数组不会影响,当调用了toArray以后,在底层是它是进行了数组的拷贝,跟原来的元素就没啥关系了,所以即使list修改了以后,数组也不受影响

链表

单向链表
  • 链表中的每一个元素称之为结点(Node)

  • 物理存储单元上,非连续、非顺序的存储结构

  • 单向链表:每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next

在这里插入图片描述

代码实现参考:

在这里插入图片描述

链表中的某个节点为B,B的下一个节点为C 表示: B.next==C

单向链表时间复杂度分析

(1)查询操作

在这里插入图片描述

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

  • 查询其他结点需要遍历链表,时间复杂度是O(n)

(2)插入和删除操作

在这里插入图片描述

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

而双向链表,顾名思义,它支持两个方向

  • 每个结点不止有一个后继指针 next 指向后面的结点

  • 有一个前驱指针 prev 指向前面的结点

参考代码

在这里插入图片描述

在这里插入图片描述

对比单链表:

  • 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址

  • 支持双向遍历,这样也带来了双向链表操作的灵活性

双向链表时间复杂度分析

在这里插入图片描述

(1)查询操作

  • 查询头尾结点的时间复杂度是O(1)

  • 平均的查询时间复杂度是O(n)

  • 给定节点找前驱节点的时间复杂度为O(1)

(2)增删操作

  • 头尾结点增删的时间复杂度为O(1)

  • 其他部分结点增删的时间复杂度是 O(n)

  • 给定节点增删的时间复杂度为O(1)

面试题-ArrayList和LinkedList的区别是什么?
  • 底层数据结构

    • ArrayList 是动态数组的数据结构实现

    • LinkedList 是双向链表的数据结构实现

  • 操作数据效率

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

    • ArrayList底层是数组,内存连续,节省内存

    • LinkedList 是双向链表需要存储数据,和两个指针,更占用内存

  • 线程安全

    • ArrayList和LinkedList都不是线程安全的
    • 如果需要保证线程安全,有两种方案:
      • 在方法内使用,局部变量则是线程安全的
      • 使用线程安全的ArrayList和LinkedList

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

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

相关文章

dataGrip连接数据库mysql和intersystems的iris

文章目录 前言创建新项目选择对应的数据库产品类型新建数据库资源连接sql命令窗体手动配置本地驱动 前言 intersystems公司的产品iris是cache的升级版本,目前绝大多数数据库工具都没法连接这个数据库 datagrip下载地址 https://download-cdn.jetbrains.com.cn/da…

eBay在人工智能道路上的成败得失:衡量标准是关键

我是2006年加入eBay的。2009年,这家公司的运营状况非常糟糕,其股价创历史新低(远低于近24美元的历史高位),还出现削减各项成本、负增长、市场占有率降低、技术团队缺乏创新能力等情况。 简而言之,eBay公司…

CentOS7自动备份数据库到git

虽然数据库没什么数据,但是有就是珍贵的啦,为了服务器什么的无了,所以还是要自动备份一下比较好。 Open备忘第一页 步骤 在Gitee(github)上创建一个私有仓库Gitee(github)配置好服务器的ssh在服…

Oracle BIEE 示例(一)数据透视表2

1 背景 版本:BIEE 12C 视图:数据透视表 实现内容(顺序与具体内容不一致): 2 空列显示(方法一) 2.1 问题 列为空时,标题栏不显示信息。 2.2 期望 即使数据为空,也要显示列名。 2.3 官方资料 2.3.1 操作步骤 2.3.1.1 要在分析级别关闭空值隐藏,请执行以下操作…

MySQL与PostgreSQL对比

对比 许可证 License MySQL 社区版采用 GPL 许可证。Postgres 发布在 PostgreSQL 许可下,是一种类似于 BSD 或 MIT 的自由开源许可。 即便 MySQL 采用了 GPL,仍有人担心 MySQL 归 Oracle 所有,这也是为什么 MariaDB 从 MySQL 分叉出来。 …

mac安装部署gitbook教程

mac安装部署gitbook教程 前言一、安装准备二、GitBook安装三、项目初始化 前言 一些自己实际操作的记录。 一、安装准备 Node.js gitbook基于Node.js,所以需要提前安装。 下载地址:https://nodejs.org/en/,可以下载比较新的版本。(但我的建议…

[已解决]504 Gateway Time-out 网关超时

文章目录 问题:504 Gateway Time-out 504 Gateway Time-out 网关超时思路解决 问题:504 Gateway Time-out 504 Gateway Time-out 网关超时 思路 网上的常规思路是修改nginx配置文件,增加请求执行时间,试过没有用 keepalive_timeout 600; fastcgi_con…

vue3-深入组件-组件注册和props更多细节

组件注册 定义好的组件需要注册才能被使用。 注册方式有两种 全局注册 局部注册 全局注册 .component() 方法,让组件在当前 Vue 应用中全局可用。 在 main.ts 中 import ./assets/main.cssimport { createApp } from vue import { createPinia } from pinia i…

基于springboot+vue的网上租赁系统(前后端分离)

博主主页:猫头鹰源码 博主简介:Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容:毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 研究背景…

碳排放预测 | Matlab实现LSTM多输入单输出未来碳排放预测,预测新数据

碳排放预测 | Matlab实现LSTM多输入单输出未来碳排放预测,预测新数据 目录 碳排放预测 | Matlab实现LSTM多输入单输出未来碳排放预测,预测新数据预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab实现LSTM长短期记忆神经网络多输入单输出未来…

架构师之路(十六)计算机网络(传输层)

前置知识(了解):计算机基础。 作为架构师,我们所设计的系统很少为单机系统,因此有必要了解计算机和计算机之间是怎么联系的。局域网的集群和混合云的网络有啥区别。系统交互的时候网络会存在什么瓶颈。 既然网络层已经…

C# Bitmap类学习1

Bitmap对象封装了GDI中的一个位图,此位图由图形图像及其属性的像素数据组成.因此Bitmap是用于处理由像素数据定义的图像的对象。 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using …

mybatis----小细节

1、起别名 在MyBatis中&#xff0c;<typeAliases>元素用于定义类型别名&#xff0c;它可以将Java类名映射为一个更简短的别名&#xff0c;这样在映射文件中可以直接使用别名而不需要完整的类名。 下面是一个示例&#xff1a; 在mybatis核心配置文件中配置typeAliases标…

第21课 在Android Native开发中架起java与c++互通的桥梁

在开始本节课&#xff0c;我尝试把项目拷贝到另一台电脑上以便继续工作&#xff0c;但出现了大量的“could not be resolved”问题&#xff0c;尝试包含新的include路径也无法解决该问题&#xff0c;最后删除了项目的Native Support&#xff0c;然后重新添加Native Support才解…

百科同名就不能重建一个百科吗,代创建百科公司是如何做到的

发现自己的名字在百度上已经有百科词条并不出奇&#xff0c;因为同名同姓的人非常多&#xff0c;但是是不是百科已经有同名词条了就不能重建一个百科&#xff0c;很多朋友在自己做百度百科不通过时往往会发出这样的疑问。 实际上百度百科同名也是可以再重新创建的&#xff0c;…

【K8S】Service使用NodePort对外暴露应用

一、背景介绍 Pod是有生命周期的&#xff0c;当一个工作节点(node)销毁时&#xff0c;节点上运行的pods也会被销毁。ReplicationController会动态地在其他节点上创建Pod来保持应用程序的运行&#xff0c;每一个Pod都有一个独立的IP地址&#xff0c;甚至是同一个节点上的Pod。可…

菜鸟导入导出assetbundle

因为菜鸟不会用unity c#什么的&#xff0c;所以最后参考贴吧的方法用的是UABE(Unity Assets Bundle Extractor)和UABEA(Unity Assets Bundle Extractor Avalonia) 可以去github上下载 对于txt、xml什么的可以直接改&#xff0c;但是byte文件里还是会有一些类似乱码的东西&…

oracle vm安装ubuntu使用桥接网络不能访问外网

1. 问题描述 公司网络环境中&#xff0c;可以ping通内网中的所有电脑&#xff0c;ping不通百度域名以及百度的ip地址在热点共享时或者家里未出现此问题 2. 尝试的解决办法 设置网络共享&#xff0c;未起作用。后来测试通以后发现共享不共享都可以通 3. 最终解决办法 H3C禁…

案例需求:多人聊天室

文章目录 案例需求描述 p189使用wxPython绘制客户端界面 p190 案例需求描述 p189 图形界面的第三方库 使用wxPython绘制客户端界面 p190 代码示例&#xff1a; import wxclass YsjClient(wx.Frame):def __init__(self,client_name):# 调用父类的初始化方法# None&#xff1a;…

Linux——系统简介

1、从UNIX到LINUX 在目前主流的服务器端操作系统中&#xff0c;UNIX诞生于20世纪60年代末&#xff0c;Windows诞生于20世纪80年代中期&#xff0c;Linux诞生于20世纪90年代初&#xff0c;可以说UNIX是操作系统中的“老大哥”。 1.1、Linux简史 Linux内核最初是由李纳斯托瓦兹…