一聚教程网:一个值得你收藏的教程网站

热门教程

java 中ArrayList与LinkedList性能比较

时间:2022-06-29 01:31:17 编辑:袖梨 来源:一聚教程网

java 中ArrayList与LinkedList性能比较

今天看一框架的代码,看到有些 可以使用ArrayList的地方 使用的是 LinkedList,用到的情景是在一个循环里面进行顺序的插入操作。

众所周知java里面List接口有两个实现ArrayList 和 LinkedList,他们的实现原理分别是c语言中介绍的数组和链表。

正如学习数据结构时的认识,对于插入操作,链表的结构更高效,原因是可以通过修改节点的指针 就可以完成插入操作, 而不像数组,

需要把插入位置之后的数组元素依次后移。

但是,实际情况真如上面设想一样吗,下面通过一个简单的例子实践,看能得出什么结论。

 

 代码如下复制代码

publicstaticvoidmain(String[] args) {

    ListarrayList =newArrayList();

    ListlinkedList =newLinkedList();

    longtime1 = System.currentTimeMillis();

    for(inti =0; i<1000000; i++) {

      arrayList.add(newString("abc"));

    }

    longtime2 = System.currentTimeMillis();

    for(inti =0; i<1000000; i++) {

      linkedList.add(newString("abc"));

    }

    longtime3 = System.currentTimeMillis();

    System.out.println("arrayList.insert_time = "+ (time2 - time1));

    System.out.println("linkedList.insert_time = "+ (time3 - time2));

    longtime11 = System.currentTimeMillis();

    for(inti =0; i<10000; i++) {

      intrandom = RandomUtils.nextInt(10000);

      String temp = arrayList.get(random);

    }

    longtime12 = System.currentTimeMillis();

    for(inti =0; i<10000; i++) {

      intrandom = RandomUtils.nextInt(10000);

      String temp = linkedList.get(random);

    }

    longtime13 = System.currentTimeMillis();

    System.out.println("arrayList.read_time = "+ (time12 - time11));

    System.out.println("linkedList.read_time = "+ (time13 - time12));

  }

 

运行结果:

 

 

 代码如下复制代码

arrayList.insert_time =188

linkedList.insert_time =250

arrayList.read_time =16

linkedList.read_time =234

 

通过结果可以看出:无论什么情况,ArrayList更加高效。尤其对于随机读取,数组的效率是链表的14倍之多。

而插入操作,两者用时相差不多,但是还是数组的实现效率高一些。

对于其中原因,仔细想想也不难想明白。

当List存储的内容不多时,写入List的最后的元素,ArrayList和LinkedList用时差不多。

但是当List存储的元素个数很大时,通过数组结构实现的ArrayList插入到最后可以通过数组下标很快访问到,但是LinkedList就需要访问每个节点直到找到最后的元素再进行插入操作,这中操作步骤的耗时是巨大的,所以列表数量越大,LinkedList就越感吃力了。

当然,对于要求随机插入的场景,这个时候LinkedList就要比ArrayList适合了。

热门栏目