List是一個(gè)有序（插入順序）的Collection（有時(shí)候也叫做序列）。可以包含重復(fù)的元素。除了從Collection繼承過來的方法外，還包含下面的操作：
- 位置訪問：基于元素位置索引來操作元素。比如
get、set、add、addAll和remove - 搜索：從List中搜索指定的元素，并且返回其位置索引。如
indexOf和lastIndexOf - 迭代：擴(kuò)展
Iterator提供利用List序列特性的遍歷操作。listIterator方法返回此類迭代器 - 區(qū)間視圖：
sublist方法提供任意的區(qū)間操作。
Java平臺(tái)提供了兩種通用的List實(shí)現(xiàn)：ArrayList和LinkedList。
集合相關(guān)操作
繼承自Collection的相關(guān)集合操作，基本都符合你期望的樣子。如果對(duì)這些不熟悉的話，請(qǐng)查看Collection接口。
需要提到的是，remove操作將會(huì)移除List中第一個(gè)出現(xiàn)的指定元素，add和addAll操作總是會(huì)將新的元素添加到原有List末尾。因此，下面的方法可以將一個(gè)List添加到另一個(gè)List后面。
list1.addAll(list2);
上面這種方式將會(huì)改變list1，可以通過下面的方式創(chuàng)建一個(gè)新的List來包含list1和list2。
List<Type> list3 = new ArrayList<Type>(list1);
list3.addAll(list2);
位置訪問和搜索操作
基本的位置訪問操作是get，set，add和remove。set和remove操作在元素被覆蓋和刪除之前會(huì)先返回舊的元素。別的操作(indexOf和lastIndexOf)將會(huì)返回從List中找到的第一個(gè)或者最后一個(gè)元素的索引。
addAll操作將指定的Collection中的所有元素，按照Collection的迭代順序插入到指定位置。此操作是Collection中的addAll的基于位置訪問版本。
下面是一個(gè)小方法用來交換List的兩個(gè)不同位置的元素。
public static void swap(List<E> list, int i, int j) {
E tmp = list.get(i);
list.set(i, list.get(j));
list.set(j, tmp);
}
當(dāng)然，這是一個(gè)多態(tài)算法：它可用來交換任意List的兩個(gè)元素，而忽略了List的實(shí)現(xiàn)類型。下面是另外一個(gè)多態(tài)算法，使用了前面的swap方法：
public static void shuffle(List<?> list, Random rnd) {
for (int i = list.size(); i > 1; i--) {
swap(list, i - 1, rnd.nextInt(i));
}
}
這個(gè)算法包含在Collections中，用來隨機(jī)打亂List。實(shí)際上，如果List的實(shí)現(xiàn)類型是LinkedList，此算法的平均運(yùn)行時(shí)間復(fù)雜度將會(huì)是O(n2)。因?yàn)殒湵砘谖恢玫牟檎倚什桓?，為O(n)。在Collections類中，shuffle方法的實(shí)現(xiàn)如下：
注意到，
shuffle方法會(huì)先去判斷List是否實(shí)現(xiàn)了RandomAccess類型，而RandomAccess實(shí)際上是一個(gè)空接口（不定義任何方法），基于名字也可以看出，它用來標(biāo)記子類實(shí)現(xiàn)是否為隨機(jī)訪問。在Java類庫(kù)中，List的實(shí)現(xiàn)者ArrayList類實(shí)現(xiàn)了此接口，而LinkedList沒有實(shí)現(xiàn)此接口。因此，從這里也可以看出，由于鏈表并非隨機(jī)訪問類型，其直接使用基于位置的混淆效率將會(huì)低下。針對(duì)這種并非隨機(jī)訪問的List，則先生成其數(shù)組形式的引用拷貝，對(duì)數(shù)組進(jìn)行位置混淆后，再將打亂的數(shù)組寫回List。注意不同的
List實(shí)現(xiàn)可能會(huì)影響到算法效率時(shí)，可以根據(jù)判斷List是否實(shí)現(xiàn)了RandomAccess接口來區(qū)分是否可隨機(jī)訪問這種技巧。
迭代器
List的iterator方法返回Iterator類型的迭代器。同時(shí)，還提供給一個(gè)增強(qiáng)版ListIterator，由listIterator返回。ListIterator可以讓你從兩個(gè)方向遍歷List，在迭代過程中修改列表，并且獲取當(dāng)前遍歷的位置。
ListIterator繼承自Iterator接口，繼承的三個(gè)方法(hasNext，next，remove)和Iterator接口的方法做完全一樣的事情。另外還包含了hasPrevious和previous方法，用來從后向前遍歷。從方法名可以看出，其是和hasNext和next方法相對(duì)應(yīng)的。
下面是一個(gè)標(biāo)準(zhǔn)的從后向前遍歷List的方法：
for (ListIterator<Type> it = list.listIterator(list.size()); it.hasPrevious(); ) {
Type t = it.previous();
……
}
注意到listIterator方法有兩種形式。無參數(shù)的形式返回一個(gè)位置位于List開始處的ListIterator，帶一個(gè)int參數(shù)的返回一個(gè)位于指定位置索引(index)的ListIterator。這里的位置索引(index)指向被首次next調(diào)用將會(huì)返回的元素。而index-1指向被首次previous調(diào)用的元素。在一個(gè)長(zhǎng)度為n的List中，index有n+1個(gè)有效的值：從0到n。
直觀地說，光標(biāo)位置總是位于兩個(gè)元素之間——一個(gè)由調(diào)用previous返回的元素和一個(gè)由調(diào)用next返回的元素。這n+1個(gè)有效index對(duì)應(yīng)于n個(gè)元素之間的n+1個(gè)間隙。下圖展示了一個(gè)包含四個(gè)元素的List可以有五個(gè)可能的光標(biāo)位置：
區(qū)間視圖操作
區(qū)間視圖操作subList(int fromIndex, int toIndex)返回一個(gè)原有List的部分List視圖，索引包括fromIndex，不包括toIndex。
注意：這個(gè)子List并非原有List的拷貝，實(shí)際上其為同一List，只不過只給你看你想要的那部分。作用在原有List上的操作將會(huì)影響到新的子List。如果修改了原有List，可能導(dǎo)致子List紊亂。同樣對(duì)子List進(jìn)行添加和刪除將會(huì)影響到原有List。
任何只需要考慮List一部分的范圍操作，都可以考慮用subList來進(jìn)行替代。比如，下面可以用來刪除List的一部分元素：
list.subList(fromIndex, toIndex).clear();
List算法
Collections類中的大部分算法都適用于List，下面是這些算法的一個(gè)總結(jié)：
- sort——使用歸并排序算法來對(duì)
List進(jìn)行排序 - shuffle——隨機(jī)打亂
List中的元素 - reverse——對(duì)
List進(jìn)行逆序操作 - rotate——以一個(gè)給定的距離旋轉(zhuǎn)
List中的所有元素 - swap—— 交換
List中指定位置的元素 - replaceAll——將在
List中所有出現(xiàn)的指定值替換為新的值 - fill ——用指定值覆蓋
List中所有元素 - copy——拷貝源
List到墓道目的List - binarySearch——使用二分查找算法在一個(gè)排好序的
List中查找給定的元素 - indexOfSubList——返回
List等于給定子List的第一個(gè)出現(xiàn)位置索引
_ lastIndexOfSubList——返回List中等于給定子List的最后一個(gè)出現(xiàn)位置索引
以上文章參考：
http://docs.oracle.com/javase/tutorial/collections/interfaces/list.html
