专栏首页关忆北.从源码分析常见集合的区别之List接口

从源码分析常见集合的区别之List接口

说到Java集合,大家肯定脱口而出List、Set、Map,(想不出来的请自行面壁),今天就详细聊聊大家耳熟能详的List吧。

List接口实现自Collection接口,是Java的集合框架中的一员,List接口下又有ArrayListLinkedList和线程安全的Vector,今天就简单分析一下ArrayListLinkedList的异同以及各自的优势。

ArrayList

引用ArrayList集合中的一段注释:

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

可见,ArrayList是底层实现是一个可变长度的Object类型的数组,当我们给list插入数据时,就会调用ArrayList的add方法,根据Java提供的看不懂的add方法注解来看,当ArrayList插入数据时,是在ArrayList的尾部进行插入,调用ensureCapacityInternal方法使链表长度+1

ensureCapacityInternal方法会检测自身容量,当链表长度大于ArrayList的默认长度时,ArrayList就会调用grow方法进行扩容

你们就不好奇ArrayList的默认长度是多少吗?emmm,这好像是一个冷知识,好吧,我们就new一个对象插入几个元素试试,下断点瞅瞅吧,下边是我写的测试代码,再下边是见证奇迹的时刻! ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 1; i <= 2000000; i++) { list.add(i); } list.forEach(System.out::println); //关于lambda表达式,见仁见智吧,我觉得是个好东西 看到刚刚的Math.max没,没看到的翻上去看,显而易见,这个三目运算符,似乎暴露了什么,嗯,ArrayList的默认长度是10。划重点,这个地方可能会考。

继续往下走无聊的断点,那根据Java的意思,就是当list的长度超过10的时候就会调用grow方法进行扩容 如果面试官问你:怎么看待ArrayList和LinkedList各自的特性,怎么看?看源码呗。

以我80多年考专八的丰富经验,grow方法就是要确保ArrayList的容量要足够你的用的,以免送你一个数组越界的异常,回归正题,当面试官问你ArrayList、LinkedList的特性时,你会不假思索的“背”出来:ArrayList擅长查询,其查询的时间是一定的,增删慢,LinkedList与ArrayList相反,如果你知道这些,恭喜你,你大学可以毕业了,因为我毕业的时候就知道这个(我谨代表广大毕业生的最低水平),哪为什么ArrayList在插入元素的时候慢呢,看源码: // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); 你品,你细品,Arrays.copyOf....,嗯,是不是这样就真相了,ArrayList在扩容的时候会把原来的数组复制到另一个内存空间更大的数组中,然后把新元素添加到扩容以后的数组中。所以喽,你不慢谁慢。 哪ArrayList为啥查询快呢?

人家通过下标查找,为啥不快,没有理由啊,你说对吧。不过,在查找的时候小心IndexOutOfBoundsException,他这个异常可不是闹着玩的。

LinkedList

小朋友,你是否有很多问号?为什么,LinkedList插入快?

LinkedList是一个由相互引用的节点组成的双向链表,那么当把数据插入至该链表某个位置时,该数据就会被组装成一个新的节点,随后只需改变链表中对应的两个节点之间的引用关系,使它们指向新节点,即可完成插入。

测试:贴代码

talk is cheap,show me your code.

ArrayList

public class List {
    public void array(){
        Scanner sc=new Scanner(System.in);
        int test = sc.nextInt();
        long start = System.currentTimeMillis(); //获取当前时间
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= test; i++) {
            list.add(i);
        }
        list.forEach(System.out::println);
        long end = System.currentTimeMillis();       // 记录结束时间
        System.out.println(end-start);
    }

    public static void main(String[] args) {
        List list = new List();
        list.array();
    }

}

LinkedList

public class Link {
    public void link(){
        Scanner sc=new Scanner(System.in);
        int test = sc.nextInt();
        long start = System.currentTimeMillis(); //获取当前时间
        LinkedList<Integer> link = new LinkedList();
        for (int i = 1; i <= test; i++) {
            link.add(i);
        }
        link.forEach(System.out::println);
        long end = System.currentTimeMillis();       // 记录结束时间
        System.out.println(end-start);
    }

    public static void main(String[] args) {
        Link link = new Link();
        link.link();
    }

}

总结

ArrayListLinkedList的快慢只是一个相对的,通过看LinkedList源码不难发现,LinkedList在插入数据的时候,会new一个Node节点,新建对象也是一种消耗资源的操作,所以,在数据量较小的时候,如插入500万以上的数据时,ArrayList的速度更快一些,一般情况下我们一般不会同时插入百万级的数据,所以一般都说

