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

目录
  • 1.ArrayList和LinkedList是什么?
  • 2.ArrayList和LinkedList性能比较
    • 1.插入效率比较
    • 2.查询效率比较
    • 3.删除效率比较
    • 4.实验总结
  • 3.面试标准回答

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的区别内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java中ArrayList和LinkedList区别

    目录 1 前言 2 数据结构的区别 2.1 ArrayList 2.2 LinkedList 2.3 使用场景 3 源码分析 3.1 ArrayList核心源码 3.2 LinkedList核心源码 4 码农来洞见 4.1为什么ArrayList比LinkedList要快 4.2 注意ArrayList不同JDK版本源码 4.3 高并发下如何保证集合数据的同步 4.4 为什么Java的Vector类被认为是过时的或者废弃的 1 前言 许多语言,例如 Perl ,Python 和 Ruby ,都有

  • Java集合框架之List ArrayList LinkedList使用详解刨析

    目录 1. List 1.1 List 的常见方法 1.2 代码示例 2. ArrayList 2.1 介绍 2.2 ArrayList 的构造方法 2.3 ArrayList 底层数组的大小 3. LinkedList 3.1 介绍 3.2 LinkedList 的构造方法 4. 练习题 5. 扑克牌小游戏 1. List 1.1 List 的常见方法 方法 描述 boolean add(E e) 尾插 e void add(int index, E element) 将 e 插入到 inde

  • java 集合之实现类ArrayList和LinkedList的方法

    List 的方法列表 方法名 功能说明 ArrayList() 构造方法,用于创建一个空的数组列表 add(E e) 将指定的元素添加到此列表的尾部 get(int index) 返回此列表中指定位置上的元素 size() 返回此列表中的元素数 clear() 移除此列表中的所有元素 isEmpty() 如果此列表中没有元素,则返回true remove(int index) 移除此列表中指定位置上的元素 indextof(Object o) 返回此列表中首次出现的指定元素的索引,或如果此列表不

  • JAVA LinkedList和ArrayList的使用及性能分析

    第1部分 List概括List的框架图List 是一个接口,它继承于Collection的接口.它代表着有序的队列.AbstractList 是一个抽象类,它继承于AbstractCollection.AbstractList实现List接口中除size().get(int location)之外的函数.AbstractSequentialList 是一个抽象类,它继承于AbstractList.AbstractSequentialList 实现了"链表中,根据index索引值操作链表的全部函数

  • java中ArrayList和LinkedList的区别详解

    ArrayList和LinkedList都实现了List接口,有以下的不同点: 1.ArrayList是基于索引的数据接口,它的底层是数组.它可以以O(1)时间复杂度对元素进行随机访问.与此对应,LinkedList是以元素列表的形式存储它的数据,每一个元素都和它的前一个和后一个元素链接在一起,在这种情况下,查找某个元素的时间复杂度是O(n). 2.相对于ArrayList,LinkedList的插入,添加,删除操作速度更快,因为当元素被添加到集合任意位置的时候,不需要像数组那样重新计算大小或者

  • Java中ArrayList和LinkedList之间的区别_动力节点Java学院整理

    一.ArrayList ArrayList是一个可以处理变长数组的类型,这里不局限于"数"组,ArrayList是一个泛型类,可以存放任意类型的对象.顾名思义,ArrayList是一个数组列表,因此其内部是使用一个数组来存放对象的,因为Object是一切类型的父类,因而ArrayList内部是有一个Object类型的数组类存放对象.ArrayList类常用的方法有add().clear().get().indexOf().remove().sort().toArray().toStri

  • java中ArrayList与LinkedList对比详情

    ArrayList,LinkedList都是Collection接口的通用实现方式,两者采用了不用的存储策略,用来适应不同场合的需要. 实现方式 ArrayList的内部采用集合的方式存储数据 唯一需要注意的是对于容量超过阈值的处理逻辑,数组的默认容量大小是10,最大容量是Integer.Max_Value,超过最大容量会抛内存溢出异常, 扩容机制看下面 扩容后的容量是原有容量的1.5倍 LinkedList的实现方式 内部采用双向链表Node内部类来存储数据,由于采用了双向链表,LinkedL

  • 浅谈 java中ArrayList、Vector、LinkedList的区别联系

    以前面试的时候经常会碰到这样的问题.,叫你写一下ArrayList.LinkedList.Vector三者之间的区别与联系:原先一直搞不明白,不知道这三者之间到底有什么区别?哎,惭愧,基础太差啊,木有办法啊委屈 现在得去说说这三者之间的区别与联系了:这三者都是实现了List接口,都拥有List接口里面定义的方法,并且同时拥有Collection接口的方法: ArrayList:采用的是数组的方式进行存储数据的,查询和修改速度快,但是增加和删除速度慢:线程是不同步 LinkedList:采用的是链

  • java 中ArrayList与LinkedList性能比较

    java 中ArrayList与LinkedList性能比较 今天看一框架的代码,看到有些 可以使用ArrayList的地方 使用的是 LinkedList,用到的情景是在一个循环里面进行顺序的插入操作. 众所周知java里面List接口有两个实现ArrayList 和 LinkedList,他们的实现原理分别是c语言中介绍的数组和链表. 正如学习数据结构时的认识,对于插入操作,链表的结构更高效,原因是可以通过修改节点的指针 就可以完成插入操作, 而不像数组, 需要把插入位置之后的数组元素依次后

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

    目录 1.ArrayList和LinkedList是什么? 2.ArrayList和LinkedList性能比较 1.插入效率比较 2.查询效率比较 3.删除效率比较 4.实验总结 3.面试标准回答 1.ArrayList和LinkedList是什么? 在我看来,要想搞清楚ArrayList和LinkedList有什么区别,首先一定得要知道这两个东西到底是什么.因为在我看来,通常拿来被比较有区别的东西,它们大体上一定存在很多相似的地方.为了剖析本质,我们直接看看它们的源码声明. Arraylis

  • 当面试官问我ArrayList和LinkedList哪个更占空间时,我是这么答的(面试官必问)

    前言 今天介绍一下Java的两个集合类,ArrayList和LinkedList,这两个集合的知识点几乎可以说面试必问的. 对于这两个集合类,相信大家都不陌生,ArrayList可以说是日常开发中用的最多的工具类了,也是面试中几乎必问的,LinkedList可能用的少点,但大多数的面试也会有所涉及,尤其是关于这两者的比较可以说是家常便饭,所以,无论从使用上还是在面试的准备上,对于这两个类的知识点我们都要有足够的了解. ArrayList ArrayList是List接口的一个实现类,底层是基于数

  • java面试常问的Runnable和Callable的区别

    Runnable Runnable接口非常简单,就定义了一个方法run(), 实现Runnable接口的run方法就可以实现多线程 // 函数式接口 @FunctionalInterface public interface Runnable { public abstract void run(); } Callable 可能很多人都知道要想在多线程中获取异步返回值结果一般是用Callable和FutureTask接口来实现,但可能很多人都不知道其实Callable是依赖于Runnable的r

  • java面试突击之sleep和wait有什么区别详析

    目录 前言 区别一:语法使用不同 区别二:所属类不同 区别三:唤醒方式不同 区别四:释放锁资源不同 sleep不释放锁 wait释放锁 区别五:线程进入状态不同 总结 前言 sleep 方法和 wait 方法都是用来将线程进入休眠状态的,并且 sleep 和 wait 方法都可以响应 interrupt 中断,也就是线程在休眠的过程中,如果收到中断信号,都可以进行响应,并抛出 InterruptedException 异常.那 sleep 和 wait 的区别都有哪些呢?接下来,我们一起来看.

  • 浅谈ArrayList和LinkedList到底谁更快

    一.ArrayList和LinkedList究竟谁快 在Java中应该都知道ArrayList和LinkedList, 一直以来的概念呢是 ArrayList在get(index)这个应该比LinkedList快: LinkedList比ArrayList在add(index,element)快: 两者共同遍历呢,应该是一样快的,毕竟都要循环遍历一遍. 直到我写了一个测试类 package com.lw; import java.util.ArrayList; import java.util.

  • Java中ArrayList和LinkedList的遍历与性能分析

    前言 通过本文你可以了解List的五种遍历方式及各自性能和foreach及Iterator的实现,加深对ArrayList和LinkedList实现的了解.下面来一起看看吧. 一.List的五种遍历方式 1.for each循环 List<Integer> list = new ArrayList<Integer>(); for (Integer j : list) { // use j } 2.显示调用集合迭代器 List<Integer> list = new Ar

  • 区分Java中的ArrayList和LinkedList

    一:ArrayList和LinkedList的大致区别如下: 1.ArrayList是实现了基于动态数组的数据结构,ArrayList实现了长度可变的数组,在内存中分配连续的空间.遍历元素和随机访问元素的效率比较高 2.LinkedList基于链表的数据结构, 插入.删除元素时效率比较高  故:[插入.删除操作频繁时,可使用LinkedList来提高效率]LinkedList提供对头部和尾部元素进行添加和删除操作的方法,插入/删除第一个和最后一个效率比较高: 3:ArrayList和Linked

随机推荐