ArrayList和LinkedList的add(E)性能秘密


声明:本文转载自https://my.oschina.net/u/3758413/blog/1637919,转载目的在于传递更多信息,仅供学习交流之用。如有侵权行为,请联系我,我会及时删除。

两者末尾添加数据的性能如何?

我将通过程序和源码来解析。

程序解析

这里我将比较两者添加数据所消耗的时间。

    ArrayList<String> arr2 = new ArrayList<String>();    LinkedList<String> link2 = new LinkedList<String>();     long start =System.currentTimeMillis();     for (int i = 0; i < asize; i++) {         arr2.add("木子道_arrayList_"+i);     }     System.out.print("ArrayList exec add method " + asize + "|||");     System.out.println(System.currentTimeMillis()- start +"/ms");     start =System.currentTimeMillis();     for (int i = 0; i < asize; i++) {         link2.add("木子道_linkedList_"+i);     }     System.out.print("LinkedList exec add method " + asize + "|||");     System.out.println( System.currentTimeMillis() - start + "/ms"); 

第一种结果:10万数据的插入ArrayList平均耗时170毫秒,LinkedList平均耗时70毫秒 ArrayList exec add method 100000,耗时 170/ms LinkedList exec add method 100000,耗时 74/ms

第二种结果:1万数据的插入ArrayList平均耗时90毫秒,LinkedList平均耗时50毫秒 ArrayList exec add method 10000,耗时 94/ms LinkedList exec add method 10000,耗时 51/ms

第三种结果:5千数据的插入ArrayList平均耗时50毫秒,LinkedList平均耗时40毫秒 ArrayList exec add method 5000,耗时 51/ms LinkedList exec add method 5000,耗时 41/ms

第四种结果:1千数据的插入ArrayList平均耗时10毫秒,LinkedList平均耗时10毫秒 ArrayList exec add method 1000,耗时 9/ms LinkedList exec add method 1000,耗时 12/ms

以上的结果不是固定的,消耗的时间也不能决定因素,只做参考。

源码解析 JDK1.7

 //*********ArrayList****** //添加数据 public boolean add(E e) {   //数据增加,容量不够就扩容     ensureCapacityInternal(size + 1);  // Increments modCount!!     elementData[size++] = e;     return true; } // private void ensureCapacityInternal(int minCapacity) {     modCount++;     // overflow-conscious code 默认在10一下不需要扩容     if (minCapacity - elementData.length > 0)         grow(minCapacity); } //扩容 private void grow(int minCapacity) {     // overflow-conscious code     int oldCapacity = elementData.length;    //按1.5倍扩容     int newCapacity = oldCapacity + (oldCapacity >> 1);     if (newCapacity - minCapacity < 0)         newCapacity = minCapacity;     if (newCapacity - MAX_ARRAY_SIZE > 0)         newCapacity = hugeCapacity(minCapacity);     // minCapacity is usually close to size, so this is a win:    //扩容成功,容量当然也要改变啦。     elementData = Arrays.copyOf(elementData, newCapacity); } //******LinkedList******* //添加数据   public boolean add(E e) {       linkLast(e);     return true; } //链接e作为最后一个元素。 void linkLast(E e) {     final Node<E> l = last;   //至关重要。。。new一个节点对象     final Node<E> newNode = new Node<>(l, e, null);     last = newNode;     if (l == null)         first = newNode;     else         l.next = newNode;     size++;     modCount++; } 

通过源码发现ArrayList添加元素偶尔需要扩容。LinkedList每次都new一个对象,开销是固定。 通过程序发现ArrayList随着数据量大,性能远远比LinkedList差。

ArrayList使用数组存储,其实是一个内存连续块,插入元素涉及数组元素移动等内存操作。 LinkedList使用双向链表,将内存碎片通过引用关联起来,形成一个可以按序号索引的线性结构,这比数组连续方式相比,内存的利用率更高。插入数据只需记录本前后节点即可。

总结

ArrayList:随机访问快,插入和删除慢,基于数组的数据结构。

LinkedList:随机访问慢,插入和删除快,基于双向链表的数据结构。

ArrayList就是根据索引查。插入数组会复制成新数组,删除会移动数组,重排序。

LinkedList只能从头开始找,访问会慢,插入和删除不需要重排序所以快。

ArrayList扩容的时候会出现的结尾预留一定的容量空间的浪费。

LinkedList的每一个元素容量空间是相等。

我的结论是:末尾添加数据量小的时候。ArrayList性能好,而数据量大则是LinkedList性能好。 欢迎指正。。。

▼长按以下二维码即可关注▼

image

2018年请与我一起打怪升级

本文发表于2018年03月17日 22:38
(c)注:本文转载自https://my.oschina.net/u/3758413/blog/1637919,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如有侵权行为,请联系我们,我们会及时删除.

阅读 1560 讨论 0 喜欢 0

抢先体验

扫码体验
趣味小程序
文字表情生成器

闪念胶囊

你要过得好哇,这样我才能恨你啊,你要是过得不好,我都不知道该恨你还是拥抱你啊。

直抵黄龙府,与诸君痛饮尔。

那时陪伴我的人啊,你们如今在何方。

不出意外的话,我们再也不会见了,祝你前程似锦。

这世界真好,吃野东西也要留出这条命来看看

快捷链接
网站地图
提交友链
Copyright © 2016 - 2021 Cion.
All Rights Reserved.
京ICP备2021004668号-1