|
1. List概述
List,就如圖名字所示一樣,是元素的有序列表。當(dāng)我們討論List時，將其與Set作對比是一個很好的辦法,Set集合中的元素是無序且唯一的。
下圖是Collection的類繼承圖,從圖中你可以對本文所討論的知識有大致的了解.
圖1
2. ArrayList、LinkedList與Vector的對比
從圖中可以看出,這三者都實現(xiàn)了List 接口.所有使用方式也很相似,主要區(qū)別在于因為實現(xiàn)方式的不同,所以對不同的操作具有不同的效率。
ArrayList 是一個可改變大小的數(shù)組.當(dāng)更多的元素加入到ArrayList中時,其大小將會動態(tài)地增長.內(nèi)部的元素可以直接通過get與set方法進(jìn)行訪問,因為ArrayList本質(zhì)上就是一個數(shù)組.
LinkedList 是一個雙鏈表,在添加和刪除元素時具有比ArrayList更好的性能.但在get與set方面弱于ArrayList.
當(dāng)然,這些對比都是指數(shù)據(jù)量很大或者操作很頻繁的情況下的對比,如果數(shù)據(jù)和運算量很小,那么對比將失去意義.
Vector 和ArrayList類似,但屬于強(qiáng)同步類。如果你的程序本身是線程安全的(thread-safe,沒有在多個線程之間共享同一個集合/對象),那么使用ArrayList是更好的選擇。
Vector和ArrayList在更多元素添加進(jìn)來時會請求更大的空間。Vector每次請求其大小的雙倍空間，而ArrayList每次對size增長50%.
而 LinkedList 還實現(xiàn)了 Queue 接口,該接口比List提供了更多的方法,包括 offer(),peek(),poll()等.
注意: 默認(rèn)情況下ArrayList的初始容量非常小,所以如果可以預(yù)估數(shù)據(jù)量的話,分配一個較大的初始值屬于最佳實踐,這樣可以減少調(diào)整大小的開銷。
3. ArrayList示例
- 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());
- }
- }
- 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. Vector
Vector和ArrayList幾乎是完全相同的,唯一的區(qū)別在于Vector是同步類(synchronized).因此,開銷就比ArrayList要大.正常情況下,大多數(shù)的Java程序員使用ArrayList而不是Vector,因為同步完全可以由程序員自己來控制。
6. ArrayList與LinkedList性能對比
時間復(fù)雜度對比如下:
|
ArrayList |
LinkedList |
|---|
get() |
O(1) |
O(n) |
|---|
add() |
O(1) |
O(1) amortized |
|---|
remove() |
O(n) |
O(n) |
|---|
* 表中的 add() 代表 add(E e),而 remove()代表 remove(int index)'
- ArrayList 對于隨機(jī)位置的add/remove，時間復(fù)雜度為 O(n),但是對于列表末尾的添加/刪除操作,時間復(fù)雜度是 O(1).
- LinkedList對于隨機(jī)位置的add/remove，時間復(fù)雜度為 O(n),但是對于列表 末尾/開頭 的添加/刪除操作,時間復(fù)雜度是 O(1).
我使用下面的代碼來測試他們的性能:
- 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");
- }
輸出結(jié)果如下:
- Test times = 10000
- -------------------------
- 1469985 <--ArrayList add
- 3530491 <--LinkedList add
- -------------------------
- 593678 <--ArrayList get
- 86914251 <--LinkedList get
- -------------------------
- 625651 <--ArrayList remove
- 2164320 <--LinkedList remove
- Test times = 100000
- -------------------------
- 11480805 <--ArrayList add
- 26384338 <--LinkedList add
- -------------------------
- 714072 <--ArrayList get
- 10040809061 <--LinkedList get
- -------------------------
- 1203935 <--ArrayList remove
- 1595905 <--LinkedList remove
- 在 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ī)模的隨機(jī)讀取
- 大量的增加/刪除操作
相關(guān)閱讀:
- HashSet
vs. TreeSet vs. LinkedHashSet - Java高效計數(shù)器
- How
to Convert Array to ArrayList in Java? - Sort
a String LinkedList in Java
|
