**高清一区二区三区,欧美一级精品高清在线观看,天天爽天天

比較ArrayList、LinkedList、Vector

2014.08.11

1. List概述

List,就如圖名字所示一樣,是元素的有序列表。當(dāng)我們討論List時(shí)，將其與Set作對(duì)比是一個(gè)很好的辦法,Set集合中的元素是無序且唯一的。

下圖是Collection的類繼承圖,從圖中你可以對(duì)本文所討論的知識(shí)有大致的了解.

圖1

2. ArrayList、LinkedList與Vector的對(duì)比

從圖中可以看出,這三者都實(shí)現(xiàn)了List 接口.所有使用方式也很相似,主要區(qū)別在于因?yàn)閷?shí)現(xiàn)方式的不同,所以對(duì)不同的操作具有不同的效率。

ArrayList 是一個(gè)可改變大小的數(shù)組.當(dāng)更多的元素加入到ArrayList中時(shí),其大小將會(huì)動(dòng)態(tài)地增長(zhǎng).內(nèi)部的元素可以直接通過get與set方法進(jìn)行訪問,因?yàn)锳rrayList本質(zhì)上就是一個(gè)數(shù)組.

LinkedList 是一個(gè)雙鏈表,在添加和刪除元素時(shí)具有比ArrayList更好的性能.但在get與set方面弱于ArrayList.

當(dāng)然,這些對(duì)比都是指數(shù)據(jù)量很大或者操作很頻繁的情況下的對(duì)比,如果數(shù)據(jù)和運(yùn)算量很小,那么對(duì)比將失去意義.

Vector 和ArrayList類似,但屬于強(qiáng)同步類。如果你的程序本身是線程安全的(thread-safe,沒有在多個(gè)線程之間共享同一個(gè)集合/對(duì)象),那么使用ArrayList是更好的選擇。

Vector和ArrayList在更多元素添加進(jìn)來時(shí)會(huì)請(qǐng)求更大的空間。Vector每次請(qǐng)求其大小的雙倍空間，而ArrayList每次對(duì)size增長(zhǎng)50%.

而 LinkedList 還實(shí)現(xiàn)了 Queue 接口,該接口比List提供了更多的方法,包括 offer(),peek(),poll()等.

注意: 默認(rèn)情況下ArrayList的初始容量非常小,所以如果可以預(yù)估數(shù)據(jù)量的話,分配一個(gè)較大的初始值屬于最佳實(shí)踐,這樣可以減少調(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.println(iter1.next());
}
}

4. LinkedList示例

[java] view plain 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());
}
}

如上面的例子所示,其使用方式是相似的,實(shí)際的區(qū)別在于底層的實(shí)現(xiàn)方式以及操作的復(fù)雜性不同.

5. Vector

Vector和ArrayList幾乎是完全相同的,唯一的區(qū)別在于Vector是同步類(synchronized).因此,開銷就比ArrayList要大.正常情況下,大多數(shù)的Java程序員使用ArrayList而不是Vector,因?yàn)橥酵耆梢杂沙绦騿T自己來控制。

6. ArrayList與LinkedList性能對(duì)比

時(shí)間復(fù)雜度對(duì)比如下:

	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 對(duì)于隨機(jī)位置的add/remove，時(shí)間復(fù)雜度為 O(n),但是對(duì)于列表末尾的添加/刪除操作,時(shí)間復(fù)雜度是 O(1).
LinkedList對(duì)于隨機(jī)位置的add/remove，時(shí)間復(fù)雜度為 O(n),但是對(duì)于列表末尾/開頭的添加/刪除操作,時(shí)間復(fù)雜度是 O(1).

我使用下面的代碼來測(cè)試他們的性能:

[java] view plain 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");
}

輸出結(jié)果如下:

[plain] view plain copy

Test times = 10000
-------------------------
1469985 <--ArrayList add
3530491 <--LinkedList add
-------------------------
593678 <--ArrayList get
86914251 <--LinkedList get
-------------------------
625651 <--ArrayList remove
2164320 <--LinkedList remove

[java] view plain copy

Test times = 100000
-------------------------
11480805 <--ArrayList add
26384338 <--LinkedList add
-------------------------
714072 <--ArrayList get
10040809061 <--LinkedList get
-------------------------
1203935 <--ArrayList remove
1595905 <--LinkedList remove

[plain] view plain copy

在 1000*1000次的運(yùn)行中,很長(zhǎng)時(shí)間過后, LinkedList的get日志還沒有打印出來，大概是15分鐘左右,結(jié)果還是沒有出來.

[java] view plain copy

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更勝一籌,所以,該怎么選擇,請(qǐng)根據(jù)自己的實(shí)際情況來決定，最好自己做測(cè)試，因?yàn)閿?shù)據(jù)類型不同,JDK版本不同,優(yōu)化不同，就可能有不同的結(jié)果。

根據(jù)時(shí)間復(fù)雜度表格,以及測(cè)試結(jié)果,我們可以判斷何時(shí)該用ArrayList,何時(shí)該用LinkedList.

簡(jiǎn)單來說,LinkedList更適用于:

沒有大規(guī)模的隨機(jī)讀取
大量的增加/刪除操作

相關(guān)閱讀:

HashSet
vs. TreeSet vs. LinkedHashSet
Java高效計(jì)數(shù)器
How
to Convert Array to ArrayList in Java?
Sort
a String LinkedList in Java

本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。

打開APP，閱讀全文并永久保存查看更多類似文章

Java提高篇(三二)-----List總結(jié)

數(shù)組、ArrayList、LinkedList查詢及遍歷性能分析

Java集合框架：ArrayList

JAVA基礎(chǔ) 之 List

計(jì)算Java運(yùn)行時(shí)間

使用stack變量?jī)?yōu)化java程序

更多類似文章 >>

免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版