面试被打脸,数据结构底层都不知道么--回去等通知吧

数据结构之常见的8种数据结构:

-数组Array

-链表 Linked List

-堆 heap

-栈 stack

-队列 Queue

-树 Tree

-散列表 Hash

-图 Graph

数据结构-链表篇


Linklist定义:


-是一种线性表,并不会按线性的顺序存储数据,即逻辑上相邻,物理上不一定相邻的元素。通过指针域来寻找对应的元素。

Linklist优缺点:

优点:
-插入、删除速度快

-灵活分配结点空间

缺点:
-查询速度慢

通过Linklist常用方法来深入底层原理


-add(E e)

-add(int index, E element)

-remove(Obeject o)

-remove(int index)

-ListIterator正向遍历

-反向遍历

总结:


-插入、删除速度快是因为只要通过前后指针就能插入或者删除到链表中,不需要移动其它元素,插入头尾节点更快,因为Node结构体中保存了头尾指针。

-查询速度慢是因为,查询先通过右位移运算来判断对链表是前半部分遍历还是后半部分遍历,剩下的半部分遍历则是一个个节点遍历,头尾查询快,因为保存了头尾指针。
 

数据结构--数组篇

数组的定义:


-申请一块连续的内存空间来存储相同类型数据的集合

-数组存储的是对象的引用而非是对象本身

数组的优缺点:


优点:查询速度快(O(1)复杂度),因为它的存储是连续的内存空间,查找元素=首地址 + 每个元素所分配的空间*下标

从cpu的读取:cpu在读取数组的时候,可以借助缓存机制预读数组的数据,cpu在读取内存的时候会把一块连续的内存空间读入,当进行遍历时,直接命中。而链表是跳跃式的地址,在缓存中命中的概率低,就要跑到内存中去读取数据,缓存的速度远大于内存的读取速度。

缺点:插入 、删除速度慢,因为需要移动该元素后面的所有元素位置

数组的使用场景:


-适合查询多,插入、删除少的场景(整体上来说)

通过数组方法来深入底层原理


ArrayList方法中的常用方法
-add(E e)方法


流程图:


remove(int index)方法:

remove(Object o)方法

remove注意:remove(Object o)方法使用了2个对null跟非null分别使用了==跟equals做了等值比较,找到元素对应的索引位置后再删除与remove(int index)方法步骤基本一样

Iterator遍历方法

迭代注意:迭代过程中有2次的ConcurrentModification检验,一次是2个记录修改次参数expectedModCount = modCount等值校验。二次是 i >= elementData.length,并发过程中多次调用next方法。

Iterator的remove方法

关于System.arraycopy,Array.copyof区别:
-System.arraycopy(Object src, int srcPos, Object dest, int destPos,int length)

有5个参数

src :原数组

srcPos:原数组开始元素拷贝的索引位置

dest:目标数组

destPos:在目标数组的索引位置开始拷贝

length:拷贝的数组长度

-Arraycopyof 底层调用的也是Native方法的System.arraycopy


面试点提问:几种删除方式有什么区别


重点关注:expectedModCount = modCount;ConcurrentModificationException

for循环删除跟Iterator删除方式有什么不同?

Iterator方法:

正序for循环则直接调用remove(Object)或者remove(index)方法,修改了modCount++的值,但是并没有走checkForComodification()检验,该方法只针对了实现了Iterator<E>的类,想要正确删除元素请使用倒序删除

以上2个方法都可以直接删除元素不会报错,正序for循环不保证结果正确性

可以用foreach加强循环删除么?
a,foreach底层的实现原理就是通过Iterator迭代来实现的。所以会存在修改次数跟预期值修改值的比较判断。

b,而foreach循环在删除元素的时候走的是fastRemove()方法,


c,只增加了modCount++


d,并没有expectedModCount = modCount赋值语句,在下一次的循环就会报错


综上所述:使用Iterator跟for循环是可以成功删除元素的,foreach循环则不行。checkForComodification()检验,该方法只针对了实现了Iterator<E>的类,而Iterator跟foreach底层实现都是依赖这个接口。for循环则不依赖

