【153期】面试官——谈谈常用的Arraylist和Linkedlist的区别

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 【153期】面试官——谈谈常用的Arraylist和Linkedlist的区别

点击上方“Java面试题精选”,关注公众号

面试刷图,查缺补漏

号外:往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅

阶段汇总集合:

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扩容:

【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别

Arraylist添加数据:(向数组尾部添加)

【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别

向数组的指定位置添加数组:

【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别

可以看到,只要ArrayList的当前容足够大,add()操作向数组的尾部的效率非常高的,当向数组指定位置添加数据时,会进行大量的数组移动复制操作。而数组复制时,最终将调用System.arraycopy()方法,因此add()操作的效率还是相当高的。往期:

尽管这样当向指定位置添加数据时也还是比Linkedlist慢,后者添加数据只需要改变指针指向即可。Arraylist删除数组也需要移动数组,效率较慢。

Linkedlist基于链表的动态数组,数据添加删除效率高,只需要改变指针指向即可,但是访问数据的平均效率低,需要对链表进行遍历。

Arraylist get数据的源码:(根据下标访问,效率高)

【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别

Linkedlist访问数据的源码:(node()函数遍历链表)

【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别 【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别

总结:

1、对于随机访问get和set,ArrayList优于LinkedList,因为LinkedList要移动指针。对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。

2、各自效率问题:

【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别

来源:blog.csdn.net/weixin_42468526/article/details/81178698

与其在网上拼命找题?** 不如马上关注我们~**

【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别

原文始发于微信公众号(Java面试题精选):

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 【153期】面试官——谈谈常用的Arraylist和Linkedlist的区别


 上一篇
【151期】谈谈 ZooKeeper 的定位——能解决什么问题?不能解决什么问题? 【151期】谈谈 ZooKeeper 的定位——能解决什么问题?不能解决什么问题?
点击上方“Java面试题精选”,关注公众号 面试刷图,查缺补漏 号外:往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅 阶段汇总集合: 目标ZooKeeper 很流行,有个基本的疑问: ZooKeeper 是用来
2021-04-05
下一篇 
【154期】面试官——你能说说 Elasticsearch 查询数据的工作原理是什么吗? 【154期】面试官——你能说说 Elasticsearch 查询数据的工作原理是什么吗?
点击上方“Java面试题精选”,关注公众号 面试刷图,查缺补漏 号外:往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅 阶段汇总集合: 面试题ES 写入数据的工作原理是什么啊?ES 查询数据的工作原理是什么啊?底层
2021-04-05