我们知道ArrayList是List接口的一个实现类,它的特点是查询效率高,增删效率低,线程不安全
原因是因为ArrayList底层是封装了一个数组,它是用数组实现的。
看下图,数组在内存中的存储方式:
现在定义一个int[] a数组,假设它的首地址是2000,int类型占4个字节,所以a[0]的首地址是2000,a[1]的首地址就是2004,以此类推….到a[n]
所以上面的这张图,就很形象的解释了,为什么ArrayList的查询效率高,每次只需要一个偏移量就可查到
但是它的增删效率为什么会低呢?
再往下看:
如果想在这个数组的中间或是第一项前插入一项,它的插入过程是以迭代的方式,让它后面的每一项依次往后挪,就如图上的要在第二项的位置上插入一项,其实这个过程是比较慢的,如果是你每次都在最后插入,这是个例外,因为它不用再去影响其它的元素,直接插在最后面;当然删也是同一个道理
看完了ArrayList,我们再去研究一下LinkedList
它的特点是:增删效率比较高,而查询效率低
LinkedList是底层用双向循环链表实现的List,链表的存储特点是不挨着,它存储的每个元素分为三段:上一项的地址、下一项的地址、元素的内容,而数组却没有上一项,下一项这种情况 ,因为数组只需要根据一个偏移量,就可以找到下一项或上一项
双向链表的底层结构图:
每个元素在内存中的排列像是随机的,中间没有连续性,通过地址来找到上一项或下一项,从图上应该可以理解了
那么现在问题来了,如果查询LinkedList中的某一项,肿么办?
没有好办法,只能把元素全部过一遍,这样就会比较的慢
而它的好处体现在它的增删效率非常的快,为什么呢?
看下面的图解:
假如我把右上的一个元素删掉,可以看到左上和右下的两个元素会直接连上,至于它们两个是怎么牵上手的,这里不多讲了,你懂的…………….
同理,在下面增加一个的时候,也是同一个道理,也就是说,当你增加或删除一个元素的时候,在LinkedList里,它最多只会影响两个元素,而不像ArrayList里,当在中间插入一个元素时,它后面的所有的元素都要受到影响,那么这样在一定程度上LinkedList的增删效率就会明显的高于ArrayList的
我们拿代码来证明一下吧:
之前我用过模版方法设计模式来测试过for、while、do-while三种循环的效率问题
这里也可以用到这个设计模式来测试ArrayList与LinkedList的增删查的效率
import java.util.*;
abstract class Template{
public abstract void test();
public void template(){
long start = System.currentTimeMillis();
test();
long end = System.currentTimeMillis();
System.out.println(end - start);
}
}
public class Test{
public static void main(String[] args){
Template t1 = new Template(){
public void test(){
List list = new ArrayList();
for(int i = 1; i < 10000 ; i++){
list.add(0,"a");
}
}
};
Template t2 = new Template(){
public void test(){
List list = new LinkedList();
for(int i = 1; i < 10000 ; i++){
list.add(0,"a");
}
}
};
Template t3 = new Template(){
public void test(){
List list = new ArrayList();
for(int i = 1; i < 10000 ; i++){
list.add("a");
}
for(int i = 1; i< 10000 ; i++){
list.get(list.size()/2);
}
}
};
Template t4 = new Template(){
public void test(){
List list = new LinkedList();
for(int i = 1; i < 10000 ; i++){
list.add("a");
}
for(int i = 1; i< 10000 ; i++){
list.get(list.size()/2);
}
}
};
t1.template();
t2.template();
t3.template();
t4.template();
}
}
输出结果:
可以看到最终的结果:
测试ArrayList的增的时间:37ms;
测试LinkedList的增的时间:4ms;(差10倍耶!!!有木有)
测试ArrayList的查的时间:3ms;(差n倍耶!!!有木有)
测试LinkedList的查的时间:77ms;
就先写到这里……
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
版权声明:本文为博主原创文章,未经博主允许不得转载。
分享到:
相关推荐
今天小编就为大家分享一篇对ArrayList和LinkedList底层实现原理详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
1.List是接口类,ArrayList和LinkedList是List的实现类 2.ArrayList是动态数组(顺序表)的数据结构 3.LinkedList
测试ArrayList和LinkedList的add方法
2,随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而ArrayList是基于 3,索引(index)的数据结构,可以直接映射到。 4,插入、删除数据时,LinkedList的效率比较高,因为ArrayList要移动数据。 ...
ArrayList、LinkedList、Vector区别简介。
关于arraylist和linkedList的区别
合理运用ArrayList与LinkedList
【Java面试题】ArrayList和LinkedList区别
list集合案例增、删、改、查,ArrayList与LinkedList的区别,LinkedList堆栈/队列的开发,list集合容量会自动扩容,list去除重复
ArrayList Vector LinkedList 区别与用法.
从底层数据结构和CPU缓存两方面剖析LinkedList的查询效率为什么比ArrayList低。以前只直到数据结构会影响两者的查询效率,偶然间得知cpu缓存(硬件级别)也会有影响
Java基础之集合List-ArrayList、LinkedList、Vector的底层实现和区别ArrayList底层实际是采用数组实现的(并且该数组的类型是
1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。 3.对于新增和删除操作add和remove,...
05丨ArrayList还是LinkedList?使用不当性能差千倍.html
比较ArrayList,LinkedList,Vector三者随机读取,插入,删除性能。
2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动 3.LinkedList不支持高效的随机元素访问 4.ArrayList的
对比Vector、ArrayList、LinkedList1
ArrayList-LinkedList-源码.rar
10.ArrayList 和LinkedList的区别.avi
Map+List+ArrayList+LinkedList Java源代码,适合初学者