JAVA集合类之ArrayList和LinkedList性能比较
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JAVA集合类之ArrayList和LinkedList性能比较,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3188字,纯文字阅读大概需要5分钟。
内容图文
关于ArrayList和LinkedList这两个集合类的性能,网上很多文章表示:ArrayList的插入性能要比LinkedList差。今天突然想测试下,这个结论是否准确。
编写了如下代码:
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Demo { public static void main(String[] args) { int count = 1000000; //循环次数 System.out.println("循环 " + count + " 次,ArrayList LinkedList 尾部插入性能测试:"); List<Integer> lst = new ArrayList<Integer>(); List<Integer> link = new LinkedList<Integer>(); new Demo().testInsert(lst, count); new Demo().testInsert(link, count); int index = 0; //插入位置 count = 90000; System.out.println("\n循环 " + count + " 次,ArrayList LinkedList 指定位置插入性能测试:"); lst = new ArrayList<Integer>(); link = new LinkedList<Integer>(); new Demo().testInsertForIndex(lst, count, index); new Demo().testInsertForIndex(link, count, index); } /** * 向默认位置插入元素 * @param count 循环次数 */ public void testInsert(List<Integer> lst, int count){ long bTime = System.currentTimeMillis(); for(int i=0; i<count; i++){ lst.add(1); } long eTime = System.currentTimeMillis(); System.out.println(lst.getClass().getName() + " 共耗时:" + (eTime - bTime) + " ms"); } /** * 向指定位置插入元素 * @param count 循环次数 * @param index 插入位置 */ public void testInsertForIndex(List<Integer> lst, int count, int index){ long bTime = System.currentTimeMillis(); for(int i=0; i<count; i++){ lst.add(index,1); } long eTime = System.currentTimeMillis(); System.out.println(lst.getClass().getName() + " 共耗时:" + (eTime - bTime) + " ms"); } }
执行结果如下:
循环 1000000 次,ArrayList LinkedList 尾部插入性能测试: java.util.ArrayList 共耗时:56 ms java.util.LinkedList 共耗时:192 ms 循环 90000 次,ArrayList LinkedList 指定位置插入性能测试: java.util.ArrayList 共耗时:3885 ms java.util.LinkedList 共耗时:5 ms
根据结果发现,在都使用add(E e)函数添加元素时,LinkedList的性能反而不如ArrayList。那这到底是为何?
我们来看看具体的源码:
ArrayList的add(E e)函数
public boolean add(E e) { ensureCapacity(size + 1); //数组扩容 elementData[size++] = e; return true; }
第一行代码:用于给ArrayList中的元素数组进行扩容,且先判断是否需要扩容,如果需要则扩容算法为:目前容量*3/2+1
第二行代码:向元素数组的尾部追加新元素
LinkedList的add(E e)函数
public boolean add(E e) { addBefore(e, header); return true; } private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }
addBefore函数首先创建一个新的Entry节点,并插入到链接表,然后分别调整新节点的前一节点的向后引用和后一节点的向前引用。
看了这两段代码前面的结论也就有了答案。
我们再来看看为什么向指定位置插入时,性能差距如此之大?
ArrayList的add(int index, E element)函数
public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1,size - index); elementData[index] = element; size++; }
此处可以看到每插入一个元素都会使用System.arraycopy进行数组的复制,可想而知这效率会有多低。
LinkedList的add(int index, E element)函数
public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); }
此处,依然调用了addBefore函数,性能与add(E e)没有差异。
总结:作为coder,每个细节都应该自己进行验证,不能人云亦云。
本文出自 “怒放的生命” 博客,请务必保留此出处http://shane.blog.51cto.com/824878/1828196
原文:http://shane.blog.51cto.com/824878/1828196
内容总结
以上是互联网集市为您收集整理的JAVA集合类之ArrayList和LinkedList性能比较全部内容,希望文章能够帮你解决JAVA集合类之ArrayList和LinkedList性能比较所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。