Java 集合深入理解：List

wqux9633 8年前發布 | 10K 次閱讀 Java Java開發

藍瘦！香菇！連著加班，一篇文章寫了好幾天，心好痛！

在 Java 集合深入理解：Collection 中我們熟悉了 Java 集合框架的基本概念和優點，也了解了根接口之一的 Collection，這篇文章來加深 Collection 的子接口之一List的熟悉。

List 接口

一個 List 是一個元素有序的、可以重復、可以為 null的集合（有時候我們也叫它“序列”）。

Java 集合框架中最常使用的幾種 List 實現類是 ArrayList，LinkedList 和 Vector。在各種 List 中，最好的做法是以 ArrayList 作為默認選擇。當插入、刪除頻繁時，使用 LinkedList，Vector 總是比 ArrayList 慢，所以要盡量避免使用它，具體實現后續文章介紹。

為什么 List 中的元素 “有序”、“可以重復”呢?

首先，List 的數據結構就是一個序列，存儲內容時直接在內存中開辟一塊連續的空間，然后將空間地址與索引對應。

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.

可以看到，List 接口的實現類在實現插入元素時，都會根據索引進行排列。

比如 ArrayList，本質是一個數組：

LinkedList, 雙向鏈表：

由于 List 的元素在存儲時互不干擾，沒有什么依賴關系，自然可以重復（這點與 Set 有很大區別）。

List 接口定義的方法

List 中除了繼承Collection 的一些方法，還提供以下操作：

位置相關： List 和數組一樣，都是從 0 開始，我們可以根據元素在 list 中的位置進行操作，比如說 get , set , add , addAll , remove ;
搜索：從 list 中查找某個對象的位置，比如 indexOf , lastIndexOf ;
迭代：使用Iterator的拓展版迭代器ListIterator 進行迭代操作;
范圍性操作：使用 subList 方法對 list 進行任意范圍的操作。

Collection 中提供的一些方法就不介紹了，不熟悉的可以去看一下。

集合的操作

remove(Object)
- 用于刪除 list 中頭回出現的指定對象；
add(E) , addAll(Collection<? extends E>)
- 用于把新元素添加到 list 的尾部，下面這段語句使得 list3 等于 list1 與 list2 組合起來的內容：
  
  List list3 = new ArrayList(list1);
  
  list3.addAll(list2);
注意：上述使用了 ArrayList 的轉換構造函數:

public ArrayList(Collection

Object 的 equlas () 方法默認和 == 一樣，比較的是地址是否相等。

public boolean equals(Object o) {
    return this == o;
}

因此和 Set，Map 一樣，List 中如果想要根據兩個對象的內容而不是地址比較是否相等時，需要重寫 equals() 和 hashCode() 方法。 remove() , contains() , indexOf() 等等方法都需要依賴它們：

@Override 
public boolean contains(Object object) {
    Object[] a = array;
    int s = size;
    if (object != null) {
        for (int i = 0; i < s; i++) {
            //需要重載 Object 默認的 equals 
            if (object.equals(a[i])) {
                return true;
            }
        }
    } else {
        for (int i = 0; i < s; i++) {
            if (a[i] == null) {
                return true;
            }
        }
    }
    return false;
}

@Override
 public int indexOf(Object object) {
    Object[] a = array;
    int s = size;
    if (object != null) {
        for (int i = 0; i < s; i++) {
            if (object.equals(a[i])) {
                return i;
            }
        }
    } else {
        for (int i = 0; i < s; i++) {
            if (a[i] == null) {
                return i;
            }
        }
    }
    return -1;
}

兩個 List 對象的所有位置上元素都一樣才能相等。

位置訪問，搜索

基礎的位置訪問操作方法有：

get , set , add , remove
- set, remove 方法返回的是 被覆蓋 或者 被刪除 的元素；
indexOf , lastIndexOf
- 返回指定元素在 list 中的首次出現/最后一次出現的位置（獲取 lastIndexOf 是通過倒序遍歷查找）;
addAll(int,Collection)
- 在特定位置插入指定集合的所有元素。這些元素按照迭代器 Iterator 返回的先后順序進行插入；

下面是一個簡單的 List 中的元素交換方法：

public static <E> void swap(List<E> a, int i, int j) {
    E tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

不同的是它是多態的，允許任何 List 的子類使用。 Collections 中的 shuffle 就有用到和下面這種相似的交換方法：

public static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}

這種算法使用指定的隨機算法，從后往前重復的進行交換。和一些其他底層 shuffle 算法不同，這個算法更加公平（隨機方法夠隨機的話，所有元素的被抽到的概率一樣），同時夠快（只要 list.size() -1 ）次交換。

局部范圍操作

List.subList(int fromIndex, int toIndex) 方法返回 List 在 fromIndex 與 toIndex 范圍內的子集。注意是左閉右開，[fromIndex,toIndex)。

注意！ List.subList 方法并沒有像我們想的那樣：創建一個新的 List，然后把舊 List 的指定范圍子元素拷貝進新 List，根！本！不！是！

subList 返回的扔是 List 原來的引用，只不過把開始位置 offset 和 size 改了下，見 List.subList() 在 AbstractList 抽象類中的實現：

public List<E> subList(int start, int end) {
    if (start >= 0 && end <= size()) {
        if (start <= end) {
            if (this instanceof RandomAccess) {
                return new SubAbstractListRandomAccess<E>(this, start, end);
            }
            return new SubAbstractList<E>(this, start, end);
        }
        throw new IllegalArgumentException();
    }
    throw new IndexOutOfBoundsException();
}

SubAbstractListRandomAccess 最終也是繼承 SubAbstractList,直接看 SubAbstractList：

SubAbstractList(AbstractList<E> list, int start, int end) {
        fullList = list;
        modCount = fullList.modCount;
        offset = start;
        size = end - start;
    }

可以看到，的確是保持原來的引用。

所以，重點來了！

由于 subList 持有 List 同一個引用，所以對 subList 進行的操作也會影響到原有 List，舉個栗子：

你猜運行結果是什么？

驗證了上述重點。

所以，我們可以使用 subList 對 List 進行范圍操作，比如下面的代碼，一句話實現了刪除 shixinList 部分元素的操作：

shixinList.subList(fromIndex, toIndex).clear();

還可以查找某元素在局部范圍內的位置：

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

List 與 Array 區別？

List 在很多方面跟 Array 數組感覺很相似，尤其是 ArrayList，那 List 和數組究竟哪個更好呢？

相似之處：
- 都可以表示一組同類型的對象
- 都使用下標進行索引
不同之處：
- 數組可以存任何類型元素
- List 不可以存基本數據類型，必須要包裝
- 數組容量固定不可改變；List 容量可動態增長
- 數組效率高; List 由于要維護額外內容，效率相對低一些

容量固定時優先使用數組，容納類型更多，更高效。

在容量不確定的情景下， List 更有優勢，看下 ArrayList 和 LinkedList 如何實現容量動態增長：

ArrayList 的擴容機制:

public boolean add(E object) {
    Object[] a = array;
    int s = size;
    //當放滿時，擴容
    if (s == a.length) {
        //MIN_CAPACITY_INCREMENT 為常量，12
        Object[] newArray = new Object[s +
                (s < (MIN_CAPACITY_INCREMENT / 2) ?
                 MIN_CAPACITY_INCREMENT : s >> 1)];
        System.arraycopy(a, 0, newArray, 0, s);
        array = a = newArray;
    }
    a[s] = object;
    size = s + 1;
    modCount++;
    return true;
}

可以看到：

當 ArrayList 的元素個數小于 6 時，容量達到最大時，元素容量會擴增 12；
反之，增加當前元素個數的一半。

LinkedList 的擴容機制：

public boolean add(E object) {
    return addLastImpl(object);
}

private boolean addLastImpl(E object) {
    Link<E> oldLast = voidLink.previous;
    Link<E> newLink = new Link<E>(object, oldLast, voidLink);
    voidLink.previous = newLink;
    oldLast.next = newLink;
    size++;
    modCount++;
    return true;
}

可以看到，沒！有！擴容機制！

這是由于 LinedList 實際上是一個雙向鏈表，不存在元素個數限制，使勁加就行了。

transient Link<E> voidLink;

private static final class Link<ET> {
    ET data;

    Link<ET> previous, next;

    Link(ET o, Link<ET> p, Link<ET> n) {
        data = o;
        previous = p;
        next = n;
    }
}

List 與 Array 之間的轉換

在 List 中有兩個轉換成數組的方法：

Object[] toArray()
- 返回一個包含 List 中所有元素的數組；
T[] toArray(T[] array)
- 作用同上，不同的是當參數 array 的長度比 List 的元素大時，會使用參數 array 保存 List 中的元素；否則會創建一個新的數組存放 List 中的所有元素；

ArrayList 中的實現：

public Object[] toArray() {
    int s = size;
    Object[] result = new Object[s];
    //這里的 array 就是 ArrayList 的底層實現，直接拷貝
    //System.arraycopy 是底層方法，效率很高
    System.arraycopy(array, 0, result, 0, s);
    return result;
}

public <T> T[] toArray(T[] contents) {
    int s = size;
    //先判斷參數能不能放下這么多元素
    if (contents.length < s) {
        //放不下就創建個新數組
        @SuppressWarnings("unchecked") T[] newArray
            = (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
        contents = newArray;
    }
    System.arraycopy(this.array, 0, contents, 0, s);
    if (contents.length > s) {
        contents[s] = null;
    }
    return contents;
}

LinkedList 的實現：

public Object[] toArray() {
    int index = 0;
    Object[] contents = new Object[size];
    Link<E> link = voidLink.next;
    while (link != voidLink) {
        //挨個賦值，效率不如 ArrayList
        contents[index++] = link.data;
        link = link.next;
    }
    return contents;
}

@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] contents) {
    int index = 0;
    if (size > contents.length) {
        Class<?> ct = contents.getClass().getComponentType();
        contents = (T[]) Array.newInstance(ct, size);
    }
    Link<E> link = voidLink.next;
    while (link != voidLink) {
        //還是比 ArrayList 慢
        contents[index++] = (T) link.data;
        link = link.next;
    }
    if (index < contents.length) {
        contents[index] = null;
    }
    return contents;
}

