java LinkedList ArrayList 随机访问效率 list.get(int index)

理论上来说,肯定LinkedList比ArrayList随机访问效率要低,然后LinkedList比ArrayList插入删除元素要快。

突然想起之前写一个日记本程序,是用LinkedList+Map索引,作为数据库。Map记录了LinkedList中每一个日记的index和日期之间的对应关系。从Map中获取到某个日期对应日记的index,然后再去LinkedList,get(index)。

        Integer a = 1;
        LinkedList list = new LinkedList();
        for (int i = 0; i < 2000000; i++) {
            list.add(a);
        }
        System.out.println(list.size());
        long start = System.nanoTime();
        list.get(1000000);
        long end = System.nanoTime();
        System.out.println(end - start);

上边一段代码,看出了几样事情:

1.LinkedList的随机访问速度确实差点,大概用了17毫秒。下边会贴出LinkedList随机访问的源代码,也就是这里为什么选择1000000中间数的原因。

2.Java栈区和堆区都是有限的,list那里如果一次添加5000000个item就会内存溢出

    (Exception in thread "main" java.lang.OutOfMemoryError: Java heap space)。

     但有点奇怪,不是new了在内存堆区吗?内存堆区也会爆~~

下边是LinkedList随机访问的源代码,采取了折半的遍历方式,每个循环里边进行一次int的比较。

    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

换了ArrayList的话,添加5000000个item都不会爆,但再大点,还是会爆~~

随机访问效率确实高很多,只需要16微秒左右,足足快了1千倍,而且跟get的index无关。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

单元测试同时支持 NUnit/MSTest

让单元测试代码同时支持NUnit/MSTest,可以参照MSDN magazine,也可以参看 Switching Between Using NUnit an...

1886
来自专栏我和未来有约会

silverlight寻奇 - Graphite

Graphite是一个能自动布局的图表控件。 目前它已经有了silverlight 2 和 wpf的版本。观看demo时按下“Ctrl”键再做点击操作。 原文...

1805
来自专栏张善友的专栏

Mono 2.0正式发布了

Mono官网:http://mono-project.com/ 2.0 Release Notes: http://www.mono-project.com/...

19610
来自专栏张善友的专栏

Firebird 数据库资源

Firebird is a database with 20 years of history, full set of features (including...

2278
来自专栏张善友的专栏

Visual Studio Magazine -Mono for Android

Cross-Platform Development With Mono for Android -- Visual Studio Magazine -plat...

17710
来自专栏张善友的专栏

WCF WebHttp Services in .NET 4

你是否使用WCF 3.5 或者WCF REST Starter Kit开发过Restful的服务?这些技术在.NET 4里头的名称叫做WCF WebHttp S...

18510
来自专栏张善友的专栏

Mono 2.8发布:C#4.0和更好的性能

在社区很多人不看好的微软.NET开源实现Mono发布了Mono 2.8,这是一个重要的版本更新,有着显著的改善,Mono 2.8包括C#4.0的支持(也是现在的...

1899
来自专栏walterlv - 吕毅的博客

Reading the Source Code of Microsoft.NET.Sdk, Writing the Creative Extension of Compiling

发布于 2018-06-30 12:27 更新于 2018-08...

612
来自专栏张善友的专栏

.NET 4.0 的Web Form和EF的例子 Employee Info Starter Kit (v4.0.0)

ASP.NET 4.0改进了许多不同的场景集(set of scenarios),如Webforms ,Dynamic Data以及基于AJAX的Web开发。此...

18110
来自专栏张善友的专栏

更新Silverlight ctp到Silverlight beta 1.0

下面是我更新Silverlight ctp到Silverlight beta 1.0的一个纪录,希望对各位同学有帮助。 1、卸载Silverlight ctp ...

1759

扫码关注云+社区