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 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Go Channel 应用模式(二)

eapache/channels提供了一些channel应用模式的方法,比如上面的扇入扇出模式等。

933
来自专栏我的博客

PHP7特性

1、标量类型声明 2、返回值类型声明 3、null合并运算符 $username = $_GET[‘user’] ?? ‘nobody’; $usern...

2925
来自专栏算法channel

一道伤脑筋的算法题 亮了

一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1)...

570
来自专栏逸鹏说道

你可能不知道的字符比较中的“秘密”

有时候,一个简单的字符比较,你可能也会被弄得晕头转向。为什么这样说呢?请看下面这个例子(代码就不贴了,因为后来发现页面不支持这两个字符的显示)。猜测一下,会是什...

1827
来自专栏Golang语言社区

Go Channel 应用模式(二)

eapache/channels提供了一些channel应用模式的方法,比如上面的扇入扇出模式等。

883
来自专栏程序员的知识天地

良好的代码格式反映了程序员的编码能力,好的程序员应该这么编码

大括号的使用约定。如果是大括号内为空,则简洁地写成{}即可,不需要换行;如果 是非空代码块则:

751
来自专栏Coding01

轻轻玩转 Laravel Helpers 函数

在使用 Laravel 函数时,我们都避免不了使用其提供的各种各样的全局函数,也称为辅助函数。

1031
来自专栏小狼的世界

如何向回调函数中传入其他参数

最近写JS经常会因为向回调函数中传参而头疼,今天总结一下向回调函数中传参的方法,以后的应用中就不用在到处去找了。

481
来自专栏yw的数据分析

data.table包使用应该注意的一些细节

  注意默认nThread=getDTthreads(),即使用所有能用的核心,但并不是核心用的越多越好,本人亲自测试的情况下,其实单核具有较强的性能,只有在数...

571
来自专栏Fundebug

5分钟掌握JavaScript小技巧

为了保证可读性,本文采用意译而非直译。另外,本文版权归原作者所有,翻译仅用于学习。

821

扫码关注云+社区