【面试:基础篇07:ArrayList与LinkedList源码分析及其性能对比】

简介: 【面试:基础篇07:ArrayList与LinkedList源码分析及其性能对比】

【面试:基础篇07:ArrayList与LinkedList源码分析及其性能对比】

01.简介

我们知道ArrayList是基于数组创建的,LinkedList是基于链表创建的,那么程序是如何判断并运行他们的呢,他们之间的性能对比又是怎么样的。

02.源码比较

ArrayList

我们查看ArrayList的源码

这里面==RandomAccess==接口值得我们注意,查看RandomAccess

我们发现RandomAccess接口没有任何内容

LinkedList

我们查看LinkedList的源码

我们发现LinkedList并没有实现RandomAccess接口

分析:

我们发现了 ArrayList源码中实现了RandomAccess接口,但是LinkedList并没有实现它。

我们可以看到RandomAccess没有任何内容,它仅仅是作为ArrayList与LinkedList区分标记

如果实现了RandomAccess 则说明是ArrayList 程序会按照下标+1去寻值,如果没有实现则说明是LinkedList 程序就会按照指针寻址寻值

03.ArrayList性能与LinkedList性能对比

ArrayList与LinkedList的查性能对比:

代码:

public static void main(String[] args) {
    int n = 1000;

    for (int i=0;i<5;i++){
        int[] list = new int[1000];
        for (int j=0;j<n;j++){
            list[j]= (int) (Math.random()*n);
        }
        // 把list数组的值存入 ArrayList与LinkedList
        ArrayList<Integer> array = (ArrayList<Integer>) Arrays.stream(list).boxed().collect(Collectors.toList());
        LinkedList<Integer> Linked = new LinkedList<>(array);
        //查性能
        randomAccess(array,Linked,n/2);
        // 插头部性能
        //            addFirst(array,Linked);
        // 插尾部性能
        //            addLast(array,Linked);
        // 插中间性能
        //            addMiddle(array,Linked,n/2);
    }
}
// 获取ArrayLis与LinkedList的查方法 执行时间
private static void randomAccess(ArrayList<Integer> array, LinkedList<Integer> linked, int mid) {
    StopWatch sw = new StopWatch();// spring的StopWatch类 用于获取程序执行时间
    sw.start("ArrayList");
    array.get(mid);
    sw.stop();

    sw.start("LinkedList");
    linked.get(mid);
    sw.stop();

    System.out.println(sw.prettyPrint());
}

结果

000005900 023% ArrayList
000020100 077% LinkedList

000001200 013% ArrayList
000007700 087% LinkedList

000001300 010% ArrayList
000011600 090% LinkedList

000001500 013% ArrayList
000010300 087% LinkedList

000001000 011% ArrayList
000008200 089% LinkedList

可以看出查的时候 ArrayList的速度明显比LinkedList要快的多

ArrayList与LinkedList的增性能对比:

因为增与删运行路径差不多 故我们只比较增方法

头部插入代码

public static void main(String[] args) {
    int n = 1000;

    for (int i=0;i<5;i++){
        int[] list = new int[1000];
        for (int j=0;j<n;j++){
            list[j]= (int) (Math.random()*n);
        }
        ArrayList<Integer> array = (ArrayList<Integer>) Arrays.stream(list).boxed().collect(Collectors.toList());
        LinkedList<Integer> Linked = new LinkedList<>(array);
        //查性能
        //             randomAccess(array,Linked,n/2);
        // 插头部性能
        addFirst(array,Linked);
        // 插尾部性能
        //            addLast(array,Linked);
        // 插中间性能
        //            addMiddle(array,Linked,n/2);
    }
}
private static void addFirst(ArrayList<Integer> array,LinkedList<Integer> linked){
    StopWatch sw = new StopWatch();
    sw.start("ArrayList");
    array.add(0,100);
    sw.stop();

    sw.start("LinkedList");
    linked.addFirst(100);
    sw.stop();

    System.out.println(sw.prettyPrint());
}

结果

000046500 072% ArrayList
000018400 028% LinkedList

000003700 073% ArrayList
000001400 027% LinkedList

000004200 078% ArrayList
000001200 022% LinkedList

000004300 077% ArrayList
000001300 023% LinkedList

000005000 078% ArrayList
000001400 022% LinkedList