數組工具類 Arrays 提供了數組轉成 List 的方法 asList :

@SafeVarargs
public static <T> List<T> asList(T... array) {
    return new ArrayList<T>(array);
}

使用的是 Arrays 內部創建的 ArrayList 的轉換構造函數：

private final E[] a;
    ArrayList(E[] storage) {
        if (storage == null) {
            throw new NullPointerException("storage == null");
        }
        //直接復制
        a = storage;
    }

迭代器 Iterator, ListIterator

List 繼承了Collection 的 iterator() 方法，可以獲取Iterator，使用它可以進行向后遍歷。

在此基礎上，List 還可以通過 listIterator(), listIterator(int location) 方法（后者指定了游標的位置）獲取更強大的迭代器ListIterator。

使用 ListIterator 可以對 List 進行向前、向后雙向遍歷，同時還允許進行 add, set, remove 等操作。

List 的實現類中許多方法都使用了 ListIterator，比如 List.indexOf() 方法的一種實現：

public int indexOf(E e) {
    for (ListIterator<E> it = listIterator(); it.hasNext(); )
        if (e == null ? it.next() == null : e.equals(it.next()))
            return it.previousIndex();
    // Element not found
    return -1;
}

ListIterator 提供了 add, set, remove 操作，他們都是對迭代器剛通過 next(), previous()方法迭代的元素進行操作。下面這個栗子中，List 通過結合 ListIterator 使用，可以實現一個多態的方法，對所有 List 的實現類都適用：