注意上面的Demo只是说删除元素时会不会报错,并不是说上面几种方式都能正确删除完全,使用for循环保证正取删除元素可以使用倒序的方式,或者使用Iterator方式(推荐)。
 

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

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

相关文章

基于硬件隔离增强risc-v调试安全2_安全提议

安全之安全(security)博客目录导读 2023 RISC-V中国峰会 安全相关议题汇总 说明&#xff1a;本文参考RISC-V 2023中国峰会如下议题&#xff0c;版权归原作者所有。

pdf怎么编辑文字?了解一下这几种编辑方法

pdf怎么编辑文字&#xff1f;PDF文件的普及使得它成为了一个重要的文件格式。然而&#xff0c;由于PDF文件的特性&#xff0c;它们不可直接编辑&#xff0c;这就使得PDF文件的修改变得比较麻烦。但是&#xff0c;不用担心&#xff0c;接下来这篇文章就给大家介绍几种编辑pdf文字…

SpringCloudAlibaba Gateway(二)详解-内置Predicate、Filter及自定义Predicate、Filter

Predicate(断言) ​ Predicate(断言)&#xff0c;用于进行判断&#xff0c;如果返回为真&#xff0c;才会路由到具体服务。SpirnngCloudGateway由路由断言工厂实现&#xff0c;直接配置即生效&#xff0c;当然也支持自定义路由断言工厂。 内置路由断言工厂实现 ​ SpringClo…

Java注解和反射

注解(Java.Annotation) 什么是注解&#xff08;Annotation&#xff09;&#xff1f; Annotation是从JDK5.0开始引入的新技术 Annotation的作用: 不是程序本身&#xff0c;可以对程序作出解释(这一点和注释(comment)没什么区别)可以被其他程序(比如:编译器等)读取Annotation的…

ChatGPT插件的优缺点

虽然西弗吉尼亚大学的研究人员看到了最新的官方ChatGPT插件——名为“代码解释器”&#xff08; Code Interpreter&#xff09;的教育应用潜力&#xff0c;但他们也发现&#xff0c;对于使用计算方法处理针对癌症和遗传疾病的定向治疗的生物数据的科学家来说&#xff0c;这款插…

20230901工作心得:IDEA列操作lambda表达式加强版用法

今天是中小学开学时间&#xff0c;亦是9月的开始&#xff0c;继续努力。 今日收获较大的有四个地方&#xff0c;先说这四点。 1、IDEA列操作 使用场景&#xff1a;需要批量将Excel表格里的数据插入到数据库中&#xff0c;此时需要写大量的insert SQL语句。 比如像这样的&am…

解码注意力Attention机制:从技术解析到PyTorch实战

目录 引言历史背景重要性 二、注意力机制基础概念定义组件 注意力机制的分类举例说明 三、注意力机制的数学模型基础数学表达式注意力函数计算权重 数学意义举例解析 四、注意力网络在NLP中的应用机器翻译代码示例 文本摘要代码示例 命名实体识别&#xff08;NER&#xff09;代…

WireShark流量抓包详解

目录 Wireshark软件安装Wireshark 开始抓包示例Wireshakr抓包界面介绍WireShark 主要界面 wireshark过滤器表达式的规则 Wireshark软件安装 软件下载路径&#xff1a;wireshark官网。按照系统版本选择下载&#xff0c;下载完成后&#xff0c;按照软件提示一路Next安装。 Wire…

ICCV 2023 | 利用双重聚合的Transformer进行图像超分辨率

导读 本文提出一种同时利用图像空间和通道特征的 Transformer 模型&#xff0c;DAT&#xff08;Dual Aggregation Transformer&#xff09;&#xff0c;用于图像超分辨&#xff08;Super-Resolution&#xff0c;SR&#xff09;任务。DAT 以块间和块内的双重方式&#xff0c;在空…

