3.2 ArrayList、Vector和LinkedList的區(qū)別

List是一種線性的列表結(jié)構(gòu)，它繼承自Collection接口，是一種有序集合，List中的元素可以根據(jù)索引進(jìn)行檢索、刪除或者插入操作。在Java語言中List接口有不同的實現(xiàn)類，圖3-3給出了部分常用的List的實現(xiàn)類。

1）ArrayList是用數(shù)組實現(xiàn)的，數(shù)組本身是隨機訪問的結(jié)構(gòu)。ArrayList為什么讀取快？是因為get(int)方法直接從數(shù)組獲取數(shù)據(jù)。為什么寫入慢？其實這個說法并不準(zhǔn)確，在容量不發(fā)生變化的情況下，它一樣很快。當(dāng)數(shù)組的容量不夠用的時候，就需要擴容，而在容量被改變的時候，grow(int)方法會被調(diào)用，這個方法會對數(shù)組進(jìn)行擴容擴從而導(dǎo)致寫入數(shù)據(jù)的效率下降。

2）LinkedList是順序訪問結(jié)構(gòu)，內(nèi)部使用雙向列表實現(xiàn)的。因此查詢指定數(shù)據(jù)會消耗一些時間（需要遍歷鏈表進(jìn)行查詢）。在頭尾增加刪除數(shù)據(jù)的操作非常迅速，但是如果要做隨機插入，那么還是需要遍歷，當(dāng)然這還是比ArrayList的System.arraycopy性能要好一些。

3）Vector與ArrayList相比，Vector是線程安全的，而且容量增長策略不同。

4）Stack是Vector的子類，提供了一些與棧特性相關(guān)方法。

圖3-3 List類圖

ArrayList、Vector、LinkedList類均在java.util包中，都是可伸縮的數(shù)組，即可以動態(tài)改變長度的數(shù)組。

ArrayList和Vector都是基于存儲元素的Object[] array來實現(xiàn)的，它們會在內(nèi)存中開辟一塊連續(xù)的空間來存儲，由于數(shù)據(jù)存儲是連續(xù)的，因此，它們支持用序號（下標(biāo)）來訪問元素，同時索引數(shù)據(jù)的速度比較快。但是在插入元素的時候需要移動容器中的元素，所以對數(shù)據(jù)的插入操作執(zhí)行速度比較慢。ArrayList和Vector都有一個初始化的容量的大小，當(dāng)里面存儲的元素超過這個大小的時候就需要動態(tài)地擴充它們的存儲空間。為了提高程序的效率，每次擴充容量的時候不是簡單的擴充一個存儲單元，而是一次就會增加多個存儲單元。Vector默認(rèn)擴充為原來的兩倍（每次擴充空間的大小是可以設(shè)置的），而ArrayList默認(rèn)擴充為原來的1.5倍（沒有提供設(shè)置空間擴充的方法）。

ArrayList與Vector最大的區(qū)別就是synchronization(同步)的使用，沒有一個ArrayList的方法是同步的，而Vector的絕大多數(shù)的方法（例如add、insert、remove、set、equals、hashcode等）都是直接或者間接同步的，所以Vector是線程安全的，ArrayList不是線程安全的。正是由于Vector提供了線程安全的機制，使其性能上也要略遜于ArrayList。

LinkedList是采用雙向鏈表來實現(xiàn)的，對數(shù)據(jù)的索引需要從列表頭開始遍歷，因此在隨機訪問的效率比較低，但是插入元素的時候不需要對數(shù)據(jù)進(jìn)行移動，因此插入效率較高。同時，LinkedList不是線程安全的。

那么，在實際使用時，如何從這幾種容器中選擇合適的使用？當(dāng)對數(shù)據(jù)的主要操作為索引或只在集合的末端增加、刪除元素，使用ArrayList或Vector效率比較高。當(dāng)對數(shù)據(jù)的操作主要為指定位置的插入或刪除操作，使用LinkedList效率比較高。當(dāng)在多線程中使用容器時（即多個線程會同時訪問該容器），選用Vector較為安全。