List是Collection三大直接子接口之一，其中的數據可以通過位置檢索，用戶可以在指定位置插入數據。List的數據可以為空，可以重復。以下是其文檔注釋，只看前兩段：

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements <tt>e1</tt> and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.

List特有方法

我們關注其不同于Collection的方法，主要有以下這些：

//在指定位置，將指定的集合插入到當前的集合中
boolean addAll(int index, Collection<? extends E> c);

//這是一個默認實現的方法，會通過Iterator的方式對每個元素進行指定的操作
default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        li.set(operator.apply(li.next()));
    }
}

//排序，依據指定的規(guī)則對當前集合進行排序，可以看到，排序是通過Arrays這個工具類完成的。
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

//獲取指定位置的元素
E get(int index);

//修改指定位置元素的值
E set(int index, E element);

//將指定元素添加到指定的位置
void add(int index, E element);

//將指定位置的元素移除
E remove(int index);

//返回一個元素在集合中首次出現的位置
int indexOf(Object o);

//返回一個元素在集合中最后一次出現的位置
int lastIndexOf(Object o);

//ListIterator繼承于Iterator，主要增加了向前遍歷的功能
ListIterator<E> listIterator();

//從指定位置開始，返回一個ListIterator
ListIterator<E> listIterator(int index);

//返回一個子集合[fromIndex, toIndex)，非結構性的修改返回值會反映到原表，反之亦然。
//如果原表進行了結構修改，則返回的子列表可能發(fā)生不可預料的事情
List<E> subList(int fromIndex, int toIndex);

通過以上對接口的分析可以發(fā)現，Collection主要提供一些通用的方法，而List則針對線性表的結構，提供了對位置以及子表的操作。

超級實現類：AbstractList

有了分析AbstractCollection的經驗，我們分析AbstractList就更容易了。首先也看下其文檔中強調的部分：

To implement an unmodifiable list, the programmer needs only to extend this class and provide implementations for the get(int) and size() methods.

To implement a modifiable list, the programmer must additionally override the set(int, E) method (which otherwise throws an UnsupportedOperationException). If the list is variable-size the programmer must additionally override the add(int, E) and remove(int) methods.

大致意思是說，要實現一個不可修改的集合，只需要復寫get和size就可以了。要實現一個可以修改的集合，還需要復寫set方法，如果要動態(tài)調整大小，就必須再實現add和remove方法。

然后看下其源碼實現了哪些功能吧：

//在AbstractCollection中，add方法默認會拋出異常，
//而在這里是調用了add(int index, E e)方法，但這個方法也是沒有實現的。
//這里默認會把元素添加到末尾。
public boolean add(E e) {
    add(size(), e);
    return true;
}

//同上，這個只需要進行一次遍歷即可
public boolean addAll(int index, Collection<? extends E> c) {
    //...   
}

接下來，還有幾個方法和Iterator與ListIterator息息相關，在AbstractList中有具體的實現，我們先看看它是如何把集合轉變成Iterator對象并支持foreach循環(huán)的吧。

我們追蹤源碼發(fā)現，在iterator()方法中直接返回了一個Itr對象

public Iterator<E> iterator() {
    return new Itr();
}

這樣我們就明白了，它是實現了一個內部類，這個內部類實現了Iterator接口，合理的處理hasNext、next、remove方法。這個源碼就不粘貼啦，其中僅僅在remove時考慮了一下多線程問題，有興趣的可以自己去看看。

另外一個就是ListIterator，

public ListIterator<E> listIterator() {
    return listIterator(0);
}

可以看到，listIterator方法依賴于listIterator(int index)方法。有了上邊的經驗，我們可以推測，它也是通過一個內部類完成的。

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);

    return new ListItr(index);
}

事實證明，和我們想的一樣，AbstractList內部還定義了一個ListItr，實現了ListIterator接口，其實現也很簡單，就不粘貼源碼啦。

接下來我們看看，利用這兩個實現類，AbstractList都做了哪些事情。

//尋找一個元素首次出現的位置，只需要從前往后遍歷，找到那個元素并返回其位置即可。
public int indexOf(Object o) {
    ListIterator<E> it = listIterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return it.previousIndex();
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return it.previousIndex();
    }
    return -1;
}

//同理，尋找一個元素最后一次出現的位置，只需要從列表最后一位向前遍歷即可。
//看到listIterator(int index)方法是可以傳遞參數的，這個我想我們都可以照著寫出來了。
public int lastIndexOf(Object o) {
    //...
}

//這個方法是把從fromIndex到toIndex之間的元素從集合中刪除。
//clear()方法也是調用這個實現的（我認為clear實現意義并不大，因為在其上級AbstractCollection中已經有了具體實現）。
protected void removeRange(int fromIndex, int toIndex) {
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

接下來還有兩塊內容比較重要，一個是關于SubList的，一個是關于equals和hashcode的。

我們先看看SubList相關的內容。SubList并不是新建了一個集合，只是持有了當前集合的引用，然后控制一下用戶可以操作的范圍，所以在接口定義時就說明了其更改會直接反應到原集合中。SubList定義在AbstractList內部，并且是AbstractList的子類。在AbstractList的基礎上增加了對可選范圍的控制。

equals和hashcode的實現，也關乎我們的使用。在AbstractList中，這兩個方法不僅與其實例有關，也和其內部包含的元素有關，所以在定義數據元素時，也應該復寫這兩個方法，以保證程序的正確運行。這里看下其源碼加深一下印象吧。

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        //這里用到了數據元素的equals方法
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        //這里用到了數據元素的hashCode方法
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

上一篇：Java集合源碼分析之超級接口：Collection

下一篇：Java集合源碼分析之List（二）：ArrayList

我是飛機醬，如果您喜歡我的文章，可以關注我~

編程之路，道阻且長。唯，路漫漫其修遠兮，吾將上下而求索。