Android开发（java基础）ArrayList、Linke
之前写了篇性能相关的文章：Android开发: 关于性能需要考虑的，都是一些文字描述，纯理论文；现在补充点实际的，以便更深刻的了解代码/数据结构/算法等对性能的影响...就从使用较多的list和for循环开始...
代码示例
程序员写作惯例，先看代码
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class MyClass {
public static void main(String[] args) {
System.out.println("使用LinkedList， 10000 * 2次");
test(10000, new LinkedList<N>());
System.out.println("使用ArrayList， 10000 * 2次");
test(10000, new ArrayList<N>());
System.out.println("使用LinkedList， 500000 * 2次");
test(500000, new LinkedList<N>());
System.out.println("使用ArrayList， 500000 * 2次");
test(500000, new ArrayList<N>());
}
private static void test(int num, List<N> list) {
long start = System.currentTimeMillis();
// 使用 list.add(N)增加num条数据
for (int i = 0; i < num; i++) {
list.add(new N(i));
}
System.out.println("list add(N)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
start = System.currentTimeMillis();
// 使用 list.add(0, N)增加num条数据
for (int i = 0; i < num; i++) {
list.add(0, new N(i));
}
System.out.println("list add(0, N)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
int size = list.size(); // 数组长度
start = System.currentTimeMillis();
list.get(10); // 取第10个
System.out.println("list get(10)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
start = System.currentTimeMillis();
list.get(size - 10); // 取倒数第十个
System.out.println("list get(size - 10)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
start = System.currentTimeMillis();
list.get(size >> 1); // 取中间值
System.out.println("list get(size >> 1)使用了"+ (System.currentTimeMillis() - start)+"毫秒");
N n;
start = System.currentTimeMillis();
// 普通for循环
for (int i = 0; i < size; i++) {
n = list.get(i);
}
System.out.println("普通for循环使用了"+ (System.currentTimeMillis() - start)+"毫秒");
start = System.currentTimeMillis();
// 增强型for循环（forEach）
for (N c2 : list) {
}
System.out.println("增强for循环使用了"+ (System.currentTimeMillis() - start)+"毫秒");
start = System.currentTimeMillis();
//迭代器遍历
for (Iterator<N> it = list.iterator(); it.hasNext(); ) {
n = it.next();
}
System.out.println("Iterator for循环使用了"+ (System.currentTimeMillis() - start)+"毫秒");
list.clear();
list = null;
}
}
class N {
int i;
N(int i) {
this.i = i;
}
}
上次代码针对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
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = 2147483639;
再看看ArrayList的add方法和add(0,N):打开ArrayList源码
public boolean add(E var1) {
this.ensureCapacityInternal(this.size + 1);
this.elementData[this.size++] = var1;
return true;
}
public void add(int var1, E var2) {
this.rangeCheckForAdd(var1);
this.ensureCapacityInternal(this.size + 1);
System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
this.elementData[var1] = var2;
++this.size;
}
add（N）做了两个操作，一个是ensureCapacityInternal，另一个是赋值，我们先看看ensureCapacityInternal做了啥？
private void ensureCapacityInternal(int var1) {
if(this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
var1 = Math.max(10, var1);
}
this.ensureExplicitCapacity(var1);
}
private void ensureExplicitCapacity(int var1) {
++this.modCount;
if(var1 - this.elementData.length > 0) {
this.grow(var1);
}
}
private void grow(int var1) {
int var2 = this.elementData.length;
int var3 = var2 + (var2 >> 1);
if(var3 - var1 < 0) {
var3 = var1;
}
if(var3 - 2147483639 > 0) {
var3 = hugeCapacity(var1);
}
this.elementData = Arrays.copyOf(this.elementData, var3);
}
这么一大段代码，其实是做了扩容操作（包含数组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节点
transient LinkedList.Node<E> first;
transient LinkedList.Node<E> last;
private static class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
this.item = var2;
this.next = var3;
this.prev = var1;
}
}
其add(N)和add(0,N)操作是怎样的呢？
首先看看add(N)
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
可以看到，LinkedList的add操作及其简单，在链表末端enw一个节点newNode，newNode的prev指向前一个元素，前一个元素的next指向newNode，然后size++
而add(0,N)是怎么样的呢？
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
可以看到，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:
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
ArrayaList的get方法很简单，直接去数组的第index个元素
我们再来看看LinkedList的get方法是怎样实现的：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
可以看到，在检查完index是否合法后，调用了node(index)去获取inde节点，我们再看看node(index)的实现
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
可以看到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：
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
这是一个接口，包含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元素)
