Java集合(二)：List列表

Java集合(二)：List列表

在上一節中，介紹了Java集合的整體情況。從這節開始，將介紹具體的類。這裡不單單介紹類的用法，還會試圖從源碼的角度分析類的實現。這一節將介紹List接口及實現類，即列表中的鏈表LinkedList和數組列表ArrayList。

1 List接口及抽象類

List接口擴展自Collection接口，這個接口設計了一些適合列表操作的方法。List是一個有序集合，元素可以添加到容器中某個特定的位置。

使用javac編譯List.java源碼後，可以使用javap反編譯源碼獲得接口的具體信息，如下是調用後的結果：

Compiled from "List.java"
public interface java.util.List extends java.util.Collection {
  public abstract int size();
  public abstract boolean isEmpty();
  public abstract boolean contains(java.lang.Object);
  public abstract java.util.Iterator iterator();
  public abstract java.lang.Object[] toArray();
  public abstract  T[] toArray(T[]);
  public abstract boolean add(E);
  public abstract boolean remove(java.lang.Object);
  public abstract boolean containsAll(java.util.Collection);
  public abstract boolean addAll(java.util.Collection);
  public abstract boolean addAll(int, java.util.Collection);
  public abstract boolean removeAll(java.util.Collection);
  public abstract boolean retainAll(java.util.Collection);
  public void replaceAll(java.util.function.UnaryOperator);
  public void sort(java.util.Comparator);
  public abstract void clear();
  public abstract boolean equals(java.lang.Object);
  public abstract int hashCode();
  public abstract E get(int);
  public abstract E set(int, E);
  public abstract void add(int, E);
  public abstract E remove(int);
  public abstract int indexOf(java.lang.Object);
  public abstract int lastIndexOf(java.lang.Object);
  public abstract java.util.ListIterator listIterator();
  public abstract java.util.ListIterator listIterator(int);
  public abstract java.util.List subList(int, int);
  public java.util.Spliterator spliterator();
}

List接口提供了這些方法，大部分是Abstract的，但也有一部分不是，這部分方法是JDK 1.8 新增的default方法，比如sort方法。

List接口提供了隨機訪問方法，比如get(int)方法，但是List並不管這些方法都某個特定的實現是否高效。為了避免執行成本較高的隨機訪問操作，Java SE 1.4 引入了一個標記接口RandomAccess。這個接口沒有任何方法，但可以用來檢測一個特定的集合是否支持高效的隨機訪問：

if(c instanceof RandomAccess)
{
    use random access algorighm
}
else
{
    use sequential access algorithm
}

ArrayList就實現了這個接口。

List接口中的例行方法在抽象類AbstractList中實現了，這樣就不需要在具體的類中實現，比如isEmpty方法和contains方法等。這些例行方法比較簡單，含義也明顯。對於隨機訪問元素的類（比如ArrayList），優先繼承這個抽象類。

在AbstractList抽象類中，有一個重要的域，叫modCount：

protected transient int modCount = 0;

這個域可以用來跟蹤列表結構性修改的次數，什麼是結構性修改呢？就是改變列表長度的修改，比如增加、刪除等。對於只修改某個節點的值不算結構性修改。

這個域在後面的迭代器中非常有用。迭代器可以使用這個域來檢測並發修改問題，這個問題會在LinkedList類中介紹。

抽象類AbstractSequentialList實現了List接口中的一些方法，對於順序訪問元素的類（比如LinkedList），優先繼承這個抽象類。

2 鏈表：LinkedList

鏈表是一個大家非常熟悉的數據結構。鏈表解決了數組列表插入和刪除元素效率太低的問題，鏈表的插入和刪除就非常高效。

鏈表將每個對象存放在獨立的節點中。Java中的LinkedList鏈表，每個節點除了有後序節點的引用外，還有一個前序節點的引用，也就是說，LinkedList是一個雙向鏈表。

LinkedList類有三個域，分別是大小、頭結點和尾節點：

transient int size;
transient Node first;
transient Node last;

還有兩個構造器，一個無參構造器和一個含參構造器：

public java.util.LinkedList();
public java.util.LinkedList(java.util.Collection);

其中無參構造器構造一個空的鏈表，含參構造器根據傳進來的一個集合構造一個鏈表。

2.1 Node內部類

LinkedList類中，定義了一個Node內部類來表示一個節點。這個類的定義如下：

