List概括
先回顧一下List的框架圖
Paste_Image.png
- List 是一個(gè)接口给赞，它繼承于Collection的接口逃呼。它代表著有序的隊(duì)列夏醉。
- AbstractList 是一個(gè)抽象類鞍泉，它繼承于AbstractCollection。AbstractList實(shí)現(xiàn)List接口中除size()阁簸、get(int location)之外的函數(shù)爬早。
- AbstractSequentialList 是一個(gè)抽象類，它繼承于AbstractList启妹。AbstractSequentialList 實(shí)現(xiàn)了“鏈表中筛严，根據(jù)index索引值操作鏈表的全部函數(shù)”。
- ArrayList, LinkedList, Vector, Stack是List的4個(gè)實(shí)現(xiàn)類饶米。
- ArrayList 是一個(gè)數(shù)組隊(duì)列桨啃，相當(dāng)于動(dòng)態(tài)數(shù)組。它由數(shù)組實(shí)現(xiàn)檬输，隨機(jī)訪問(wèn)效率高照瘾，隨機(jī)插入、隨機(jī)刪除效率低丧慈。
- LinkedList 是一個(gè)雙向鏈表网杆。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作伊滋。LinkedList隨機(jī)訪問(wèn)效率低，但隨機(jī)插入队秩、隨機(jī)刪除效率低笑旺。
- Vector 是矢量隊(duì)列，和ArrayList一樣馍资，它也是一個(gè)動(dòng)態(tài)數(shù)組筒主，由數(shù)組實(shí)現(xiàn)。但是ArrayList是非線程安全的，而Vector是線程安全的乌妙。
- Stack 是棧使兔，它繼承于Vector。它的特性是：先進(jìn)后出(FILO, First In Last Out)藤韵。
第2部分 List使用場(chǎng)景
學(xué)東西的最終目的是為了能夠理解虐沥、使用它。下面先概括的說(shuō)明一下各個(gè)List的使用場(chǎng)景泽艘，后面再分析原因欲险。
如果涉及到“棧”匹涮、“隊(duì)列”天试、“鏈表”等操作，應(yīng)該考慮用List然低，具體的選擇哪個(gè)List喜每，根據(jù)下面的標(biāo)準(zhǔn)來(lái)取舍。
- 對(duì)于需要快速插入雳攘，刪除元素带兜，應(yīng)該使用LinkedList。
- 對(duì)于需要快速隨機(jī)訪問(wèn)元素来农，應(yīng)該使用ArrayList鞋真。
- 對(duì)于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會(huì)被單個(gè)線程操作”沃于，此時(shí)應(yīng)該使用非同步的類(如ArrayList)涩咖。
- 對(duì)于“多線程環(huán)境，且List可能同時(shí)被多個(gè)線程操作”繁莹，此時(shí)檩互，應(yīng)該使用同步的類(如Vector)。
通過(guò)下面的測(cè)試程序咨演，我們來(lái)驗(yàn)證上面的(01)和(02)結(jié)論闸昨。參考代碼如下：
import java.util.*;
import java.lang.Class;
/*
* @desc 對(duì)比ArrayList和LinkedList的插入、隨機(jī)讀取效率薄风、刪除的效率
*
* @author skywang
*/
public class ListCompareTest {
private static final int COUNT = 100000;
private static LinkedList linkedList = new LinkedList();
private static ArrayList arrayList = new ArrayList();
private static Vector vector = new Vector();
private static Stack stack = new Stack();
public static void main(String[] args) {
// 換行符
System.out.println();
// 插入
insertByPosition(stack) ;
insertByPosition(vector) ;
insertByPosition(linkedList) ;
insertByPosition(arrayList) ;
// 換行符
System.out.println();
// 隨機(jī)讀取
readByPosition(stack);
readByPosition(vector);
readByPosition(linkedList);
readByPosition(arrayList);
// 換行符
System.out.println();
// 刪除
deleteByPosition(stack);
deleteByPosition(vector);
deleteByPosition(linkedList);
deleteByPosition(arrayList);
}
// 獲取list的名稱
private static String getListName(List list) {
if (list instanceof LinkedList) {
return "LinkedList";
} else if (list instanceof ArrayList) {
return "ArrayList";
} else if (list instanceof Stack) {
return "Stack";
} else if (list instanceof Vector) {
return "Vector";
} else {
return "List";
}
}
// 向list的指定位置插入COUNT個(gè)元素饵较，并統(tǒng)計(jì)時(shí)間
private static void insertByPosition(List list) {
long startTime = System.currentTimeMillis();
// 向list的位置0插入COUNT個(gè)數(shù)
for (int i=0; i<COUNT; i++)
list.add(0, i);
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : insert "+COUNT+" elements into the 1st position use time：" + interval+" ms");
}
// 從list的指定位置刪除COUNT個(gè)元素，并統(tǒng)計(jì)時(shí)間
private static void deleteByPosition(List list) {
long startTime = System.currentTimeMillis();
// 刪除list第一個(gè)位置元素
for (int i=0; i<COUNT; i++)
list.remove(0);
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : delete "+COUNT+" elements from the 1st position use time：" + interval+" ms");
}
// 根據(jù)position遭赂，不斷從list中讀取元素循诉，并統(tǒng)計(jì)時(shí)間
private static void readByPosition(List list) {
long startTime = System.currentTimeMillis();
// 讀取list元素
for (int i=0; i<COUNT; i++)
list.get(i);
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : read "+COUNT+" elements by position use time：" + interval+" ms");
}
}
從中，我們可以發(fā)現(xiàn)：
- 插入10萬(wàn)個(gè)元素撇他，LinkedList所花時(shí)間最短：29ms茄猫。
- 刪除10萬(wàn)個(gè)元素狈蚤，LinkedList所花時(shí)間最短：15ms。
- 遍歷10萬(wàn)個(gè)元素划纽，LinkedList所花時(shí)間最長(zhǎng)：10809 ms脆侮；而ArrayList、Stack和Vector則相差不多勇劣，都只用了幾秒靖避。
考慮到Vector是支持同步的，而Stack又是繼承于Vector的芭毙；因此筋蓖，得出結(jié)論：
- 對(duì)于需要快速插入，刪除元素退敦，應(yīng)該使用LinkedList粘咖。
- 對(duì)于需要快速隨機(jī)訪問(wèn)元素，應(yīng)該使用ArrayList侈百。
- 對(duì)于“單線程環(huán)境” 或者 “多線程環(huán)境瓮下，但List僅僅只會(huì)被單個(gè)線程操作”，此時(shí)應(yīng)該使用非同步的類钝域。Vector
- ArrayList支持序列化讽坏，而Vector不支持；即ArrayList有實(shí)現(xiàn)java.io.Serializable接口例证，而Vector沒(méi)有實(shí)現(xiàn)該接口路呜。
- Vector支持通過(guò)Enumeration去遍歷，而對(duì)于需要快速插入织咧，刪除元素胀葱，應(yīng)該使用LinkedList，ArrayList不支持
本文來(lái)自： http://www.cnblogs.com/skywang12345/p/3308900.html
