比较ArrayList、LinkedList、Vector

2019-11-08 02:26:42

字体：大中小

来源：转载

供稿：网友

1. List概述

List,就如图名字所示一样,是元素的有序列表。当我们讨论List时，将其与Set作对比是一个很好的办法,Set集合中的元素是无序且唯一的。下图是Collection的类继承图,从图中你可以对本文所讨论的知识有大致的了解.

图12. ArrayList、LinkedList与Vector的对比从图中可以看出,这三者都实现了List 接口.所有使用方式也很相似,主要区别在于因为实现方式的不同,所以对不同的操作具有不同的效率。ArrayList 是一个可改变大小的数组.当更多的元素加入到ArrayList中时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问,因为ArrayList本质上就是一个数组.LinkedList 是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList.当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比,如果数据和运算量很小,那么对比将失去意义.Vector 和ArrayList类似,但属于强同步类。如果你的程序本身是线程安全的(thread-safe,没有在多个线程之间共享同一个集合/对象),那么使用ArrayList是更好的选择。Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间，而ArrayList每次对size增长50%.而 LinkedList 还实现了 Queue 接口,该接口比List提供了更多的方法,包括 offer(),peek(),poll()等.注意: 默认情况下ArrayList的初始容量非常小,所以如果可以预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。3. ArrayList示例[java] view plain copy

public static void testArrayList() { ArrayList<Integer> al = new ArrayList<Integer>(); al.add(3); al.add(2); al.add(1); al.add(4); al.add(5); al.add(6); al.add(6); Iterator<Integer> iter1 = al.iterator(); while(iter1.hasNext()){ System.out.PRintln(iter1.next()); } } 4.%20LinkedList示例[java] view%20plain copy

public static void testLinkedList() { LinkedList<Integer> ll = new LinkedList<Integer>(); ll.add(3); ll.add(2); ll.add(1); ll.add(4); ll.add(5); ll.add(6); ll.add(6); Iterator<Integer> iter2 = ll.iterator(); while(iter2.hasNext()){ System.out.println(iter2.next()); } } 如上面的例子所示,其使用方式是相似的,实际的区别在于底层的实现方式以及操作的复杂性不同.5.%20VectorVector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized).因此,开销就比ArrayList要大.正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。6.%20ArrayList与LinkedList性能对比时间复杂度对比如下: ArrayListLinkedListget() O(1) O(n)add() O(1) O(1) amortizedremove() O(n) O(n)

* 表中的%20add()%20代表%20add(E%20e),而%20remove()代表%20remove(int%20index)'ArrayList%20对于随机位置的add/remove，时间复杂度为%20O(n),但是对于列表末尾的添加/删除操作,时间复杂度是%20O(1). LinkedList对于随机位置的add/remove，时间复杂度为%20O(n),但是对于列表%20末尾/开头%20的添加/删除操作,时间复杂度是%20O(1).

我使用下面的代码来测试他们的性能:

[java] view%20plain copy

public static void testPerformance() { ArrayList<Integer> arrayList = new ArrayList<Integer>(); LinkedList<Integer> linkedList = new LinkedList<Integer>(); int times = 10 * 1000; // times = 100 * 1000; // times = 1000 * 1000; System.out.println("Test times = " + times); System.out.println("-------------------------"); // ArrayList add long startTime = System.nanoTime(); for (int i = 0; i < times; i++) { arrayList.add(i); } long endTime = System.nanoTime(); long duration = endTime - startTime; System.out.println(duration + " <--ArrayList add"); // LinkedList add startTime = System.nanoTime(); for (int i = 0; i < times; i++) { linkedList.add(i); } endTime = System.nanoTime(); duration = endTime - startTime; System.out.println(duration + " <--LinkedList add"); System.out.println("-------------------------"); // ArrayList get startTime = System.nanoTime(); for (int i = 0; i < times; i++) { arrayList.get(i); } endTime = System.nanoTime(); duration = endTime - startTime; System.out.println(duration + " <--ArrayList get"); // LinkedList get startTime = System.nanoTime(); for (int i = 0; i < times; i++) { linkedList.get(i); } endTime = System.nanoTime(); duration = endTime - startTime; System.out.println(duration + " <--LinkedList get"); System.out.println("-------------------------"); // ArrayList remove startTime = System.nanoTime(); for (int i = times - 1; i >= 0; i--) { arrayList.remove(i); } endTime = System.nanoTime(); duration = endTime - startTime; System.out.println(duration + " <--ArrayList remove"); // LinkedList remove startTime = System.nanoTime(); for (int i = times - 1; i >= 0; i--) { linkedList.remove(i); } endTime = System.nanoTime(); duration = endTime - startTime; System.out.println(duration + " <--LinkedList remove"); }

输出结果如下:

[plain] view%20plain copy

Test times = 10000 ------------------------- 1469985 <--ArrayList add 3530491 <--LinkedList add ------------------------- 593678 <--ArrayList get 86914251 <--LinkedList get ------------------------- 625651 <--ArrayList remove 2164320 <--LinkedList remove [java] view%20plain copy

Test times = 100000 ------------------------- 11480805 <--ArrayList add 26384338 <--LinkedList add ------------------------- 714072 <--ArrayList get 10040809061 <--LinkedList get ------------------------- 1203935 <--ArrayList remove 1595905 <--LinkedList remove [plain] view%20plain copy

在 1000*1000次的运行中,很长时间过后, LinkedList的get日志还没有打印出来，大概是15分钟左右,结果还是没有出来.

[java] view%20plain copy

Test times = 1000000 ------------------------- 132632998 <--ArrayList add 322885939 <--LinkedList add ------------------------- 3690752 <--ArrayList get 1520315361147 <--LinkedList get ------------------------- 8750043 <--ArrayList remove 13872885 <--LinkedList remove 他们性能的差异相当明显,LinkedList在 add和remove 上更快,而在get上更慢(原文是这样的).

译者注: 译者的编译和执行环境是 MyEclipse的JDK6,不论怎么看,都是 ArrayList更胜一筹,所以,该怎么选择,请根据自己的实际情况来决定，最好自己做测试，因为数据类型不同,JDK版本不同,优化不同，就可能有不同的结果。

根据时间复杂度表格,以及测试结果,我们可以判断何时该用ArrayList,何时该用LinkedList.

简单来说,LinkedList更适用于:没有大规模的随机读取大量的增加/删除操作