public static <E> void replace(List<E> list, E val, E newVal) {
    for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
        if (val == null ? it.next() == null : val.equals(it.next()))
            it.set(newVal);
}

List 的相關算法：

集合的工具類 Collections 中包含很多 List 的相關操作算法：

sort ，歸并排序
shuffle ，隨機打亂
reverse ，反轉元素順序
swap ，交換
binarySearch ，二分查找
……

來自：http://blog.csdn.net/u011240877/article/details/52802849

本文由用戶 wqux9633 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1476324728282.html

Java Java開發

Java 集合深入理解：List

List 接口

為什么 List 中的元素 “有序”、“可以重復”呢?

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.

List 接口定義的方法

List 中除了繼承Collection 的一些方法，還提供以下操作：

集合的操作

Object 的 equlas () 方法默認和 == 一樣，比較的是地址是否相等。

位置訪問，搜索

下面是一個簡單的 List 中的元素交換方法：

局部范圍操作

List 與 Array 區別？

List 在很多方面跟 Array 數組感覺很相似，尤其是 ArrayList，那 List 和數組究竟哪個更好呢？

容量固定時優先使用數組，容納類型更多，更高效。

在容量不確定的情景下， List 更有優勢，看下 ArrayList 和 LinkedList 如何實現容量動態增長：

List 與 Array 之間的轉換

在 List 中有兩個轉換成數組的方法：

ArrayList 中的實現：

LinkedList 的實現：

數組工具類 Arrays 提供了數組轉成 List 的方法 asList :

迭代器 Iterator, ListIterator

List 繼承了Collection 的 iterator() 方法，可以獲取Iterator，使用它可以進行向后遍歷。

List 的實現類中許多方法都使用了 ListIterator，比如 List.indexOf() 方法的一種實現：

List 的相關算法：

集合的工具類 Collections 中包含很多 List 的相關操作算法：

sort ，歸并排序

shuffle ，隨機打亂

reverse ，反轉元素順序

swap ，交換

binarySearch ，二分查找

……

相關經驗

相關資訊

相關文檔

目錄

Java 集合深入理解：List

List 接口

為什么 List 中的元素 “有序”、“可以重復”呢?

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.

List 接口定義的方法

List 中除了繼承Collection 的一些方法，還提供以下操作：

集合的操作

Object 的 equlas () 方法默認和 == 一樣，比較的是地址是否相等。

位置訪問，搜索

下面是一個簡單的 List 中的元素交換方法：

局部范圍操作

List 與 Array 區別？

List 在很多方面跟 Array 數組感覺很相似，尤其是 ArrayList，那 List 和數組究竟哪個更好呢？

容量固定時優先使用數組，容納類型更多，更高效。

在容量不確定的情景下， List 更有優勢，看下 ArrayList 和 LinkedList 如何實現容量動態增長：

List 與 Array 之間的轉換

在 List 中有兩個轉換成 數組 的方法：

ArrayList 中的實現：

LinkedList 的實現：

數組工具類 Arrays 提供了數組轉成 List 的方法 asList :

迭代器 Iterator, ListIterator

List 繼承了Collection 的 iterator() 方法，可以獲取Iterator，使用它可以進行向后遍歷。

List 的實現類中許多方法都使用了 ListIterator，比如 List.indexOf() 方法的一種實現：

List 的相關算法：

集合的工具類 Collections 中包含很多 List 的相關操作算法：

sort ，歸并排序

shuffle ，隨機打亂

reverse ，反轉元素順序

swap ，交換

binarySearch ，二分查找

……

相關經驗

相關資訊

相關文檔

目錄

在 List 中有兩個轉換成數組的方法：