专栏首页JMCuiArrayList 和 LinkedList的执行效率比较

ArrayList 和 LinkedList的执行效率比较

一、概念:

    一般我们都知道ArrayList* 由一个数组后推得到的 List。作为一个常规用途的对象容器使用,用于替换原先的 Vector。允许我们快速访问元素,但在从列表中部插入和删除元素时,速度却嫌稍慢。一般只应该用ListIterator 对一个 ArrayList 进行向前和向后遍历,不要用它删除和插入元素;与 LinkedList 相比,它的效率要低许多LinkedList 提供优化的顺序访问性能,同时可以高效率地在列表中部进行插入和删除操作。但在进行随机访问时,速度却相当慢,此时应换用 ArrayList。

二、测试

    本来自己写了一些测试类想测试下ArrayList和LinkedList的性能比较,发现怎么写都差强人意,今天在《Thinking in Java》中看到了这样的一段代码,个人觉得写得不赖。

public class ListPerformance
{
    private static final int REPS = 100;

    private abstract static class Tester//内部抽象类,作为List测试。
    {
        String name;
        int size;

        Tester(String name, int size)
        {
            this.name = name;
            this.size = size;
        }

        abstract void test(List a);
    }

    private static Tester[] tests = {new Tester("get", 300)//一个测试数组,存储get(随机取)、iteration(顺序遍历)、insert(中间插入)、remove(随机删除)
    {
        void test(List a)
        {
            for (int i = 0; i < REPS; i++) {
                for (int j = 0; j < a.size(); j++) {
                    a.get(j);
                }
            }
        }
    }, new Tester("iteration", 300)
    {
        void test(List a)
        {
            for (int i = 0; i < REPS; i++) {
                Iterator it = a.iterator();
                while (it.hasNext()) it.next();
            }
        }
    }, new Tester("insert", 1000)
    {
        void test(List a)
        {
            int half = a.size() / 2;
            String s = "test";
            ListIterator it = a.listIterator(half);
            for (int i = 0; i < size * 10; i++) {
                it.add(s);
            }
        }
    }, new Tester("remove", 5000)
    {
        void test(List a)
        {
            ListIterator it = a.listIterator(3);
            while (it.hasNext()) {
                it.next();
                it.remove();
            }
        }
    },
                                     };

    public static void test(List a)
    {
        System.out.println("Testing " + a.getClass().getName());//输出测试的类名称
        for (int i = 0; i < tests.length; i++) {
            fill(a, tests[i].size);//填充空集合
            System.out.print(tests[i].name);
            long t1 = System.currentTimeMillis();
            tests[i].test(a);//进行测试
            long t2 = System.currentTimeMillis();
            System.out.print(":" + (t2 - t1)+" ms ");
        }
    }

    public static Collection fill(Collection c, int size)
    {
        for (int i = 0; i < size; i++) {
            c.add(Integer.toString(i));
        }
        return c;
    }

    public static void main(String[] args)
    {
        test(new ArrayList());
        System.out.println();
        test(new LinkedList());
    }

}

三、总结

    首先,真的夸一下,这段代码写得真是好啊,无论是内部类的应用还是对面向对象的认识,都考虑的恰到好处,哎,我什么时候才能写出这么棒的代码啊。

    测试结果每次都有些许的差异,但不难得出以下的结论:

        1、在 ArrayList 中进行随机访问(即 get())以及循环反复是最划得来的 。原因在于,ArrayList是基于数组而来的,所以每个元素都有其对应的index,所以随机定位一个元素要快捷的多。

        2、在 LinkedList 中进行顺序访问、插入、删除动作的话还是比较高效的。原因在于,插入、删除的话对于LinkedList来说只需要改变其排列的一个node结点就可以了,而对于ArrayList来说删除一个元素,需要不断把后面的元素移到前面的位置上。

        3、至于顺序访问,之前一直认为ArrayList 基于数组排列,在内存中是连续排列的,应该会快得多,然后多次测试发现并不是想象的那样,或者说ArrayList没有表现出它该有的优势,甚至还不如LinkedList的访问速度。原因在于:LinkedList 提供了优化的顺序访问性能。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SpringBoot 之Actuator.

        Actuator 是 SpringBoot 项目中一个非常强大一个功能,有助于对应用程序进行监视和管理,通过 restful api 请求来监管、审计、...

    JMCui
  • Linux 学习记录 二 (文件的打包压缩).

     前言:本文参考《鸟哥的Linux 私房菜》,如有说的不对的地方,还请指正!谢谢!  环境:Centos 6.4  和window不同,在Linux压缩文件需要...

    JMCui
  • String 的 intern() 方法解析

    JDK7 之前和之后的版本,String 的 intern() 方法在实现上存在差异,本文的说明环境是 JDK8,会在文末说明 intern() 方法的版本差异...

    JMCui
  • 剑指offer 滑动窗口的最大值

    给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,...

    week
  • Java Collection Framework : List

    List 是 Java Collection Framework的重要成员,具体包括List接口及其所有的实现类。由于List接口继承了Collection接口...

    heasy3
  • Linux 学习笔记之超详细基础linux命令 Part 4

    ---------------------------------接Part 3------------------------------

    授客
  • 【左神算法课】二维矩阵的子矩阵最大累加和

    xiaoxi666
  • 零基础使用Django2.0.1打造在线教育网站(三):Django基础知识回顾

    努力与运动兼备~有任何问题可以加我好友或者关注微信公众号,欢迎交流,我们一起进步!

    编程思录
  • 如何做好需求收集[来之《程序员》第2期]

    项目前期需求收集过程的效果好坏,会对软件产品的最终质量产生直接的影响。如何收集好需求,本文作者给出了一条行之有效的实际操作途径。 什么是需求收集? 需求收集,...

    阿新
  • 让你轻松学习嵌入式的几种线路图方向

    嵌入式学习是一个循序渐进的过程,如果是希望向嵌入式软件方向发展的话,目前最常见的是嵌入式Linux方向,关注这个方向,我认为大概分3个阶段: 1、嵌入式lin...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券