ArrayList插入遍历快,增删慢,LinkedList增删快,插入慢。两者皆没有线程安全做处理,而Vector的方法由synchronized关键字修饰所以Vector是线程安全的List。

完结撒花。

代码我会同步在Github,欢迎访问:

我的Github

我们站在巨人的肩膀上,文章参考了

https://blog.csdn.net/xu962336414/article/details/84032693

https://blog.csdn.net/qq_34144916/article/details/81154528?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://blog.csdn.net/weixin_42313773复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • Carson带你学Java:那些关于集合的知识都在这里了!

    在本节中,会先介绍Collection接口,再介绍其具体集合实现类(List、Set、Queue类)

    Carson.Ho
  • Java:那些关于集合的知识都在这里了!

    在本节中,会先介绍Collection接口,再介绍其具体集合实现类(List、Set、Queue类)

    Carson.Ho
  • 数据结构

    队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。

    后端码匠
  • 2019 最新 Java 核心技术教程,都在这了!

    以下是Java技术栈微信公众号发布的所有关于 Java 的技术干货,会从以下几个方面汇总,本文会长期更新。

    Java技术栈
  • Java集合框架常见面试题

    从下图可以看出,在 Java 中除了以 Map 结尾的类之外, 其他类都实现了 Collection 接口。

    Vincent-yuan
  • 01 详析一次腾讯一面 | 移动端开发岗

    URL realUrl = new URL(url); HttpURLConnection conn = (Htt...

    凌川江雪
  • 全面&详细的面试指南:Java语言篇 (附答案)

    关于上述Java集合的所有内容介绍,具体请看文章:Carson带你学Java:那些关于集合的知识都在这里了!

    Carson.Ho
  • 起飞了!Git新开源高星《Flutter跨平台开发入门与实战笔记》安卓高阶必备

    有了Flutter,就有了几乎无穷无尽的可能性,因此即使是体量巨大的App也可以轻松地被创建出来。如果你是做移动App开发的并且尚未尝试过Flutter,我强烈...

    用户1907613
  • Android 进阶之路(我的博客文章目录)

    版权声明:转载前请留言获得作者许可,转载后标明作者 张拭心 与 原文链接。大家都是成年人,创作不易,感谢您的支...

    张拭心 shixinzhang
  • 助力秋招-独孤九剑荡剑式 | Java语言&基础面试题

    https://blog.csdn.net/sufu1065/article/details/88051083

    王知无-import_bigdata
  • Java容器(List、Set、Map)知识点快速复习手册(下)

    http://wiki.jikexueyuan.com/project/java-collection/hashset.html

    Rude3Knife的公众号
  • 【Java核心面试宝典】Day2、谈一谈List接口的实现?

    在Java的相关面试中,集合相关的内容问到的还是比较多的,一般都是List接口及常见实现,Map接口及常见实现和Set接口及常见实现,其中最经常问到的要数Map...

    灰小猿
  • 后台开发常问面试题集锦(问题搬运工,文末附问题链接)

    Synchronized(对象锁)和Static Synchronized(类锁)的区别

    Java架构技术
  • java集合,Collection,list,set,map汇总

    Java是一门面向对象的语言,就免不了处理对象,为了方便操作多个对象,那么我们就得把这多个对象存储起来,想要存储多个对象(变量),很容易就能想到一个容器(集合)...

    用户8870853
  • 集合前篇—List 源码分析

    这里的博客都是笔者初学时写下,一段时间后有其他的理解就再次回来修订 所以排版,文字,图片会有错乱,但重写一篇太过耗费时间,所以只能修修补补又重发

    晚上没宵夜
  • JDK源码分析-List, Iterator, ListIterator

    List 是最常用的容器之一。之前提到过,分析源码时,优先分析接口的源码,因此这里先从 List 接口分析。List 方法列表如下:

    WriteOnRead
  • 「Java面试题精华集」1w字的Java集合框架篇(2020最新版)附PDF版 !

    一个多月前,我和一些小伙伴决定做一系列的 Java 知识点常见重要问题的小册,方便用来夯实基础!小册的标准就一个,那就是:取精华,取重点。每一本小册,我们都会充...

    Guide哥
  • 各大厂都在考的 Java 集合知识点总结,不来看看???

    Java 集合类主要都是从 Collection 和 Map 两个接口派生而成,其中 Collection 又包含 List、Set 和 Queue,如下图。J...

    村雨遥

扫码关注腾讯云开发者

领取腾讯云代金券