private static class Node {
    E item;
    Node next;
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

這是一個靜態內部類，也沒有對外部的引用，這個類有三個域：值，前序節點的引用，後序節點的引用，也有一個構造方法，定義很簡單。

如果要創建一個Node節點，可以這樣：

Node node=new Node<>(pre,item,next);

其中，pre和next分別是前序節點和後序節點的引用。

2.2 鏈表操作的基本方法

既然是鏈表，就少不了鏈表節點的添加與刪除。在LinkedList類中，提供了六個基本的鏈表操作的方法，這些方法都對鏈表的結構進行修改，因此會改變AbstractList類中的modCount域，這六個方法如下：

private void linkFirst(E);//在鏈表頭部添加給定值的節點作為頭結點
void linkLast(E);//在鏈表尾部添加一個給定值的節點作為尾節點
void linkBefore(E, java.util.LinkedList$Node);//在給定的節點前插入一個節點
private E unlinkFirst(java.util.LinkedList$Node);//刪除頭結點，並返回頭結點的值
private E unlinkLast(java.util.LinkedList$Node);//刪除尾節點，並返回尾節點的值
E unlink(java.util.LinkedList$Node);//刪除給定的節點

這些方法都是私有的（或包內私有的），因此可以稱為工具方法，LinkedList類中的所有結構性修改操作都是基於這六個方法實現的。

這六個方法都是鏈表的基本操作，代碼比較簡單，不過給出實現可以看看源碼實現者的寫法，對於自己編程還是有幫助的：

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node f = first;
        final Node newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node succ) {
        // assert succ != null;
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Unlinks non-null first node f.
     */
    private E unlinkFirst(Node f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null last node l.
     */
    private E unlinkLast(Node l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null node x.
     */
    E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
        final Node next = x.next;
        final Node prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

2.3 列表迭代器：ListIterator接口

鏈表是一個有序集合，每個對象的位置十分重要。LinkedList.add方法只是將節點加到尾部，然而對於鏈表的操作還有很大一部分需要將節點添加到鏈表中間。由於迭代器是秒數集合中的位置的，所以這種依賴位置的添加方法將由迭代器負責。只有對自然有序的集合使用迭代器添加元素才有意義。比如，對於無序的集合set，在Iterator接口中就沒有add方法。相反的，在集合類庫中提供了ListIterator接口，其中就有add方法：

interface ListIterator extends Iterator
{
    void add(E element);
    ...
}

與Collection接口中的add方法不同，這個方法不返回boolean類型的值，因為它假定添加操作總是改變鏈表。

另外，除了hasNext和next方法，ListIterator接口還提供了下面的兩個方法：

E previous();
boolean hasPrevious();

這兩個方法用來反向遍歷鏈表，previous也像next一樣，返回越過的對象。

LinkedList類的listIterator方法返回一個迭代器對象：

ListIterator iter=list.listIterator();

在介紹接口時我們知道，不能實例化一個接口對象，但可以聲明一個接口對象然後引用一個實現了該接口的類的實例。那麼listIterator方法返回的就必然是一個類的實例，而這個類也必然實現了這個接口，問題是，這個類是什麼？

這個類其實是LinkedList的一個內部類，即ListItr：

Compiled from "LinkedList.java"
class java.util.LinkedList$ListItr implements java.util.ListIterator {
  private java.util.LinkedList$Node lastReturned;
  private java.util.LinkedList$Node next;
  private int nextIndex;
  private int expectedModCount;
  final java.util.LinkedList this$0;
  java.util.LinkedList$ListItr(java.util.LinkedList, int);
  public boolean hasNext();
  public E next();
  public boolean hasPrevious();
  public E previous();
  public int nextIndex();
  public int previousIndex();
  public void remove();
  public void set(E);
  public void add(E);
  public void forEachRemaining(java.util.function.Consumer);
  final void checkForComodification();
}

上面也是使用javap反編譯的結果。可以看到，這個內部類實現了ListIterator接口，並實現了這個接口的方法。

這正是理解迭代器的關鍵。我們知道，迭代器可以看做是一個位置，這個位置在兩個節點的中間，也就是說，對於一個大小為n的鏈表，迭代器的位置有n+1個：

| a | b | ...| z |

在這個例子中，鏈表表示26個字母，迭代器的位置就有27個。

這裡也是把迭代器形象化為光標，next方法就是光標移到下一個位置，飯後返回剛剛越過的元素，同理previous也是一樣，只不過是左移一個位置，然後返回剛剛越過的元素。下面是這兩個方法的代碼：

public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();

    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();

    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

這兩個方法首先調用checkForComodifcation方法檢查並發修改問題。前面說過，AbstractList的modCount記錄了鏈表的修改次數，而每一個迭代器都通過下面的字段維護一個獨立的計數器：

private int expectedModCount = modCount;

這個域初始化為類的modCount修改次數。而checkForComodification檢查迭代器自己維護的計數器是否和類的modCount相等，如果不等，就會拋出一個ConcurrentModificationException。

並發修改檢查通過後，會調用hasNext或hasPrevious方法檢查是否有待訪問的元素。ListItr類有一個nextIndex域：

private int nextIndex;

這個域維護迭代器的當前位置，當然，對於LinkedList來說，由於迭代器指向兩個元素中間，所以可以同時產生兩個索引：nextIndex方法返回下一次調用next方法時返回元素的整數索引；previousIndex返回下一次調用previous方法時返回元素的索引，這個索引比nextIndex小1。

hasNext和hasPrevious方法就是檢查nextIndex和previousIndex是否在正確范圍來確實是否有待訪問元素的。

ListItr類還有兩個域：

private Node lastReturned;
private Node next;

lastReturned用來保存上次返回的節點，next就是迭代器位置的下一個元素，也可以看做光標的下一個元素（下一個元素總是光標的右面那個元素）。調用next方法後，光標右移一位，越過next域保存的節點，然後更新這兩個域的值，即剛才的next變為lastReturned，next就是再下一個元素，然後nextIndex增1。

previous相對於next操作來說相當於光標左移一位，在更新lastReturned和next時，需要考慮next是否為null。如果next為null，說明在沒執行previous時，迭代器在最後一個位置，所以執行previous後，next應該是鏈表的尾節點last；如果next不是null，那麼next更新為next的前序節點。而lastReturned為光標剛越過的元素，即現在的next節點，這時，lastReturned和next節點指向同一個元素。

ListItr類有三個可以修改鏈表的方法：add、remove和set。其中add和remove會改變迭代器的位置，因為這兩個方法修改了鏈表的結構；而set方法不會修改迭代器的位置，因為它不修改鏈表的結構。

這三個方法的代碼如下：

public void remove() {
    checkForComodification();
    if (lastReturned == null)
        throw new IllegalStateException();

    Node lastNext = lastReturned.next;
    unlink(lastReturned);
    if (next == lastReturned)
        next = lastNext;
    else
        nextIndex--;
    lastReturned = null;
    expectedModCount++;
}

public void set(E e) {
    if (lastReturned == null)
        throw new IllegalStateException();
    checkForComodification();
    lastReturned.item = e;
}

public void add(E e) {
    checkForComodification();
    lastReturned = null;
    if (next == null)
        linkLast(e);
    else
        linkBefore(e, next);
    nextIndex++;
    expectedModCount++;
}

值得注意的是remove方法。在每次調用remove方法後，都會將lastReturned置為null。也就是說，如果連續調用remove方法，第二次調用就會拋出一個IllegalStateException異常。因此，remove操作必須跟在next或previous操作之後。

現在已經介紹了ListIterator接口的基本方法，可以從前後兩個方向遍歷鏈表中的元素，並可以添加、刪除元素。

記住一點：鏈表的任意位置添加與刪除節點的操作是ListIterator迭代器提供的，類本身的add方法只能在結尾添加。

2.4 隨機訪問

在Java類庫中，還提供了許多理論上存在一定爭議的方法。鏈表不支持快速隨機訪問。如果要查看鏈表中的第n個元素，就必須從頭開始，越過n-1個元素，沒有捷徑可走。鑒於這個原因，在程序需要采用整數索引訪問元素時，一般不選用鏈表。

盡管如此，LinkedList類還提供了一個用來訪問某個特定元素的get方法：

LinkedList list=...;
String s=list.get(n);

當然，這個方法的效率不太高。絕不應該使用這種讓人誤解的隨機訪問方法來遍歷鏈表。下面的代碼效率極低：

for(int i=0;i

每次查找一個元素都要從頭開始重新搜索。LinkedList對象根本不做任何緩存位置信息的處理。
其實，在LinkedList類中，get方法會判斷當前的位置距離頭和尾哪一端更近，然後判斷從左向右遍歷還是從右向左遍歷。
2.5 例子
下面的代碼演示了LinkedList類的基本操作。它簡單的創建兩個鏈表，將它們合並在一起，然後從第二個鏈表中每間隔一個元素刪除一個元素，最後測試removeAll方法：

import java.util.*;
public class LinkedListTest {
    public static void main(String[] args) {
        List a=new LinkedList<>();
        a.add("A");
        a.add("C");
        a.add("E");

        List b=new LinkedList<>();
        b.add("B");
        b.add("D");
        b.add("F");
        b.add("G");

        ListIterator aIter=a.listIterator();
        Iterator bIter=b.iterator();

        while(bIter.hasNext()){
            if(aIter.hasNext())aIter.next();
            aIter.add(bIter.next());
        }
        System.out.println(a);

        bIter=b.iterator();
        while(bIter.hasNext()){
            bIter.next();
            if(bIter.hasNext()){
                bIter.next();
                bIter.remove();
            }
        }
        System.out.println(b);

        a.removeAll(b);
        System.out.println(a);
    }
}
結果如下：




3 數組列表：ArrayList
前面介紹了List接口和實現了這個接口的LinkedList類。List接口用於描述一個有序集合，並且集合中每個元素的位置十分重要。有兩種訪問元素的協議：一種是用迭代器，另一種使用get和set方法隨機訪問每個元素。後者不適用於鏈表，但對數組很有用。集合類庫提供了一個大家非常熟悉的ArrayList類，這個類也實現了List接口。ArrayList類封裝了一個動態再分配的對象數組。
Java集合類庫中還有一個動態數組：Vector類。不過這個類的所有方法是同步的，可以由兩個線程安全的訪問一個Vector對象。但是，如果一個線程訪問Vector，代碼要在同步上消耗大量的時間。而ArrayList方法不是同步的，因此，如果不需要同步時使用ArrayList。
在ArrayList詳解中詳細介紹了類的實現及方法的使用。