1. List概述
List,就如圖名字所示一樣,是元素的有序列表。當(dāng)我們討論List時，將其與Set作對比是一個很好的辦法,Set集合中的元素是無序且唯一的。下圖是Collection的類繼承圖,從圖中你可以對本文所討論的知識有大致的了解.
圖12. ArrayList、LinkedList與Vector的對比從圖中可以看出,這三者都實現(xiàn)了List 接口.所有使用方式也很相似,主要區(qū)別在于因為實現(xiàn)方式的不同,所以對不同的操作具有不同的效率。ArrayList 是一個可改變大小的數(shù)組.當(dāng)更多的元素加入到ArrayList中時,其大小將會動態(tài)地增長.內(nèi)部的元素可以直接通過get與set方法進行訪問,因為ArrayList本質(zhì)上就是一個數(shù)組.LinkedList 是一個雙鏈表,在添加和刪除元素時具有比ArrayList更好的性能.但在get與set方面弱于ArrayList.當(dāng)然,這些對比都是指數(shù)據(jù)量很大或者操作很頻繁的情況下的對比,如果數(shù)據(jù)和運算量很小,那么對比將失去意義.Vector 和ArrayList類似,但屬于強同步類。如果你的程序本身是線程安全的(thread-safe,沒有在多個線程之間共享同一個集合/對象),那么使用ArrayList是更好的選擇。Vector和ArrayList在更多元素添加進來時會請求更大的空間。Vector每次請求其大小的雙倍空間，而ArrayList每次對size增長50%.而 LinkedList 還實現(xiàn)了 Queue 接口,該接口比List提供了更多的方法,包括 offer(),peek(),poll()等.注意: 默認情況下ArrayList的初始容量非常小,所以如果可以預(yù)估數(shù)據(jù)量的話,分配一個較大的初始值屬于最佳實踐,這樣可以減少調(diào)整大小的開銷。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.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()); } } 如上面的例子所示,其使用方式是相似的,實際的區(qū)別在于底層的實現(xiàn)方式以及操作的復(fù)雜性不同.5.%20VectorVector和ArrayList幾乎是完全相同的,唯一的區(qū)別在于Vector是同步類(synchronized).因此,開銷就比ArrayList要大.正常情況下,大多數(shù)的Java程序員使用ArrayList而不是Vector,因為同步完全可以由程序員自己來控制。6.%20ArrayList與LinkedList性能對比時間復(fù)雜度對比如下: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"); } 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分鐘左右,結(jié)果還是沒有出來. Test times = 1000000 ------------------------- 132632998 <--ArrayList add 322885939 <--LinkedList add ------------------------- 3690752 <--ArrayList get 1520315361147 <--LinkedList get ------------------------- 8750043 <--ArrayList remove 13872885 <--LinkedList remove 他們性能的差異相當(dāng)明顯,LinkedList在 add和remove 上更快,而在get上更慢(原文是這樣的).譯者注: 譯者的編譯和執(zhí)行環(huán)境是 MyEclipse的JDK6,不論怎么看,都是 ArrayList更勝一籌,所以,該怎么選擇,請根據(jù)自己的實際情況來決定，最好自己做測試，因為數(shù)據(jù)類型不同,JDK版本不同,優(yōu)化不同，就可能有不同的結(jié)果。
根據(jù)時間復(fù)雜度表格,以及測試結(jié)果,我們可以判斷何時該用ArrayList,何時該用LinkedList.
簡單來說,LinkedList更適用于:沒有大規(guī)模的隨機讀取大量的增加/刪除操作新聞熱點
疑難解答
