Java集合深入理解:List(藍瘦,香菇,這些我怎麼才知道!)

2021-03-02 程序人生

在 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) 

add(E), addAll(Collection<? extends E>)

注意：上述使用了 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 

indexOf, lastIndexOf 

addAll(int,Collection) 

下面是一個簡單的 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 更有優勢，看下 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;}

可以看到：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() 

T[] toArray(T[] array) 

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 :

@SafeVarargspublic 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, ListIteratorList 繼承了 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 ，二分查找

……

具體實現我們後續介紹，感謝關注！

關聯： Collection, ListIterator, Collections

Thanks:

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/List.html

https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

http://blog.csdn.net/mazhimazh/article/details/17759579#comments

http://www.blogjava.net/flysky19/articles/92775.html

出處：http://blog.csdn.net/u011240877/article/details/52802849
聲明：版權歸原作者所有。




相關焦點

  • java集合【6】——— Iterable接口
    iterable接口整個接口框架關係如下（來自百度百科）：iterable接口其實是java集合大家庭的最頂級的接口之一了，實現這個接口，可以視為擁有了獲取迭代器的能力。內部定義的方法 java集合最源頭的接口，實現這個接口的作用主要是集合對象可以通過迭代器去遍歷每一個元素。
  • 藍瘦香菇原版視頻 藍瘦香菇是什麼意思 藍瘦香菇表情包
    藍瘦香菇是什麼意思近日，小編的朋友圈被「藍瘦香菇」刷屏，剛開始小編看得還是一臉懵逼，不知所云，相信很多網友也跟小編一樣。於是小編決定一探究竟，終於挖出了「藍瘦香菇」的意思，同時還有藍瘦香菇的原版視頻和藍瘦香菇表情包，感興趣的朋友不妨來看一看，樂一樂~
  • 藍瘦香菇到底是什麼梗?
    來源：文案袋（ID:CWtoday）,本文經作者授權發布，文案君編輯藍瘦香菇到底是什麼梗？今天，朋友圈和微博都被莫名其妙的「藍瘦香菇」刷屏了！！！「藍瘦，香菇」什麼鬼？明天就真的沒法愉快的好好聊天了！（咳咳，敲黑板...）
  • 「藍瘦香菇」英語怎麼說?
    吉米老師有預感，「藍瘦香菇」這個詞會成為繼「洪荒之力」universe power「身體被掏空」body empty 之後，2016年又一個全民網絡熱詞social catchword。Actually，這個「藍瘦香菇」的梗來自於一位廣西南寧小哥brother，他在失戀disappointed in love之後錄record了下面一個短視頻video。
  • 輕鬆 「藍瘦香菇」刷屏了嗎?不知道就out了!「藍瘦香菇」吉他彈唱版都出來了!
    這兩天，微博和朋友圈被一個新詞給刷屏了："藍瘦，香菇"，還出了一系列的表情包。
  • 【驚呆】你以為「藍瘦 香菇」=難受想哭?錯了!
    昨天懷遠三胞胎姐妹過冬的衣服終於有了著落，那些好心人的善舉感動的小編藍瘦香菇.最近，小編看了《麻雀》最後幾集，那劇情，嘖嘖嘖，感動的藍瘦香菇.什麼，你還不知道啥是「藍瘦香菇」？？來，看看百度百科的標準答案：
  • 突然火了的「藍瘦香菇」是個什麼鬼?
    朋友圈都被「藍瘦，香菇」這兩個詞給刷爆了到底是什麼鬼啊？鬼知道他經歷了什麼？？...
  • 別「藍瘦,香菇」了,本月有這些好電影陪伴你!
    藍瘦和香菇這到底是什麼鬼？你聽到的字幕：藍瘦，香菇，本來新顛，高高興興，泥為什莫要說射種話？藍瘦，香菇，賽射裡，第一翅，為一個女孩屎射麼香菇，藍瘦。泥為什莫要說射種話，丟我一個人賽射裡，香菇，藍瘦，賽射裡，香菇。字幕翻譯：難受，想哭。本來今天，高高興興，你為什麼要說這種話？
  • 【六點日常0/1】我的愛在哪裡 藍瘦 香菇
    藍瘦，香菇是什麼意思?為何一夜刷爆朋友圈，微博，空間?你以為藍瘦 真的是纖體產品，香菇真的是吃的香菇嗎?那你就真的錯了，那麼就由今天的任務發布人我（大逗）來正解一下(知道詳情的小夥伴請無視跳過直接接取任務)。　　南寧一小哥失戀後錄的視頻，小哥因為女友和他分手了，他很難受也很想哭，藍瘦，香菇，本來今顛高高興興，泥為什莫要說這種話?藍瘦，香菇在這裡。
  • 藍瘦,香菇 這普通話,誰教的?
    最近，「藍瘦、香菇」突然就火了，「香菇」我還知道是個什麼東西，那麼「藍瘦」又是什麼鬼？
  • 「藍瘦香菇」英文怎麼說?這倆翻譯神了!
    「藍瘦香菇」，這猛地一看小譯還以為是哪裡培育了能減肥變瘦的新型香菇呢，結果卻是「難受、想哭」的廣西方言版本，那麼問題來了，「藍瘦香菇」的英文要怎麼說呢？「藍瘦香菇」到底是什口音嘞？
  • java集合詳解合集
    Java集合類基本概念在編程中，常常需要集中存放多個數據。從傳統意義上講，數組是我們的一個很好的選擇，前提是我們事先已經明確知道我們將要保存的對象的數量。所以的集合類都位於java.util包下，後來為了處理多線程環境下的並發安全問題，java5還在java.util.concurrent包下提供了一些多線程支持的集合類。在學習Java中的集合類的API、編程原理的時候，我們一定要明白，"集合"是一個很古老的數學概念，它遠遠早於Java的出現。
  • 藍瘦香菇飯,來賓開一家?
    據人民網消息，隨著藍瘦香菇的火爆，各種衍生周邊也是各盡其才、層出不窮。近日，在廣西大學南苑食堂便是把握商機，創新推出了「藍瘦香菇蓋澆飯」，價格實惠量又足，師弟師妹們火熱追捧，厲害了我的哥~小編不禁想問，什麼時候到來賓開個連鎖店喂？~人民網報導：日前,一名南寧小夥子發布的告白視頻走紅網絡,其帶著壯語口音的「藍瘦香菇」風靡全國。
  • 藍瘦香菇(難受想哭)?在麗江發生的這10件事情才真的讓你香菇(想哭)!
    朋友圈都被「藍瘦，香菇」這兩個詞給刷爆了到底是什麼鬼啊？...原來是一個廣西小夥失戀後操著一口純正的廣西普通話錄製了一個視頻結果居然火了普通群眾聽到的字幕：藍瘦，香菇，本來新顛，高高興興，泥為什莫要說射種話？
  • 藍瘦香菇!這是什麼鬼……
    告訴我不是一個人，第一次看到這個圖的時候感覺眼睛裡進了風油精。
  • 藍瘦香菇火了!還改編唱了出來……城會玩
    感謝大家對我的支持 我會更加努力更新好文章給大家看 也許還有新來的不知道怎麼看以前我更新的文章 進入公眾號後 你可以看到精彩回顧點進去就行了 或者進入公眾號點右上角查看歷史信息也可以！！（關注ID：dnb5566）
  • 這些 Java 8 官方挖的坑,你踩過幾個?
    Stream很高大上，List轉Map卻全失敗……這些JDK8官方挖的坑，你踩過幾個？02被吞噬的異常：我不敢說出你的名字這個問題理解起來還是蠻費腦子的，所以我把這個系統異常發生的過程提煉成了一個美好的故事，放鬆一下，吟詩一首！
  • 原創┃古代美女對「藍瘦香菇」有另一種理解?
    藍瘦，香菇在這裡。第一翅（次）為一個女孩屎（子）這麼香菇，藍瘦。泥（你）為什莫（麼）要說射（這）種話，丟我一個人在這裡。「藍瘦，香菇」的釋義是：「難受，想哭」。因為廣西壯語裡面的發音沒有翹舌音，沒有送氣音。其實大部分的網友很「香菇」，並不是因為失戀，而是太胖真的很藍（難）瘦。那麼古代的愛美人士如何保持身材呢？古代的胖紙們會不會「藍（難）瘦」和「香菇」呢？
  • 刷爆朋友圈的【藍瘦 香菇】到底是什麼鬼!!!
    如果你還不知道這是什麼梗，明天就真的沒法愉快的好好聊天了！（咳咳，敲黑板...）不明真相的吃瓜群眾們，看完這個視頻你知道是腫麼回事了！這兩天，你是不是無緣無故被「藍瘦香菇」四個字刷屏了？ 原話是這樣：藍瘦，香菇，本來今顛高高興興，泥為什莫要說這種話？藍瘦，香菇在這裡。第一翅為一個女孩屎這麼香菇，藍瘦。泥為什莫要說射種話，丟我一個人在這裡。看不懂？給大家翻譯一下：難受，想哭，本來今天高高興興，你為什麼要說這種話？難受，想哭在這裡。第一次為一個女孩子這麼想哭，難受。你為什麼要說這種話，丟我一個人在這裡。
  • 蘑菇開會,藍瘦香菇怎麼沒來——不能錯過的蘑菇大全
    最近有個藍瘦香菇的段子很火