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

相关文章

来自专栏技术小黑屋

Java性能调优之容器扩容问题

在Java和Android编程中,我们经常使用类似ArrayList,HashMap等这些容器。这些容器少则存储几条,多则上千甚至更多。作为性能调优的一部分,容...

841
来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

2465
来自专栏WindCoder

数据统计第一弹-按时/天/周/月补全某一段时间的数据-Java核心逻辑

本代码均结合之前的发布的DateUtil使用,之后的mysql查询部分看心情发布,就这么任性~ ~

571
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

2234
来自专栏数据处理

leetcode222求完全二叉树节点个数

3494
来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

3196
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

1021
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

1575
来自专栏Java技术

为什么MySQL数据库索引选择使用B+树?

在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出...

2551
来自专栏计算机视觉与深度学习基础

Leetcode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the resul...

1905

扫码关注云+社区