专栏首页程序员的成长之路【153期】面试官:谈谈常用的Arraylist和Linkedlist的区别

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

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>

本文分享自微信公众号 - 程序员的成长之路(cxydczzl),作者:戳一戳→

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 经典面试题-ArrayList、LinkedList和Vector的区别

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • www6662016com请拨18687679362_环球国际常见Java面试题解析

    金三银四马上要来了,整理了Java一些经典面试题,也给出了答案,希望对大家有帮助,有哪里你觉得不正确的话,欢迎指出,非常感谢。

    用户7106032
  • 【Python面试】谈谈对 Python3 和 Python2 的区别?​

    小猿会从最基础的面试题开始,每天一题。如果参考答案不够好,或者有错误的话,麻烦大家可以在留言区给出自己的意见和讨论,大家是要一起学习的 。

    程序IT圈
  • 二本本科秋招无实习 | 上岸滴滴京东58科大讯飞复盘(中)

    我面过的那些公司目前没有遇到过群面,最多遇到对面的面试官是 HR+N 个技术一起问问题的,小事,hold 住他,不要紧张,慢慢来,自信点。

    Java宝典
  • 面试总结——Java高级工程师(二)

    时运不济,才到16年10月份,公司资金紧张,不得已又出去面试,面试了大概四家公司,只有一家offer ,被打击的体无完肤。 多说无益,下面是面试中提到的面试题和...

    执笔记忆的空白
  • ArrayList、LinkedList 你真的了解吗?

    经常在面试时,被问到集合的概念,集合 List、Map、Set 等底层设计以及其使用场景与注意细节。但大部分人的回答都是千篇一律,跟网上的答案一模一样,这是致命...

    程序猿Damon
  • java每日一练(2017/8/7)

    本期题目: (单选题) 1、如果子类要调用父类的构造函数,则通过super()调用来实现。 A 正确 B 错误 ---- (单选题) 2、ArrayList和...

    Java学习
  • 2019年Java面试题:谈谈springmvc和struts2的区别

    目前企业中使用SpringMvc的比例已经远远超过Struts2,那么两者到底有什么区别,是很多初学者比较关注的问题。

    葆宁
  • 最新BAT的实习面经

    6. 数据库:事务的概念,索引,B+树讲了一下。可能我回答的太不规范,然后也说了自己忘了数据库的知识了,于是就没往下问

    好好学java

扫码关注云+社区

领取腾讯云代金券