ArrayList与LinkedList的效率比较

Question

书上都说ArrayList是以数组形式存储数据,查询数据快,增加和删除数据慢.
而LinkedList是以链表形式存储数据,查询数据慢,增加和删除数据快.
于是我写了个测试程序来验证一下,代码如下:public class Test {

public static void main(String[] args) {

ArrayList<String> aList = new ArrayList<String>(1000);
LinkedList<String> lList = new LinkedList<String>();

long aStart = System.nanoTime();
for(int i = 0; i < 1000; i++)
{
aList.add("a");
}
System.out.println("ArrayList添加元素花: " + (System.nanoTime() - aStart) + "ns");

aStart = System.nanoTime();
for(int i = 0; i < 1000; i++)
{
lList.add("b");
}
System.out.println("LinkedList添加元素花: " + (System.nanoTime() - aStart) + "ns");

aStart = System.nanoTime();
Iterator<String> it = aList.iterator();
while(it.hasNext()) {
it.next();
}
System.out.println("ArrayList迭代元素花: " + (System.nanoTime() - aStart) + "ns");

aStart = System.nanoTime();
Iterator<String> lit = aList.iterator();
while(lit.hasNext()) {
lit.next();
}
System.out.println("LinkedList迭代元素花: " + (System.nanoTime() - aStart) + "ns");
}
}输出结果如下:ArrayList添加元素花: 161165ns
LinkedList添加元素花: 433769ns
ArrayList迭代元素花: 456203ns
LinkedList迭代元素花: 297991ns为什么ArrayList添加元素比LinkedList要快,而在迭代元素时比LinkedList要慢呢,和书上讲的不一样呀,是不是我理解有误呢,哪位仁兄解释下? 

Answer 1

因为你的 ArrayList 存放元素大小是固定的，并且在事先已经指定并开僻了 1000 个容量的数组空间，实际上只是对数组进行了操作。而 LinkedList 是采用链表实现的，在事先无法指定容量，每添加一个数据都得去开僻新的空间。如果在添加时这样进行比较的话，对于 LinkedList 是很不公平的。对于迭代来说，ArrayList 速度远比 LinkedList 慢，因为链表迭代是很快的，如果要让 ArrayList 比 LinkedList 快的话，可以使用下标索引。一般来说，ArrayList 和 LinkedList 具体使用哪一个以下这些我总结的使用规则：1：事先能预知元素数量时，应优先选择 ArrayList，并且在构造中进行初始化
2：事先不能预知元素数量时，根据不同的迭代需要选择 ArrayList 或者 LinkedList
3：如果有很多的 remove 操作时，应优先选择 LinkedList
4：需要顺序迭代，也就是从第一个元素开始一个一个地访问到最后一个时，应优先选择 LinkedList
5：需要随机访问，也就是使用 get(int) 方法取任意下标访问时，应优先选择 ArrayList

Answer 2

除第三点外，其他认同。更详细的测试可以看：http://blog.csdn.net/inkfish/archive/2010/01/13/5185320.aspx

Answer 3

inkfish 您好，我看了一下您博客中的测试。LinkedList 如果在随机访问时的效率肯定是比不过 ArrayList 的，对于随机访问的复杂度 LinkedList 的效率是 O(N)，而 ArrayList 只有 O(1)。如果使用 remove(int) 方法来移除的话，ArrayList 远比 LinkedList 要快很多。但是，如果使用 remove(Object) 这个方法的话，ArrayList 和 LinkedList 都必须进行全容器的搜索，但由于 ArrayList 在每次 remove Object 时需要使用 System.arraycopy 移动内部数组，而 LinkedList 没有这个操作。

Answer 4

我测试了一下，使用 remove(Object) 或者 removeAll(Collection) 方法的话，如果需要删除的元素全部在容器中存在，那么 LinkedList 的速度比 ArrayList 快。

Answer 5

学习1楼。
基本只用arraylist，没怎么用过linkedlist，下次设计时需要多一些考虑了。

Answer 6

偶在使用ArrayList时，还是比较少初始化容量。。
下次可以试下。。偶同样比较少用LinkList。下次也试下

Answer 7

谢谢大家的解答，bao110908兄的答案让我茅塞顿开，不给分你，对不起人民群众呀。 ^_^