文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java面试岗常见问题之ArrayList和LinkedList的区别

2024-04-02 19:55

关注

1.ArrayList和LinkedList是什么?

在我看来,要想搞清楚ArrayList和LinkedList有什么区别,首先一定得要知道这两个东西到底是什么。因为在我看来,通常拿来被比较有区别的东西,它们大体上一定存在很多相似的地方。为了剖析本质,我们直接看看它们的源码声明。

 Arraylist:

 LinkedList:

可以看出ArrayList和LinkedList都是List接口下的实现类,而List接口可以说是集合类中最常用的接口了,它是一个元素有序、可以重复、可以为null的集合。而且List接口的元素,都可以直接通过下标索引获取。既然如此,那么说明ArrayList和LinkedList都具有上述的功能,那他们使用起来的效率到底有什么区别呢?

2.ArrayList和LinkedList性能比较               

1.插入效率比较

因为上面我们已经提到过这两者都是主要用来存储元素的集合类,那我们可以使用较大的数据量,来测试一下它们插入的效率如何      


//插入到头部
public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
 
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list1.add(0,i);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list2.add(0,i);
        }
        long time3 = System.currentTimeMillis();
        //ArrayList的插入时间
        System.out.println(time2-time1);//58746
        //LinkedList的插入时间
        System.out.println(time3-time2);//124
    }

     //插入到尾部
     public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
 
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list1.add(i);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list2.add(i);
        }
        long time3 = System.currentTimeMillis();
        //ArrayList的插入时间
        System.out.println(time2-time1);//23
        //LinkedList的插入时间
        System.out.println(time3-time2);//140
    }

大家发现没有,当插入100万个元素到头部时,LinkedList的速率竟然是ArrayList五千倍之多,当我们插入100万个元素到尾部时,但是又发现ArrayList的速率比LinkedList还快,这是为什么呢?

其实做这个实验,是为了打消许多人的误区——LinkedList的插入效率一定比ArrayList要高。没错,理论上确实是如此,因为Arraylist的底层是数组实现,而LinkedList的底层为双向链表。在初学数据结构时链表的插入效率高于数组这是我们就学习过的知识,可实际上在这里其实当数据量越来越大时,ArrayList的插入和删除效率是比LinkedList越来越高的,这涉及到数组和链表在元素操作上的问题。但其实在元素量较少时,两者的效率几乎所差无几。        

2.查询效率比较

我们向ArrayList和LinkedList同时插入10万条数据,然后去索引每个下标,测试一下两者的查询效率如何        


 public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百万个元素
        for (int i = 0; i < 100000; i++) {
            list1.add(i);
            list2.add(i);
        }
        long time1 = System.currentTimeMillis();
        for (int i = 0; i <list1.size() ; i++) {
            list1.get(i);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 0; i <list2.size() ; i++) {
            list2.get(i);
        }
        long time3 = System.currentTimeMillis();
        System.out.println(time2-time1);//1
        System.out.println(time3-time2);//5479
    }

从测试的结果来看,并没有出乎我们的意外,因为ArrayList的底层为数组实现,对于任何一个下标的索引都是O(1)的时间复杂度。而LinkedList的底层为双向链表,对于查询索引需要从头部或者尾部去遍历找到下标。   

3.删除效率比较

我们同样向ArrayList和LinkedList放入100万个元素,然后同样测试从头部删除和从尾部删除有什么区别,来测试一下他们的删除效率。

从尾部删除:


public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百万个元素
        for (int i = 0; i < 1000000; i++) {
            list1.add(i);
            list2.add(i);
        }
        long time1 = System.currentTimeMillis();
        for (int i = 1000000; i >0 ; i--){
            list1.remove(i-1);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 1000000; i >0 ; i--) {
            list2.remove(i-1);
        }
        long time3 = System.currentTimeMillis();
        //ArrayList的删除时间
        System.out.println(time2-time1);//8
        //LinkedList的删除时间
        System.out.println(time3-time2);//18
    }

从头部删除:


public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        //先放入一百万个元素
        for (int i = 0; i < 1000000; i++) {
            list1.add(i);
            list2.add(i);
        }
        long time1 = System.currentTimeMillis();
        for (int i = 1000000; i >0 ; i--){
            list1.remove(0);
        }
        long time2 = System.currentTimeMillis();
        for (int i = 1000000; i >0 ; i--) {
            list2.remove(0);
        }
        long time3 = System.currentTimeMillis();
        System.out.println(time2-time1);//55962
        System.out.println(time3-time2);//14
    }

       大家发现了吗,从尾部删除的时候,ArrayList的速度比LinkedList快,而从头部删除后,ArrayList就不知道被LinkedList甩了几条街去了。其实删除同插入其实是一样的,再次实践一次是想让大家加深印象,能走出误区。

4.实验总结

       之所以会做这几个实验,不仅仅是为了让大家更加深刻的去认识ArrayList和LinkedList,也是想让大家走出一些误区,比如什么LinkedList插入删除一定比ArrayList快啊,ArrayList查询一定比LinkedList快啊,从理论上来说确实如此,但通过实验以后,我们应该这样表达:

       1.在数据量不大时,ArrayList和LinkedList的查询效率其实所差无几,只有在数据量较大时,ArrayList会对比出优势

       2.在插入和删除上,LinkedList并不一定ArrayList效率更好,这与数据量以及插入和删除的位置都是有关系的        

3.面试标准回答

       1.ArrayList底层为数组实现,LinkedList底层为双向链表实现。ArrayList只能作为列表使用,LinkedList还能作为队列,因为实现了Deque接口。

       2.LinkedList在数组中的开销更大,因为它不仅需要存储元素,还需要保存前后结点的地址,而ArrayList更加轻量级。

       3. 在插入和删除效率上,理论上LinkedList优于ArrayList,但这还与数据量与处理的位置有关系,但查询的效率上ArrayList更占有优势   

如果兄弟们在实际使用时实在纠结用哪个,那就无脑使用Arraylist吧,别问,问就是它更好用!      

到此这篇关于Java面试岗常见问题之ArrayList和LinkedList的区别的文章就介绍到这了,更多相关Java ArrayList和LinkedList的区别内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