Android 原创 开发&源码 ·

Android开发(java基础一)ArrayList、LinkedList与for循环

之前写了篇性能相关的文章:Android开发: 关于性能需要考虑的,都是一些文字描述,纯理论文;现在补充点实际的,以便更深刻的了解代码/数据结构/算法等对性能的影响...就从使用较多的listfor循环开始...

代码示例

程序员写作惯例,先看代码

上次代码针对ArrayList和LinkedList及for循环做了多个测试,分为:
横向比较:ArrayList和LinkedList之间针对add(T)和add(int, T)耗时比较;使用for循环耗时比较
纵向比较:同一list的add和add(int,T)耗时比较;同一list使用不同for循环的耗时比较;以及同一list不同数量级时的耗时比较

结果分析

我们先来看看上述代码运行的结果

thinkinDemo.png

重点看红线标注的值。

横向对比:

①.在使用liast.add(T)时,ArrayList和LinedList耗时差别不大,当数据为10000 * 2时,几乎无差别,在数据达到500000 * 2时,LinkedList耗时多于ArrayList.
②.在使用list.add(0, T)时,耗时差距就很明显了,LinkedList明显优于ArrayList. 我们先接着看数据,原因稍后分析
③.再看看for循环获取指定对象,不管是普通for循环,forEach,还是iterator,ArrayList都优于LinkedList

纵向对比:

①.ArrayList使用add(N)速度明显高于add(0,N);
②.LinkedList.get(size >> 1)耗时远高于get(10)及get(size - 10)
③.LinkedList使用forEach和iterrator效率原告与普通for循环

为什么?(源码分析)

下面,带着这一系列结果,我们来深入了解下ArrayList,LinkedList及forEach

我们先看看ArrayList,可以了解到ArrayList是基于数组的实现,而且默认初始长度是10,最大储存长度是2147483639

再看看ArrayList的add方法和add(0,N):打开ArrayList源码

add(N)做了两个操作,一个是ensureCapacityInternal,另一个是赋值,我们先看看ensureCapacityInternal做了啥?

这么一大段代码,其实是做了扩容操作(包含数组copy,扩容规则是变成原来最大容量的1.5倍+1,将原数组copy到新的数组中)
而add(0,N)与add(N)相比,在扩容之前先调用rangeCheckForAdd判断0位置是否可以插入,扩容后还需要进行一次数组copy,会移动0位置及之后的元素
所以,在ArrayLsit中add(0,N)相比于add(N)耗时会更多。

再来看看LinkedList,LinkedList是基于链表的实现,记录有first节点和last节点,其节点定义中包含prev和next节点

其add(N)和add(0,N)操作是怎样的呢?
首先看看add(N)

可以看到,LinkedList的add操作及其简单,在链表末端enw一个节点newNode,newNode的prev指向前一个元素,前一个元素的next指向newNode,然后size++

add(0,N)是怎么样的呢?

可以看到,add(0, N)同样很简单,多了一个checkPositionIndex检测0位置是否合法,然后如果0位置位于链表最尾端,则与add(0)进行同样的操作linkLast,如果不是,则进行LinkBefore操作,LinkBefore会new一个newNode节点置于0位置,并修改其前后节点的next或prev值,size++
因此:LinkedList的add(0, N)虽然比add(0)慢,但不像ArrayList的差距那么大

然后,我们再看看看ArrayList与LinkedList的get方法:
首先是ArrayList:

ArrayaList的get方法很简单,直接去数组的第index个元素
我们再来看看LinkedList的get方法是怎样实现的:

可以看到,在检查完index是否合法后,调用了node(index)去获取inde节点,我们再看看node(index)的实现

可以看到node(index)使用了折半的方式,但由于LinkedList是基于链表,需要通过首节点不断next或者尾节点不断prev才能获取到想要的index节点,这就很好的解释了为什么LinkedList的get方法耗时远低于ArrayList,而且同一个LinkedList,越靠近首尾位置的节点,get速度越快

最后,来看看for循环
看了上面get的源码,我们已经很清楚为什么LinkedList进行普通for循环时为什么会耗时这么久(普通for循环需要通过get去获取list中的元素),而使用forEach和Iterator为什么会快这么多呢?
我们先看看forEach是怎样实现的(好吧,这个没看到源码,但网上搜一下有不少解释,其实它会由编译器解释成iterator)...好吧,其实还是基于iterator的for循环,不过forEach更容易让人理解,使用起来也更方面。然后我们需要看看iterator:

这是一个接口,包含next(),然后我们可以发现List实现了Collection接口,而Collection接口继承了Iterator接口。
好吧!其实forEach只是在按照顺序不断的next(),这相比于LinkedList每次调用get()去循环查找效率当然高了几个数量级;

总结

由于ArrayList和LinkedList分别基于数组和链表,所以ArrayList更适合于查找以及顺序的增加add(index),而LinkedList则更适合于随机的增加add(index, E)和删除;

在内存上,ArrayList因为是按照1.5倍的扩容,在尾端可能会有内存浪费,而LinkedList每个节点存在着prev和next的内存开销。

由于ArrayList存在扩容,如果数据量大,可以将初始容量设置更合理(默认10),减少扩容太多次的开销,特别在addAll时。

LinkedList尽量不要选用普通for循环,使用forEach或者iterator(可以remove元素)

参与评论