java 中ArrayList与LinkedList性能比较
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);
Stringtemp=arrayList.get(random);
}
longtime12=System.currentTimeMillis();
for(inti=0;i<10000;i++){
intrandom=RandomUtils.nextInt(10000);
Stringtemp=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适合了。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！