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

相关文章

来自专栏趣学算法

数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识,C 表示孩子结点标识,L/R...

3123
来自专栏WindCoder

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

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

1301
来自专栏数据处理

leetcode222求完全二叉树节点个数

3754
来自专栏尾尾部落

[剑指offer] 重建二叉树

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

1391
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

1725
来自专栏swag code

Calendar类-set()方法的延时操作

set(f,value)方法将日历字段f更改为value,此外还设置了一个内部成员变量,

752
来自专栏工科狗和生物喵

【我的漫漫跨考路】数据结构之单链表线性存储实现 Beta

正文之前 ? 昨天晚上阶段性的完成了一部分数学的复习,所以今天打算撸一撸代码,然后发现提电脑忘指针。所以自己磕磕盼盼,对照了一下网上的代码,总算把线性存储单链表...

36511
来自专栏技术小黑屋

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

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

1121
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

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

Leetcode 258. Add Digits

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

2015

扫码关注云+社区

领取腾讯云代金券