MyException - 我的异常网
当前位置:我的异常网» Java相关 » ArrayList 跟 LinkedList的执行效率比较

ArrayList 跟 LinkedList的执行效率比较

www.MyException.Cn  网友分享于:2013-08-16  浏览:0次
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 提供了优化的顺序访问性能。

    

文章评论

当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
为什么程序员都是夜猫子
为什么程序员都是夜猫子
如何成为一名黑客
如何成为一名黑客
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员必看的十大电影
程序员必看的十大电影
Java程序员必看电影
Java程序员必看电影
每天工作4小时的程序员
每天工作4小时的程序员
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
那些争议最大的编程观点
那些争议最大的编程观点
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
总结2014中国互联网十大段子
总结2014中国互联网十大段子
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
 程序员的样子
程序员的样子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
编程语言是女人
编程语言是女人
我的丈夫是个程序员
我的丈夫是个程序员
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
一个程序员的时间管理
一个程序员的时间管理
我是如何打败拖延症的
我是如何打败拖延症的
鲜为人知的编程真相
鲜为人知的编程真相
中美印日四国程序员比较
中美印日四国程序员比较
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个调试和排错的小建议
10个调试和排错的小建议
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
老程序员的下场
老程序员的下场
旅行,写作,编程
旅行,写作,编程
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员的鄙视链
程序员的鄙视链
程序员都该阅读的书
程序员都该阅读的书
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有