我们可以看出在往头部插入数据时,LinkedList的速度明显优于ArrayList

尾部插入代码

public static void main(String[] args) {
    int n = 1000;

    for (int i=0;i<5;i++){
        int[] list = new int[1000];
        for (int j=0;j<n;j++){
            list[j]= (int) (Math.random()*n);
        }
        ArrayList<Integer> array = (ArrayList<Integer>) Arrays.stream(list).boxed().collect(Collectors.toList());
        LinkedList<Integer> Linked = new LinkedList<>(array);
        //查性能
        //             randomAccess(array,Linked,n/2);
        // 插头部性能
        //            addFirst(array,Linked);
        // 插尾部性能
        addLast(array,Linked);
        // 插中间性能
        //            addMiddle(array,Linked,n/2);
    }
}
private static void addLast(ArrayList<Integer> array,LinkedList<Integer> linked){
    StopWatch sw = new StopWatch();
    sw.start("ArrayList");
    array.add(100);
    sw.stop();

    sw.start("LinkedList");
    linked.add(100);
    sw.stop();

    System.out.println(sw.prettyPrint());
}

结果

000010400 066% ArrayList
000005300 034% LinkedLis

000001100 050% ArrayList
000001100 050% LinkedList

000001100 055% ArrayList
000000900 045% LinkedList

000001200 043% ArrayList
000001600 057% LinkedList

000001200 050% ArrayList
000001200 050% LinkedList

可以看出在尾部插入时 ArrayList的速度与LinkedList的速度差不多

中间插入代码

==注意==:在大家刚学链表时一定听过 数组查询块增删慢,链表查询慢增删快,但事实可能不是这样的

public static void main(String[] args) {
    int n = 1000;

    for (int i=0;i<5;i++){
        int[] list = new int[1000];
        for (int j=0;j<n;j++){
            list[j]= (int) (Math.random()*n);
        }
        ArrayList<Integer> array = (ArrayList<Integer>) Arrays.stream(list).boxed().collect(Collectors.toList());
        LinkedList<Integer> Linked = new LinkedList<>(array);
        //查性能
        //             randomAccess(array,Linked,n/2);
        // 插头部性能
        //            addFirst(array,Linked);
        // 插尾部性能
        //            addLast(array,Linked);
        // 插中间性能
        addMiddle(array,Linked,n/2);
    }
}
private static void addMiddle(ArrayList<Integer> array,LinkedList<Integer> linked,int mid){
    StopWatch sw = new StopWatch();
    sw.start("ArrayList");
    array.add(mid,100);
    sw.stop();

    sw.start("LinkedList");
    linked.add(mid,100);
    sw.stop();

    System.out.println(sw.prettyPrint());
}

结果

000031800 040% ArrayList
000047300 060% LinkedList

000003600 023% ArrayList
000011900 077% LinkedList

000003000 016% ArrayList
000015300 084% LinkedList

000006600 024% ArrayList
000020600 076% LinkedList

000005800 015% ArrayList
000032300 085% LinkedList

我们可以惊讶的看到ArrayList的速度明显优于LinkedList,这与我们的认知是不一样的。

04.ArrayList VS LinkedList

它们的优劣对比:

1.在查情况下明显 ArrayList要优于LinkedList

2.在头插入时LinkedList要优于ArrayList

3.在尾插入时ArrayList和LinkedList差不多

4.在中间插入时ArrayList要优于LinkedList,原因也非常简单,因为如果要插入则一定要查询 很明显ArrayList查询要快于LinkedList,虽然ArrayList在插入时 会往后整体移动数组,但还是优于LinkedList的查询速度

补充:缓存一致性原理

我们的cpu直接读写内存数据速度很慢 所有我们通常采用把数据存入缓存 再由cpu读写,而缓存采用的策略是缓存一致性原理:把数据需要的数据的相邻地址也存入缓存 ,例如一个数组是 {1 2 3 4 5 6} 现在我们想要读写1,则会把2 3 4也放入缓存 这样的好处是我们如果读写1 大概率也会读写 2 3 4 所以更能加快读写速度,对于ArrayList来说可以完美适应缓存一致性原理,但对于LinkedList来说 它是又链表实现的 所以相邻地址不同 不能完美的适应缓存一致性 导致同样的读写操作 ArrayList速度更快。

综上