企业工程项目管理系统源码-专注项目数字化管理-Java工程管理-二次开发

工程项目各模块及其功能点清单 一、系统管理 1、数据字典&#xff1a;实现对数据字典标签的增删改查操作 2、编码管理&#xff1a;实现对系统编码的增删改查操作 3、用户管理&#xff1a;管理和查看用户角色 4、菜单管理&#xff1a;实现对系统菜单的增删改查操…

用于设计和分析具有恒定近心点半径的低推力螺旋轨迹研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

用Kubernetes(k8s)的ingress部署https应用

用Kubernetes的ingress部署https应用 环境准备Ingress安装域名证书准备 部署应用通过ingress暴露应用根据ssl证书生成对应的secret创建ingress暴露部署的应用确认自己安装了ingress创建ingress 访问你暴露的应用 环境准备 Ingress安装 我之前有一片文章写的是用ingress暴露应…

树和二叉树基础

引言&#xff1a; 树是一种非线性的结构&#xff0c;也是由一个一个的结点构成。 树的一些基本概念&#xff1a; 节点的度&#xff1a;一个节点含有的子树的个数称为该节点的度&#xff1b;如上图&#xff1a;A的度为6 叶节点或终端节点&#xff1a;度为0的节点称为叶节点。…

【LeetCode75】第四十四题 省份数量

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 给我们一个二维数组&#xff0c;表示城市之间的连通情况&#xff0c;连在一起的城市为一个省份&#xff0c;问我们一共有多少个省份。 这…

cocos creator配置终端调试

在launch.json里添加"preLaunchTask":“CocosCreator compile” 在cocos creator里选择开发者&#xff0c;visual studio code工作流&#xff0c;选择添加编译任务。 添加 settings.json {"files.exclude":{"**/.git": true,"**/.DS_Sto…

【大数据】Flink 详解(六):源码篇 Ⅰ

Flink 详解&#xff08;六&#xff09;&#xff1a;源码篇 Ⅰ 55、Flink 作业的提交流程&#xff1f;56、Flink 作业提交分为几种方式&#xff1f;57、Flink JobGraph 是在什么时候生成的&#xff1f;58、那在 JobGraph 提交集群之前都经历哪些过程&#xff1f;59、看你提到 Pi…

2023年7月京东打印机行业品牌销售排行榜(京东运营数据分析)

鲸参谋监测的京东平台7月份打印机行业销售数据已出炉&#xff01; 7月份&#xff0c;打印机市场呈现下滑趋势。根据鲸参谋平台的数据可知&#xff0c;当月京东平台打印机的销量为48万&#xff0c;环比下降约28%&#xff0c;同比下降约18%&#xff1b;销售额为4亿&#xff0c;环…

【云原生】Kubernetes容器编排工具

目录 1. K8S介绍 1.1 k8s的由来 下载地址 1.2 docker编排与k8s编排相比 1.3 传统后端部署与k8s 的对比 传统部署 k8s部署 ​2. k8s的集群架构与组件 &#xff08;1&#xff09; Kube-apiserver &#xff08;2&#xff09;Kube-controller-manager &#xff08;3&a…

(数字图像处理MATLAB+Python)第十一章图像描述与分析-第三、四节:几何表述和形状描述

文章目录 一&#xff1a;几何描述&#xff08;1&#xff09;像素间几何关系A&#xff1a;邻接与连通B&#xff1a;距离 &#xff08;2&#xff09;像素间几何特征A&#xff1a;位置B&#xff1a;方向C&#xff1a;尺寸 &#xff08;3&#xff09;程序 二&#xff1a;形状描述&a…

SPI3+DMA外设驱动-TFTLCD初始化

前言 &#xff08;1&#xff09;本系列是基于STM32的项目笔记&#xff0c;内容涵盖了STM32各种外设的使用&#xff0c;由浅入深。 &#xff08;2&#xff09;小编使用的单片机是STM32F105RCT6&#xff0c;项目笔记基于小编的实际项目&#xff0c;但是博客中的内容适用于各种单片…