技术圈首页
程序员
解决方案
聚合短信
APP下载
登录
注册
首页
文章详情
【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别
程序员的成长之路
|
369
2021-03-14 00:10
0
0
0
程序员的成长之路
互联网/程序员/技术/资料共享
关注
阅读本文大概需要 2 分钟。
来自:
blog.csdn.net/weixin_42468526/article/details/81178698
Arraylist:底层是基于动态数组,根据下表随机访问数组元素的效率高,向数组尾部添加元素的效率高;但是,删除数组中的数据以及向数组中间添加数据效率低,因为需要移动数组。
例如最坏的情况是删除第一个数组元素,则需要将第2至第n个数组元素各向前移动一位。而之所以称为动态数组,是因为Arraylist在数组元素超过其容量大,Arraylist可以进行扩容(针对JDK1.8 数组扩容后的容量是扩容前的1.5倍),Arraylist源码中最大的数组容量是Integer.MAX_VALUE-8。
对于空出的8位,目前解释是 :①存储Headerwords;②避免一些机器内存溢出,减少出错几率,所以少分配③最大还是能支持到Integer.MAX_VALUE(当Integer.MAX_VALUE-8依旧无法满足需求时)。
以下是Arraylist部分源码:
Arraylist扩容:
Arraylist添加数据:(向数组尾部添加)
向数组的指定位置添加数组:
可以看到,只要ArrayList的当前容足够大,add()操作向数组的尾部的效率非常高的,当向数组指定位置添加数据时,会进行大量的数组移动复制操作。而数组复制时,最终将调用System.arraycopy()方法,因此add()操作的效率还是相当高的。
尽管这样当向指定位置添加数据时也还是比Linkedlist慢,后者添加数据只需要改变指针指向即可。Arraylist删除数组也需要移动数组,效率较慢。
Linkedlist基于链表的动态数组,数据添加删除效率高,只需要改变指针指向即可,但是访问数据的平均效率低,需要对链表进行遍历。
Arraylist get数据的源码:(根据下标访问,效率高)
Linkedlist访问数据的源码:(node()函数遍历链表)
总结:
1、对于随机访问get和set,ArrayList优于LinkedList,因为LinkedList要移动指针。对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
2、各自效率问题:
<END>
推荐阅读:
【152期】面试官:你能说出MySQL主从复制的几种复制方式吗?
【151期】谈谈 ZooKeeper 的定位:能解决什么问题?不能解决什么问题?
【150期】面试官:Redis的各项功能解决了哪些问题?
5T技术资源大放送!包括但不限于:C/C++,Linux,Python,Java,PHP,人工智能,单片机,树莓派,等等。在公众号内回复「
2048
」,即可免费获取!!
微信扫描二维码,关注我的公众号
朕已阅
0
赞
0
收藏
×
添加附言
附加内容, 使用此功能的话, 会给所有参加过讨论的人发送提醒.
回复数量:
0
暂无评论~~
请注意单词拼写,以及中英文排版,
参考此页
支持 Markdown 格式,
**粗体**
、~~删除线~~、
`单行代码`
, 更多语法请见这里
Markdown 语法
支持表情,见
Emoji cheat sheet
@name 会链接到用户页面,并会通知他
上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jp(e)g, png, gif
Ctrl+Enter
下载APP
程序员的成长之路
1729
文章
0
获赞
关注TA
NEW
相关文章推荐
被Bug搞疯了?给你的应用嵌入一个Logcat吧
FFmpeg音频处理——音频混合、拼接、剪切、转码
视觉算法的工业部署及落地方面的技术知识,怎么学?
文件上传踩坑记及文件清理原理探究
STM32串口用中断还是用轮询
windows 10编译YOLOv4,包括exe和d
深度好文 | 超全SLAM技术及应用介绍
打造自己的内存泄漏检测工具