我们大多数情况应该采用ArrayList,它的增删改查操作大多数情况都优于LinkedList。
目录
相关文章
|
1月前
|
消息中间件 存储 Java
招行面试:10Wqps场景,RocketMQ 顺序消费 的性能 如何提升 ?
45岁资深架构师尼恩在其读者群中分享了关于如何提升RocketMQ顺序消费性能的高并发面试题解析。面对10W QPS的高并发场景,尼恩详细讲解了RocketMQ的调优策略,包括专用方案如增加ConsumeQueue数量、优化Topic设计等,以及通用方案如硬件配置(CPU、内存、磁盘、网络)、操作系统调优、Broker配置调整、客户端配置优化、JVM调优和监控与日志分析等方面。通过系统化的梳理,帮助读者在面试中充分展示技术实力,获得面试官的认可。相关真题及答案将收录于《尼恩Java面试宝典PDF》V175版本中,助力求职者提高架构、设计和开发水平。
招行面试:10Wqps场景,RocketMQ 顺序消费 的性能 如何提升 ?
|
1月前
|
人工智能 自然语言处理 架构师
字节面试: es怎么提升性能和精准度?(尼恩独家,史上最全)
本文由40岁老架构师尼恩撰写,针对ES(Elasticsearch)提升搜索性能和精准度的面试题进行详细解析。文章首先指出,提升ES速度和精准度是两个独立的问题,分别涉及性能优化和精准度优化。这些内容不仅有助于应对面试中的难题,还能帮助开发者在实际项目中构建更高效的搜索系统。尼恩强调,掌握这些知识后可以在面试中“吊打”面试官,轻松获得理想Offer。同时,他还提供了《尼恩Java面试宝典PDF》等资源供读者学习参考。
|
6月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
6月前
|
存储 Java 索引
【Java集合类面试二十四】、ArrayList和LinkedList有什么区别?
ArrayList基于动态数组实现,支持快速随机访问;LinkedList基于双向链表实现,插入和删除操作更高效,但占用更多内存。
|
5月前
|
设计模式 Java 关系型数据库
【Java笔记+踩坑汇总】Java基础+JavaWeb+SSM+SpringBoot+SpringCloud+瑞吉外卖/谷粒商城/学成在线+设计模式+面试题汇总+性能调优/架构设计+源码解析
本文是“Java学习路线”专栏的导航文章,目标是为Java初学者和初中高级工程师提供一套完整的Java学习路线。
532 37
|
7月前
|
存储 安全 Java
面试官没想到一个ArrayList,我都能跟他扯半小时
面试官:List集合都知道哪些对象?作为四大集合之一的List,在业务开发中我们比较常见的是以下 3 种:ArrayList、Vector、LinkedList,业务开发我们接触最多就是容器类库了,容器类库可以说是面向对象语言最重要的类库。大家看看在工作里你比较熟悉的是哪个?这篇文章南哥打算专注于List集合,后面四大集合之Map、Queue、Set后续再来填坑,比心心♥。
144 2
面试官没想到一个ArrayList,我都能跟他扯半小时
|
6月前
|
缓存 NoSQL Redis
一天五道Java面试题----第九天(简述MySQL中索引类型对数据库的性能的影响--------->缓存雪崩、缓存穿透、缓存击穿)
这篇文章是关于Java面试中可能会遇到的五个问题,包括MySQL索引类型及其对数据库性能的影响、Redis的RDB和AOF持久化机制、Redis的过期键删除策略、Redis的单线程模型为何高效,以及缓存雪崩、缓存穿透和缓存击穿的概念及其解决方案。
|
6月前
|
存储 SQL 搜索推荐
一天十道Java面试题----第一天(面向对象-------》ArrayList和LinkedList)
这篇文章是关于Java面试的笔记,涵盖了面向对象、JDK/JRE/JVM的区别、`==`和`equals`、`final`关键字、`String`、`StringBuffer`和`StringBuilder`的区别、重载与重写、接口与抽象类、`List`与`Set`、`hashcode`与`equals`以及`ArrayList`和`LinkedList`的对比等十个主题。
|
6月前
|
运维 监控 算法
[go 面试] 优化线上故障排查与性能问题的方法
[go 面试] 优化线上故障排查与性能问题的方法
|
3月前
|
存储 缓存 算法
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!