集合概述

Java集合框架標(biāo)準(zhǔn)化了Java處理對(duì)象組的方式。Java集合框架在JDK1.2版本提出屿衅，在JDK1.5版本進(jìn)行了修改(引入了泛型埃难、自動(dòng)裝箱/拆箱以及for-each格式循環(huán))。
集合框架再設(shè)計(jì)之初有幾個(gè)目標(biāo)：

• 框架是高性能的涤久，基本集合(動(dòng)態(tài)數(shù)組涡尘、鏈表、樹响迂、哈希表等)的實(shí)現(xiàn)是高效的考抄。
• 框架必須允許不同類型的集合以類似的方式進(jìn)行工作，并且有很高的互操作性。
• 擴(kuò)展或改造集合必須是容易實(shí)現(xiàn)的
• 比如添加可以將標(biāo)準(zhǔn)數(shù)組集成到集合框架的機(jī)制。

Java集合框架由以下幾部分組成：

• 接口：表示集合抽象的數(shù)據(jù)類型测暗。接口允許我們操作集合時(shí)不需要關(guān)注具體的實(shí)現(xiàn)芥丧，從而達(dá)到多態(tài)。
• 實(shí)現(xiàn)類：集合接口的具體實(shí)現(xiàn)，是重用性很高的數(shù)據(jù)結(jié)構(gòu)。
• 算法：根據(jù)需要對(duì)實(shí)現(xiàn)類實(shí)現(xiàn)的集合進(jìn)行計(jì)算，比如排序丢早、搜索。

Java集合框架除了定義集合相關(guān)的數(shù)據(jù)結(jié)構(gòu)诫给，還定義了映射的數(shù)據(jù)結(jié)構(gòu)香拉。雖然映射是集合框架的一部分，但是嚴(yán)格意義上映射并不是集合中狂。

image.png

Iterator迭代器

再看集合實(shí)現(xiàn)前凫碌，我們需要先看下迭代器，因?yàn)槲覀兿胍闅v集合胃榕、獲取或者移除元數(shù)時(shí)盛险，都需要使用迭代器，而實(shí)現(xiàn)Iterator接口是使用迭代器的方法之一勋又。
迭代器是一種模式苦掘，它可以使得遍歷序列方式和被遍歷對(duì)象分離。即我們無(wú)需該序列的底層結(jié)構(gòu)是什么樣子楔壤，只要拿到迭代器對(duì)象就可以遍歷該序列鹤啡。

Enumeration接口

在Iterator接口之前，Java在1.0版本采用的是Enumeration接口作為迭代器接口蹲嚣，但是該接口在當(dāng)初設(shè)計(jì)沒有考慮全面递瑰，比如它只包含了兩個(gè)方法祟牲。

public interface Enumeration<E> {
    /**
     * 是否還有元素
     */
    boolean hasMoreElements();

    /**
     * 返回下一個(gè)元素
     */
    E nextElement();
}

我們可以看到在JDK1.0版本提供需要使用迭代器的類都還是繼承的Enumeration，比如StringTokenizer類就是實(shí)現(xiàn)了Enumeration接口抖部。但是從JDK2.0開始说贝，官方使用Iterator接口代替了Enumeration接口，所以當(dāng)我們需要實(shí)現(xiàn)使用迭代器功能的類時(shí)記得要使用Iterator接口慎颗。

Iterator

Iterator被定義為集合上的迭代器乡恕。Iterator取代了Enumeration，它們二者的主要區(qū)別為：

• Iterator允許調(diào)用方在遍歷過(guò)程中俯萎，以正確的方式刪除元素
• 對(duì)方法名稱進(jìn)行了改進(jìn)傲宜，Enumeration中的方法名稱太長(zhǎng)了。

public interface Iterator<E> {
    /**
     * 迭代中是否還是更多元素
     */
    boolean hasNext();

    /**
     * 返回迭代中的下一個(gè)元素.
     * 如果沒有下一個(gè)元素夫啊，應(yīng)該拋出NoSuchElementException蛋哭。
     */
    E next();

    /**
     * 從迭代器指向的Collection中移除迭代器返回最后一個(gè)元素。Java8將該方法改為默認(rèn)方法實(shí)現(xiàn)涮母，對(duì)于沒有實(shí)現(xiàn)remove方法的集合類，如果使用remove方法會(huì)拋出UnsupportedOperationException躁愿。
     */
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    /**
     * 對(duì)集合中沒有處理的元素叛本，執(zhí)行action指定動(dòng)作。
     * JDK8新增方法彤钟，并且提供接口方法默認(rèn)實(shí)現(xiàn)
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

JDK1.5新增的forEach循環(huán)就是使用Iterator實(shí)現(xiàn)的来候。但是使用forEach循環(huán)是不能修改集合內(nèi)容，想要在遍歷過(guò)程中修改集合內(nèi)容逸雹，還需要使用Iterator迭代器营搅。

Iterable

我們會(huì)發(fā)現(xiàn)我們無(wú)論自己寫代碼還是集合類型都沒有直接實(shí)現(xiàn)Iterator接口，而是實(shí)現(xiàn)了Iterable接口梆砸。我們可以看下面Iterable接口的源碼转质，它最主要的一個(gè)方法是返回一個(gè)Iterator方法。
之所以不直接實(shí)現(xiàn)Iterator接口帖世，而是通過(guò)Iterable返回一個(gè)迭代器休蟹。主要原因就是Iterator接口的核心方法hasNext和next都依賴當(dāng)前位置迭代位置，如果將集合框架直接實(shí)現(xiàn)Iterator接口日矫，那么就需要一個(gè)指針來(lái)標(biāo)識(shí)這個(gè)迭代位置赂弓，但是如果這樣就會(huì)導(dǎo)致再對(duì)同一個(gè)集合進(jìn)行遍歷時(shí)，指針出現(xiàn)混亂哪轿。所以我們通過(guò)實(shí)現(xiàn)Iterable接口為需要遍歷集合的方法都提供一個(gè)新的迭代器盈魁，它們之間互不影響。

public interface Iterable<T> {
    /**
     * 返回該集合的一個(gè)迭代器
     */
    Iterator<T> iterator();

    /**
     * 對(duì)Iterable所有元素執(zhí)行特定操作窃诉，直到所有元素處理完成或操作元素出現(xiàn)異常杨耙。
     * 接口方法默認(rèn)實(shí)現(xiàn)赤套。
     */
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    /**
     * 返回Spliteratordei迭代器。
     * JDK8提供
     */
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

如果想要使用for-each循環(huán)按脚，就需要實(shí)現(xiàn)Iterable接口

Spliterator

我們會(huì)看到上面Iterable還返回一個(gè)了Spliterator接口于毙，那么這個(gè)Spliterator是什么呢？
Spliterator是JDK1.8新增的一種迭代器辅搬，它主要是為了并行迭代遍歷數(shù)據(jù)源中元素而設(shè)計(jì)的(因?yàn)楝F(xiàn)在是多核時(shí)代唯沮，順序遍歷已經(jīng)不能滿足性能上的需求了)。
Spliterator接口的設(shè)計(jì)思想就是利用遞歸將任務(wù)分解成小任務(wù)堪遂，然后并行處理介蛉，最終再將結(jié)果進(jìn)行合并。JDK8中函數(shù)式編程是Java主要發(fā)展的一個(gè)方向溶褪，所以Spliterator接口方法基本都是使用函數(shù)式編程的思想币旧。
Spliterator有幾個(gè)核心的方法：

除了這些方法输瓜，Spliterator還有一些關(guān)于特征的方法以及特定常量的定義，它們能夠幫助創(chuàng)建高效芬萍、健壯的代碼尤揣。

關(guān)于Spliterator的具體實(shí)現(xiàn)我們可以到ArrayList時(shí)候在查看。
下面是一個(gè)使用Spliterator的實(shí)例：

//這里并沒有體現(xiàn)Spliterator的強(qiáng)大柬祠，在并行處理的地方Spliterator的最大優(yōu)勢(shì)才能體現(xiàn)出來(lái)北戏。一般Spliterator和流API中使用
List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        Spliterator<Integer> sIterator=  list.spliterator();
        while (sIterator.tryAdvance(n -> System.out.println(n)));

JDK已經(jīng)所有集合提供了默認(rèn)的Spliterator實(shí)現(xiàn)，但是它并不是根據(jù)不同集合特征而實(shí)現(xiàn)的漫蛔，所以效率可能不是非常高最欠。如果想要高效使用，還需要根據(jù)自己的集合特征進(jìn)行實(shí)現(xiàn)惩猫。

借鑒：
Java8編程官方參考文檔
https://segmentfault.com/q/1010000007087438

ListIterator

ListIterator繼承自Iterator接口芝硬，它相對(duì)Iterator來(lái)說(shuō)有以下特點(diǎn)：

• 允許雙向遍歷列表。
• 允許在遍歷過(guò)程中修改列表元素轧房。
• 能夠獲取遍歷過(guò)程中元素的下標(biāo)位置拌阴。

ListIterator不存在當(dāng)前元素的概念，因?yàn)樗褂糜螛?biāo)來(lái)獲取元素奶镶，游標(biāo)總是在要獲取下一個(gè)元素的前面迟赃。這就是為什么它能夠雙向遍歷陪拘，并且能夠獲取元素下標(biāo)位置的原因。

image.png

可以看到上面除了next纤壁、hasNext左刽、remove這些Iterator接口，ListIterator還提供了向前遍歷方法hasPrevious酌媒、previous欠痴，獲取位置下標(biāo)方法nextIndex、修改和增加元素的set秒咨、add方法喇辽。

游標(biāo)默認(rèn)開始是-1，因?yàn)橛螛?biāo)總是在要訪問(wèn)元素的前面(向后遍歷的情況)雨席。

關(guān)于ListIterator的使用可以在查看List源碼時(shí)候來(lái)講解菩咨。

Collection集合框架

集合表示一組對(duì)象，每個(gè)對(duì)象在集合中稱為元素陡厘。集合可以分為有序抽米、無(wú)序集合，可重復(fù)糙置、不可重復(fù)等集合缨硝。Collection是集合層級(jí)結(jié)構(gòu)的根接口。正因?yàn)榧系姆N類多種多樣罢低，所以JDK沒有提供Collection接口的直接實(shí)現(xiàn)類，而是提供了更具體的接口比如有序可重復(fù)的List胖笛、有序不可重復(fù)的Set等等网持。Collection接口一般用于傳遞集合，并在需要最大的通用性時(shí)提供操作长踊。

Collection接口

Collection接口是集合類的根接口功舀，它的位置如圖所示：

image.png

Collection定義了集合所需要的基本方法，它集成Iterable接口身弊，所以能夠使用iterator方法返回迭代器辟汰，并且所有集合類都能夠使用for-each循環(huán)。

public interface Collection<E> extends Iterable<E> {}

下面是Collection提供的方法：

image.png

這些方法主要分為五類：查詢操作阱佛、修改操作帖汞、批處理操作、比較和散列凑术、流處理翩蘸。

查詢操作

• int size()：返回集合元素中的個(gè)數(shù)，如果超過(guò)Integer.MAX_VALUE則直接返回Integer.MAX_VALUE淮逊。
• boolean isEmpty()：如果集合元素為空催首，則返回true扶踊。
• boolean contains(Object o)：如果集合包含指定元素則返回true。一般判斷方法：o==null ? e==null : o.equals(e)
• Iterator<E> iterator()：返回迭代器
• default Spliterator<E> spliterator()：返回并行迭代器Spliterator(JDK8新增)郎任。
• Object[] toArray()：返回包含所有集合元素的數(shù)組秧耗，它是數(shù)據(jù)和集合之間的橋梁。
• <T> T[] toArray(T[] a)：同上舶治，只不過(guò)指定了數(shù)組具體數(shù)據(jù)類型分井。如果返回元素大于數(shù)組a，則會(huì)重新創(chuàng)建一個(gè)新數(shù)組存儲(chǔ)集合元素返回歼疮，如果小于等于則直接返回?cái)?shù)組a杂抽。

修改操作

• boolean add(E e)：將元素e添加到集合中，如果添加成功則返回true韩脏。如果元素已經(jīng)存在集合中缩麸，并且該集合不允許重復(fù)，則返回false赡矢。
• boolean remove(Object o)：刪除集合中指定元素杭朱。

批處理操作

批處理操作就是方法用于操作另一個(gè)集合。

• boolean containsAll(Collection<?> c)：如果集合包含集合c中的所有元素吹散，則返回true弧械，否則返回false。
• boolean addAll(Collection<? extends E> c)：將集合c中所有元素添加到集合中空民，如果調(diào)用的集合發(fā)生的改變刃唐，則返回true，否則返回false界轩。
• boolean removeAll(Collection<?> c)：從調(diào)用集合中刪除c中的所有元素画饥，如果調(diào)用集合發(fā)生改變，則返回true浊猾。
• default boolean removeIf(Predicate<? supper E> filter)：從調(diào)用集合中刪除滿足predicate過(guò)濾條件的元素(JDK8新增)抖甘。
• boolean retainAll(Collectio<?> c)：移除調(diào)用者集合中不包含在集合c中的元素，如果集合有變化葫慎，則返回true衔彻。
• clean()：移除集合中所有元素

比較和散列

• boolean equals(Object o)：如果調(diào)用集合與obj相等，則返回true偷办。
• int hashCode()：返回調(diào)用集合散列值艰额。

流處理

• default Stream<E> stream()：返回一個(gè)使用調(diào)用集合作為源的流，該流是順序流椒涯。
• default Stream<E> parallelStream()：同上悴晰，但是該流支持并行操作

默認(rèn)實(shí)現(xiàn)Collection接口的方法并沒有使用同步協(xié)議，所以當(dāng)需要方法同步處理時(shí)，需要覆蓋Collection提供的方法铡溪，自己實(shí)現(xiàn)同步協(xié)議漂辐。
JDK8新增的接口默認(rèn)實(shí)現(xiàn)方法語(yǔ)法極大的方便了接口的擴(kuò)展，這樣對(duì)向下兼容提供了很好的幫助棕硫。所以如果想要對(duì)已有接口進(jìn)行擴(kuò)展髓涯，為了向前兼容，就需要使用這種接口默認(rèn)實(shí)現(xiàn)方法哈扮。

List列表

List結(jié)合框架實(shí)現(xiàn)如下纬纪，除了這些還有AttributeList、RoleList滑肉、RoleUnresolvedList這些javax.management包下的實(shí)現(xiàn)包各。

image.png

List是一個(gè)元素有序、空重復(fù)靶庙、允許為空的集合序列(列表)问畅。List的數(shù)據(jù)結(jié)構(gòu)是一個(gè)線性表，它里面有順序表六荒、鏈表的實(shí)現(xiàn)類护姆。
List擴(kuò)展了Collection<E>接口，我們會(huì)發(fā)現(xiàn)Collection<E>中的接口方法List又重新定義了一遍掏击。我理解之所以這么做是因?yàn)樵贚ist中這些方法的定義比Collection<E>中更具體卵皂，比如add()方法在List說(shuō)明了通過(guò)add()將元素添加到列表某位，而Collection<E>中add()方法就是說(shuō)了將元素添加到集合砚亭。這樣做就是通過(guò)注釋將含義具體化灯变，在語(yǔ)法上List其實(shí)是可以不重寫的。

List中定義發(fā)生改變的方法

下面我將List中重寫Collection<E>方法定義發(fā)生改變的梳理了一下：

• boolean add(E e)：將元素添加到列表末尾捅膘，具體實(shí)現(xiàn)類可以對(duì)該方法進(jìn)行添加限制添祸，比如不允許添加null。
• boolean remove(Object o)：刪除列表中第一元素篓跛。
• boolean addAll(Collection<? extends E> c)：將集合c中所有元素添加到列表的末尾。
• boolean equals(Object o)：比較兩個(gè)列表是否相等坦刀，兩個(gè)列表定義相同愧沟，列表元素也相同返回true。
• int hashCode()：返回列表哈希值鲤遥，計(jì)算方式：

  int hashCode = 1;
     for (E e : list)
         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

List接口新增方法

下面是List接口根據(jù)列表的特性沐寺，新增的一些接口方法定義。

• boolean addAll(int index,Collection<? extends E> c)：將集合c中所有元素插入到列表的index索引位置盖奈，列表中index后面的元素全部向后移動(dòng)混坞。如果調(diào)用列表發(fā)生了改變，則返回true。
• default void replaceAll(UnaryOperator<E> operator)：將列表中所有元素通過(guò)operator函數(shù)處理究孕，來(lái)更新列表中所有元素啥酱。
• default void sort(Comparator<? supper E> c)：使用c比較器，將列表元素進(jìn)行排序厨诸。
• E get(int index)：返回列表指定索引位置元素
• E set(int index,E element)：替換指定索引位置元素镶殷，返回舊元素。
• void add(int index,E element)：在列表指定索引位置添加元素微酬。
• E remove(int index)：刪除指定索引位置元素绘趋。
• int indexOf(Object o)：返回指定元素在列表中第一次出現(xiàn)的位置。如果列表不包含該元素颗管，則返回-1陷遮。
• int lastIndexOf(Object o)：同上，不過(guò)返回最后一次出現(xiàn)的維值垦江。
• ListIterator<E> listiterator()：返回編列列表的listiterator帽馋。
• ListIterator<E> listiterator(int index)：返回指定起始索引位置的Listiterator。
• List<E> subList(int fromIndex,int toIndex)：返回該列表從索引位置fromIndex到toIndex元素的視圖疫粥。注意茬斧，這里并不是創(chuàng)建了一個(gè)新列表，二者是同一引用梗逮。一個(gè)很好的使用方式项秉，比如刪除列表指定范圍元素：list.subList(from, to).clear();。

ArrayList

ArrayList接口繼承抽象類AbstractList<E>慷彤，并且實(shí)現(xiàn)了List<E>娄蔼、RandomAccess、Cloneable和Java.io.Serializable接口底哗。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

再說(shuō)ArrayList之前我們先看下AbstractList抽象類把岁诉。

AbstractList

AbstractList抽象抽類繼承AbstractCollection<E>抽象類和List<E>接口。
它在集合框架中的位置如下圖：

image.png

AbstractCollection<E>抽象類是Cllection<E>接口骨架實(shí)現(xiàn)跋选，除了將iterator()和size()方法定義為抽象方法涕癣，其它方法基本都進(jìn)行了默認(rèn)實(shí)現(xiàn)。
AbstractCollection<E>實(shí)現(xiàn)分為兩種類型前标，一種是真正的通用坠韩，所有下面的集合類基本都會(huì)以相同的方式實(shí)現(xiàn)該方法。比如isEmpty()炼列、contains()只搁、remove()、toArray()等這些方法俭尖，

public abstract class AbstractCollection<E> implement Collection<E>{
    public boolean isEmpty() {
        //通過(guò)子類實(shí)現(xiàn)的size方法比較
        return size() == 0;
    }
    public boolean contains(Object o) {
        //調(diào)用子類實(shí)現(xiàn)的迭代器氢惋，通過(guò)迭代器遍歷集合
        Iterator<E> it = iterator();
        //通過(guò)null值的判斷就知道洞翩，Collection底層本身是支持存儲(chǔ)null的
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }
    public boolean remove(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext()) {
                if (it.next()==null) {
                    it.remove();
                    return true;
                }
            }
        } else {
            while (it.hasNext()) {
                //子類需要自己實(shí)現(xiàn)equal方法
                if (o.equals(it.next())) {
                    it.remove();
                    return true;
                }
            }
        }
        return false;
    }
    ....
}

我們可以看到AbstractCollection<E>所有遍歷操作都是用子類需要實(shí)現(xiàn)的迭代器iterator()來(lái)完成的，對(duì)于比較操作都是使用equals()方法焰望，所以子類都需要實(shí)現(xiàn)和重寫這兩個(gè)方法骚亿。接下來(lái)我們?cè)賮?lái)看看AbstractList<E>抽象類。

AbstractList<E>是List<E>接口的骨干實(shí)現(xiàn)抽象類柿估，它最大限度的為Java能夠“隨機(jī)訪問(wèn)”數(shù)據(jù)存儲(chǔ)(比如數(shù)組)提供了實(shí)現(xiàn)循未。

對(duì)于順序訪問(wèn)的數(shù)據(jù)存儲(chǔ)，需要使用AbstractList的子類AbstractSequentialList抽象類秫舌。

首先AbstractList實(shí)現(xiàn)了AbstractCollection中的iterator()方法的妖，但是沒有實(shí)現(xiàn)size()方法，并且又增加了一個(gè)get()方法足陨。所以AbstractList的子類必須實(shí)現(xiàn)size()和get()方法嫂粟。

abstract public E get(int index);

下面看看AbstractList具體實(shí)現(xiàn)的方法。

默認(rèn)AbstractList是不支持修改操作的墨缘，所以如果想要支持修改星虹，子類需要重新實(shí)現(xiàn)set、add镊讼、remove方法宽涌，否則拋出UnsupportedOperationException異常。

    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }

通過(guò)ListIterator來(lái)實(shí)現(xiàn)正反向索引數(shù)據(jù)方法蝶棋。ListIterator通過(guò)游標(biāo)的方式記錄遍歷位置卸亮，所以當(dāng)調(diào)用next()方法時(shí)游標(biāo)其實(shí)已經(jīng)移到元素后面了，所以當(dāng)我們找到元素后要返回游標(biāo)的前一個(gè)位置玩裙。

public int indexOf(Object o) {
        ListIterator<E> it = listIterator();
        if (o==null) {
            while (it.hasNext())
                //當(dāng)next()方法已經(jīng)找到匹配元素后兼贸，返回游標(biāo)的前一個(gè)位置
                if (it.next()==null)
                    return it.previousIndex();
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return it.previousIndex();
        }
        return -1;
    }

    public int lastIndexOf(Object o) {
        ListIterator<E> it = listIterator(size());
        if (o==null) {
            while (it.hasPrevious())
                //同理通過(guò)previous()方法匹配到指定元素后，返回游標(biāo)的后一個(gè)位置
                if (it.previous()==null)
                    return it.nextIndex();
        } else {
            while (it.hasPrevious())
                if (o.equals(it.previous()))
                    return it.nextIndex();
        }
        return -1;
    }

清除列表全部元素吃溅，AbstractList抽象出一個(gè)removeRange方法溶诞，能夠刪除列表中任意連續(xù)元素。

    public void clear() {
        removeRange(0, size());
    }
    protected void removeRange(int fromIndex, int toIndex) {
        //從刪除起始位置獲取ListIterator迭代器
        ListIterator<E> it = listIterator(fromIndex);
       //很細(xì)節(jié)n的使用
        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();
        }
    }

將集合元素添加到當(dāng)前列表决侈，使用子類實(shí)現(xiàn)的add方法螺垢。

public boolean addAll(int index, Collection<? extends E> c) {
        //檢測(cè)下標(biāo)是否越界
        rangeCheckForAdd(index);
        //只要有元素添加進(jìn)去就返回true
        boolean modified = false;
        for (E e : c) {
            add(index++, e);
            modified = true;
        }
        return modified;
    }
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size())
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

AbstractList不但實(shí)現(xiàn)了iterator()方法，還提供了listIterator()方法赖歌。

    public Iterator<E> iterator() {
        return new AbstractList.Itr();
    }
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }
    public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);
        return new AbstractList.ListItr(index);
    }

并且以內(nèi)部類實(shí)現(xiàn)了Iterator的Itr和ListIterator的ListItr枉圃。這兩個(gè)內(nèi)部類代碼太長(zhǎng)了，就不貼了說(shuō)下他們思想俏站。
Itr通過(guò)游標(biāo)cursor來(lái)表示下一個(gè)元素的位置讯蒲，同時(shí)它利用一個(gè)lastRet表示本次迭代的位置痊土，lastRet的作用就是為remove方法提供刪除最后一次迭代的元素肄扎。lastRet只要在remove用完一次都會(huì)將它置為-1。Itr在next()和remove()方法中都會(huì)調(diào)用下面這個(gè)方法，判斷操作數(shù)(modCount)是否在遍歷期間發(fā)生改變犯祠，如果有就直接拋出ConcurrentModificationException旭等，目的就是為了防止并發(fā)修改。

    final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

ListItr繼承了Itr類衡载，同樣使用游標(biāo)cursor來(lái)索引數(shù)據(jù)搔耕。只不過(guò)提供了previous()和hasPrevious()和獲取索引位置的接口。

AbstractList針對(duì)截取還提供了內(nèi)個(gè)實(shí)現(xiàn)類：SubList和RandomAccessSubList痰娱。SubList雖然是個(gè)獨(dú)立類弃榨，但實(shí)際操作的就是AbstractList。而RandomAccessSubList就是提供了標(biāo)識(shí)能夠支持隨機(jī)隨機(jī)訪問(wèn)的SubList梨睁。

      public List<E> subList(int fromIndex, int toIndex) {
        return (this instanceof RandomAccess ?
                new RandomAccessSubList<>(this, fromIndex, toIndex) :
                new SubList<>(this, fromIndex, toIndex));
    }

RandomAccess

ArrayList還實(shí)現(xiàn)了RandomAccess接口鲸睛，RandomAccess是一個(gè)空接口，用于標(biāo)識(shí)子類支持快速隨機(jī)訪問(wèn)坡贺。
比如對(duì)于支持隨機(jī)訪問(wèn)的集合官辈，使用隨機(jī)訪問(wèn)的速度是快于使用迭代器的。

//速度更快遍坟，所以List應(yīng)該實(shí)現(xiàn)它
for (int i=0, n=list.size(); i < n; i++)
         list.get(i);

for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();     

Clonable

Clonable接口也是一個(gè)標(biāo)識(shí)接口拳亿，表示實(shí)現(xiàn)類可以使用clone方法(clone()是java.lang.Object中定義的方法，所以所有類實(shí)際都可以重寫該方法)愿伴。如果沒有使用Clonable接口標(biāo)記類肺魁，直接調(diào)用clone()方法將會(huì)拋出CloneNotSupportedException異常。
需要注意的兩點(diǎn)是：

1. 拷貝對(duì)象返回的是一個(gè)新對(duì)象公般，而不是之前的引用(從堆中重新創(chuàng)建一個(gè)對(duì)象)万搔。
2. 使用clone()方法和new操作符返回的對(duì)象相比，clone()返回的對(duì)象已經(jīng)包含原對(duì)象的操作信息官帘，而不是對(duì)象的初始信息瞬雹。

Object中的clone()方法已經(jīng)有默認(rèn)實(shí)現(xiàn)了，但是這個(gè)實(shí)現(xiàn)的是一種淺拷貝刽虹，也就是并不會(huì)把對(duì)象所有屬性全部拷貝一份酗捌，而是有選擇的拷貝。比如對(duì)于引用類型涌哲，實(shí)際拷貝過(guò)去的是引用地址胖缤，這樣就會(huì)導(dǎo)致兩個(gè)對(duì)象操作同一個(gè)引用宦焦。
所以如果想要使用深拷貝醋闭，需要重新實(shí)現(xiàn)clone方法，不僅利用淺拷貝將基礎(chǔ)類型進(jìn)行拷貝侣滩，而且還還需將引用類型進(jìn)行深拷貝初烘。
還有一種實(shí)現(xiàn)深拷貝的方法就是利用序列化與反序列化涡真，將對(duì)象序列化成字節(jié)分俯，然后反序列化成對(duì)象返回。

Serializable

Serializable也是一個(gè)標(biāo)記接口哆料，用于表示實(shí)現(xiàn)類可以被序列化缸剪。序列化與反序列化其實(shí)就是將Java中對(duì)象轉(zhuǎn)換成字節(jié)，或從字節(jié)反序列化成對(duì)象东亦。之所以需要轉(zhuǎn)換成字節(jié)杏节，是因?yàn)槲覀儫o(wú)論是將對(duì)象持久化還是將對(duì)象進(jìn)行網(wǎng)絡(luò)傳輸，操作的只能是字節(jié)典阵。
Java提供了對(duì)象的序列化與反序列化方法奋渔，就是使用ObjectInputStream和ObjectOutputStream。

序列化一般常用于：

1. 將內(nèi)存中的對(duì)象持久化到磁盤上壮啊。
2. 使用套接字將對(duì)象在網(wǎng)絡(luò)上傳輸卒稳。
3. 想通過(guò)RMI在網(wǎng)絡(luò)中傳輸對(duì)象。

使用序列化需要有以下注意點(diǎn)：

• 當(dāng)一個(gè)父類實(shí)現(xiàn)序列化他巨，子類自動(dòng)實(shí)現(xiàn)序列化充坑，無(wú)需重新實(shí)現(xiàn)Serializable接口。
• 序列化時(shí)只保存對(duì)象的狀態(tài)染突，不保存對(duì)象的方法捻爷。
• 序列化對(duì)象會(huì)將引用類型變量也進(jìn)行序列化，并且這個(gè)過(guò)程是遞歸的份企。

實(shí)際中我們可能不需要序列化對(duì)象中所有的數(shù)據(jù)(比如一些敏感數(shù)據(jù)也榄，或一些不重要數(shù)據(jù))，這時(shí)候就可以使用transient關(guān)鍵字司志。使用transient關(guān)鍵字修飾的變量甜紫，不會(huì)被序列化。

除了使用Serializable接口進(jìn)行序列化骂远，還可以使用Externalizable接口進(jìn)行序列化囚霸。使用Externalizable接口進(jìn)行序列化就需要自己實(shí)現(xiàn)writeExternal和readExternal方法。

    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(age);
    }
    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        age = in.readInt();
    }

使用Externalizable接口還需要提供一個(gè)無(wú)參構(gòu)造方法激才，因?yàn)樵谧x取該對(duì)象時(shí)拓型，會(huì)調(diào)用無(wú)參改造方法創(chuàng)建對(duì)象。
對(duì)于單例對(duì)象瘸恼，為了保證單例對(duì)象的特性劣挫，我們可以提供一個(gè)readResolve()方法，該方法直接返回單例對(duì)象东帅。

private Object readResolve() throws ObjectStreamException{
    return getInstance();
} 

ArrayList實(shí)現(xiàn)

說(shuō)完了上面這些压固，我們來(lái)看看ArrayList具體是怎么實(shí)現(xiàn)的。
ArrayList有以下特點(diǎn)：

• 容量不固定靠闭，可以動(dòng)態(tài)擴(kuò)容帐我。
• 元素可重復(fù)并且有序刘莹。
• 允許存儲(chǔ)null值矿咕。
• 對(duì)于隨機(jī)訪問(wèn)效率非常高狼钮，時(shí)間復(fù)雜度為O(1)碳柱。
• 對(duì)于添加和刪除元素，需要移動(dòng)數(shù)據(jù)，平均時(shí)間復(fù)雜度為O(n)。
• 相較LinkedList占用空間更小钮糖，不需要存儲(chǔ)額外數(shù)據(jù)酪我。

ArrayList在集合框架的位置：

image.png

ArrayList使用Object數(shù)組作為底層存儲(chǔ)消痛。

    //列表默認(rèn)大小
    private static final int DEFAULT_CAPACITY = 10;
    //ArrayList為空時(shí)存儲(chǔ)數(shù)組對(duì)應(yīng)的數(shù)組，不知道用途
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //ArrayList存儲(chǔ)數(shù)據(jù)的數(shù)組
    transient Object[] elementData; 
    //ArrayList的長(zhǎng)度
    private int size;
    //數(shù)組最大長(zhǎng)度都哭，因?yàn)橛行㎎VM會(huì)在數(shù)組前添加一個(gè)標(biāo)簽肄满，所以減去8。最大值為2^31-1质涛，大概有2147483647
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList提供了三個(gè)構(gòu)造方法稠歉。

//指定列表容量大小
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }
    //沒有指定容量大小，測(cè)試用默認(rèn)大小(默認(rèn)大小為10)
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //構(gòu)造包含指定集合的列表
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray有可能返回不是Object[]數(shù)組
            if (elementData.getClass() != Object[].class)
            //Arrays.copyOf可以用來(lái)創(chuàng)建一個(gè)新數(shù)組汇陆。
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

下面是一些查詢相關(guān)的實(shí)現(xiàn)：

 //返回指定長(zhǎng)度
    public int size() {
        return size;
    }
    //通過(guò)長(zhǎng)度來(lái)判斷列表是否為空
    public boolean isEmpty() {
        return size == 0;
    }
    //判斷是否包含指定元素怒炸，通過(guò)indexOf正向搜索判斷。如果不存在則-1 < 0
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    //正向索引只要包括指定元素就返回其索引位置毡代，否則返回-1
    public int indexOf(Object o) {
        if (o == null) {
            //通過(guò)隨機(jī)訪問(wèn)來(lái)遍歷阅羹，效率要比iterator高
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    //同上勺疼，只不過(guò)從后向前搜索
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

將ArrayList轉(zhuǎn)換成數(shù)組。

    public Object[] toArray() {
        //使用Arrays.copyOf創(chuàng)建一個(gè)包含指定數(shù)組元素的新數(shù)組捏鱼，之所以不直接返回执庐，是因?yàn)橛锌赡軘?shù)組還有空余空間
        return Arrays.copyOf(elementData, size);
    }
    public <T> T[] toArray(T[] a) {
        //如果給定數(shù)組小于列表長(zhǎng)度，則返回一個(gè)新數(shù)組
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        //使用System.arraycopy將一個(gè)數(shù)組元素copy到另一個(gè)數(shù)組中
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

下面是一些獲取导梆、修改轨淌、增加的常規(guī)操作。需要注意在調(diào)用ensureCapacityInternal()擴(kuò)容方法時(shí)看尼，modCount進(jìn)行了自加1操作递鹉。modCount的作用就是fail-fast，防止迭代過(guò)程中其它線程修改列表藏斩。

//通過(guò)elementData方法強(qiáng)制數(shù)據(jù)類型轉(zhuǎn)換躏结，只需要添加一個(gè)unchecked注解
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
    public E get(int index) {
        //檢測(cè)給定的下標(biāo)是否越界
        rangeCheck(index);
        return elementData(index);
    }
    //修改元素沒有增加modCount。狰域。媳拴。
    public E set(int index, E element) {
        rangeCheck(index);
        //修改完元素后，返回修改前的值
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    public boolean add(E e) {
        //添加元素前判斷是否需要擴(kuò)容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        //添加元素判斷是否需要?jiǎng)討B(tài)擴(kuò)容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }
    public E remove(int index) {
        rangeCheck(index);
        //增加操作記錄數(shù)兆览，用于fail-fast判斷禀挫，防止迭代過(guò)程中并發(fā)修改
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            //通過(guò)System.arrayCopy將要?jiǎng)h除元素位置后面的所有元素向前移動(dòng)一位
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        //將最后一位置為null
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
    }
    public boolean remove(Object o) {
        if (o == null) {
            //移除第一次出現(xiàn)的目標(biāo)元素
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    //用于刪除指定位置元素
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }
    public void clear() {
        modCount++;

        //并沒有直接將數(shù)組置為null，而是逐個(gè)元素置為null拓颓。方便之后使用
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

下面看一下ArrayList如何實(shí)現(xiàn)的動(dòng)態(tài)擴(kuò)容语婴。

1. 每當(dāng)添加新元素時(shí)，首先判斷剩余容量是否滿足新添加的元素驶睦。如果不足砰左，則進(jìn)行擴(kuò)容。
2. 首先嘗試分配原容量1.5倍场航，判斷是否滿足需求缠导。如果不滿足需求，則擴(kuò)容至所需的最少容量溉痢。這個(gè)最小容量就是原大小加上所要添加的元素個(gè)數(shù)僻造。
3. 如果擴(kuò)容后的大小超過(guò)了Integer.MAX_VALUE則直接OOM。
4. 最大能夠分配的容量大小為Integer.MAX_VALUE個(gè)元素孩饼。

//傳入最小需要的容量大小髓削，如果add()調(diào)用則minCapacity為size+1，如果addAll()則minCapacity為需要添加的集合大小加上原始長(zhǎng)度
    //注意minCapacity為原始長(zhǎng)度加上要擴(kuò)容的大小
    private void ensureCapacityInternal(int minCapacity) {
        //如果當(dāng)前數(shù)組為空镀娶，則最小擴(kuò)容至minCapacity的最大值立膛。也就是說(shuō)數(shù)組最小長(zhǎng)度一定大于默認(rèn)容量10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        //每次調(diào)用該方法，說(shuō)明肯定修改了列表，將修改記錄器自加1
        modCount++;

        // 判斷剩余容量不夠宝泵，需要進(jìn)行擴(kuò)容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //擴(kuò)容到原來(lái)容量的1.5好啰，增加當(dāng)前數(shù)組長(zhǎng)度一半
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果1.5倍容量不足，則使用傳遞過(guò)來(lái)的最小所需容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新容量超過(guò)了最大值儿奶，則盡量分配所能分配的大小框往，最大值也就是Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 創(chuàng)建一個(gè)更大的數(shù)組
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        //如果所需容量都超過(guò)了MAX_INTEGER(超過(guò)MAX_INTEGER后，為負(fù)數(shù)了)直接拋出OOM
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

我們?cè)賮?lái)看下ArrayList的clone方法闯捎，它實(shí)際是一個(gè)淺拷貝椰弊，列表元素如果為引用類型，則只是將引用拷貝過(guò)去隙券。

    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

實(shí)現(xiàn)forEach方法，將每個(gè)元素作用action闹司，遍歷過(guò)程中如果其它線程修改了列表娱仔，則直接fail-fast。

    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

最后我們?cè)賮?lái)看下ArrayList如何完成的排序游桩。傳入c為比較器牲迫，如果為null，則默認(rèn)采用自然排序比較器借卧。

    @Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

ArrayList還重新實(shí)現(xiàn)了ListItr和Itr盹憎，實(shí)現(xiàn)原理和AbstractList差不多，只是添加了一個(gè)forEachRemaining方法铐刘。
Arraylist還實(shí)現(xiàn)了SplIterator陪每，并行迭代器。

LinkedList

LinkedList是列表的雙向鏈表實(shí)現(xiàn)镰吵，LinkedList是雙向隊(duì)列Deque的一種實(shí)現(xiàn)檩禾，但是它是為一個(gè)允許存儲(chǔ)null元素的隊(duì)列。LinkedList不是線程安全的疤祭，如果我們向操作線程安全的LinkedList可以在創(chuàng)建LinkedList時(shí)添加同步處理：

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList是順序訪問(wèn)的列表盼产，它不是繼承AbstractList抽象類，而是繼承AbstractSequenceList勺馆。AbstractSequenceList是List的簡(jiǎn)化版本戏售，它只支持按順序訪問(wèn)。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

AbstractSequenceList抽象類定義草穆，

image.png

它對(duì)外提供了隨機(jī)獲取的接口灌灾，但是內(nèi)部還是通過(guò)迭代器順序訪問(wèn)所需元素。

    public E get(int index) {
        try {
            //利用子類實(shí)現(xiàn)的listIterator迭代器訪問(wèn)指定位置元素
            return listIterator(index).next();
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
    public E set(int index, E element) {
        try {
            //利用子類實(shí)現(xiàn)的listIterator迭代器訪問(wèn)指定位置元素
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);
            return oldVal;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

LinkedList雙向鏈表節(jié)點(diǎn)定義：

    private static class Node<E> {
        E item;
        Node<E> next;//指向前一個(gè)元素的指針
        Node<E> prev;//指向后一個(gè)元素的指針

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

因?yàn)樗请p向隊(duì)列Deque的實(shí)現(xiàn)類悲柱，所以LinkedList也支持雙向操作紧卒。LinkedList通過(guò)指向頭尾節(jié)點(diǎn)的指針來(lái)完成相應(yīng)操作。

transient Node<E> first;
transient Node<E> last;

下面是鏈表的核心實(shí)現(xiàn)诗祸，列表其它方法都是調(diào)用的這些方法操作鏈表跑芳。

//在鏈表頭部插入元素
    private void linkFirst(E e) {
        final LinkedList.Node<E> f = first;
        //創(chuàng)建新節(jié)點(diǎn)轴总，將原頭節(jié)點(diǎn)作為新節(jié)點(diǎn)的next
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f);
        //插入節(jié)點(diǎn)作為first節(jié)點(diǎn)
        first = newNode;
        //最后要修改原頭節(jié)點(diǎn)的prev
        //如果fist節(jié)點(diǎn)之前為空，說(shuō)明之前是一個(gè)空鏈表博个，要將last節(jié)點(diǎn)指向新節(jié)點(diǎn)
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    //在鏈表尾部添加元素
    void linkLast(E e) {
        final LinkedList.Node<E> l = last;
        //將原尾節(jié)點(diǎn)作為新節(jié)點(diǎn)的prev節(jié)點(diǎn)
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
        //下面是修改原尾節(jié)點(diǎn)的next
        last = newNode;
        //如果原尾節(jié)點(diǎn)為null怀樟，說(shuō)明之前是一個(gè)空列表，需要將頭部元素也指向當(dāng)前節(jié)點(diǎn)盆佣。
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    //在指定節(jié)點(diǎn)前添加元素
    void linkBefore(E e, LinkedList.Node<E> succ) {
        //指定節(jié)點(diǎn)作為新節(jié)點(diǎn)的前節(jié)點(diǎn)往堡，指定節(jié)點(diǎn)的后節(jié)點(diǎn)最為新節(jié)點(diǎn)的后節(jié)點(diǎn)
        final LinkedList.Node<E> pred = succ.prev;
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    //刪除頭節(jié)點(diǎn)
    private E unlinkFirst(LinkedList.Node<E> f) {
        // 取出頭節(jié)點(diǎn)元素，作為返回值
        final E element = f.item;
        final LinkedList.Node<E> next = f.next;
        //釋放頭結(jié)點(diǎn)空間
        f.item = null;
        f.next = null; // help GC
        //將頭節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)
        first = next;
        //如果下一個(gè)節(jié)點(diǎn)為空共耍，說(shuō)明刪除節(jié)點(diǎn)后就是空鏈表了虑灰，需要將尾節(jié)點(diǎn)置為null
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
    //刪除尾節(jié)點(diǎn)
    private E unlinkLast(LinkedList.Node<E> l) {
        //取出尾節(jié)點(diǎn)值，作為返回值
        final E element = l.item;
        final LinkedList.Node<E> prev = l.prev;
        //釋放尾節(jié)點(diǎn)空間
        l.item = null;
        l.prev = null; // help GC
        //將尾節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)
        last = prev;
        //如果前一個(gè)節(jié)點(diǎn)為null痹兜，說(shuō)明此列表當(dāng)前為空列表
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    //刪除指定節(jié)點(diǎn)
    E unlink(LinkedList.Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final LinkedList.Node<E> next = x.next;
        final LinkedList.Node<E> prev = x.prev;
        //如果刪除節(jié)點(diǎn)的前節(jié)點(diǎn)為null穆咐，則說(shuō)明刪除的是頭節(jié)點(diǎn)，需要將fist指向刪除節(jié)點(diǎn)的后節(jié)點(diǎn)
        if (prev == null) {
            first = next;
        } else {
            //否則將刪除節(jié)點(diǎn)的前節(jié)點(diǎn)的尾指針字旭，指向刪除節(jié)點(diǎn)的后節(jié)點(diǎn)
            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;
    }

CopyOnWriteArrayList

線程安全的ArrayList对湃，它的所有操作都是通過(guò)創(chuàng)建底層數(shù)組的新副本來(lái)實(shí)現(xiàn)的。
CopyOnWriteArrayList是直接實(shí)現(xiàn)List接口來(lái)實(shí)現(xiàn)的：

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

CopyOnWriteArrayList對(duì)于修改和新增元素通過(guò)ReentrantLock鎖來(lái)防止多線程并發(fā)操作遗淳，并且所有操作都是通過(guò)創(chuàng)建一個(gè)新數(shù)組來(lái)完成的拍柒。

    public boolean add(E e) {
        //同步鎖
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            //使用新數(shù)組添加元素
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            //將新數(shù)組賦值為CopyOnWriteArrayList的數(shù)組
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

Vector

Vector和ArrayList一樣實(shí)現(xiàn)了可動(dòng)態(tài)擴(kuò)容的動(dòng)態(tài)數(shù)組，Vector相比ArrayList的區(qū)別就是它是線程安全的屈暗。如果不需要線程安全特性拆讯，可以使用ArrayList來(lái)代替。
Vector定義和ArrayList完全一樣：

 public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector與ArrayList不同的是提供了一種構(gòu)造方法能夠制定每次動(dòng)態(tài)擴(kuò)容的增長(zhǎng)容量养叛。

public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        //制定每次增長(zhǎng)的容量
        this.capacityIncrement = capacityIncrement;
    }

方法實(shí)現(xiàn)方式和ArrayList基本相同往果，只不過(guò)每個(gè)方法都添加了synchronize標(biāo)識(shí)。

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

下面是Vector的動(dòng)態(tài)擴(kuò)容機(jī)制一铅，實(shí)現(xiàn)原理和ArrayList一樣陕贮，區(qū)別就是每次擴(kuò)容的大小。

   private void ensureCapacityHelper(int minCapacity) {
        //判斷是否需要?jiǎng)討B(tài)擴(kuò)容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //如果沒有指定每次擴(kuò)容大小潘飘，則默認(rèn)為之前的2倍
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                capacityIncrement : oldCapacity);
        //如果擴(kuò)容之后的大小還是不滿足需求肮之，則使用最少需要的容量作為擴(kuò)容后大小
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //超過(guò)容量最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //最多分配Integer.MAX_VALUE
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

Vector中的許多方法定義感覺名稱和淘汰Enumeratio如果沒有同步需求最好使用ArrayList，否則效率太低卜录。

Stack

Stack是數(shù)據(jù)結(jié)構(gòu)的堆棧實(shí)現(xiàn)戈擒，它擴(kuò)展了Vector類，提供了棧的入棧艰毒、出棧筐高、查看元素、是否為空和搜索元素這幾個(gè)方法。

image.png

由于它基于Vector實(shí)現(xiàn)柑土，所以Stack也是線程安全的蜀肘。

public E push(E item) {
        //入棧，并返回元素
        addElement(item);
        return item;
    }
    public synchronized E pop() {
        E obj;
        int len = size();
        //返回并刪除棧頂元素
        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    public synchronized E peek() {
        //獲取棧頂元素
        int len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    public boolean empty() {
        return size() == 0;
    }
    public synchronized int search(Object o) {
        //從后向前搜索
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

由于Deque雙邊隊(duì)列的特性稽屏，其實(shí)我們可以使用它作為棧使用扮宠，這也是官方推薦的。比如使用LinkedList作為棧使用狐榔，是非常方便的坛增。

Queue/Deque

Java提供的隊(duì)列：

image.png

Queue

隊(duì)列是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，它具有先進(jìn)先出的特點(diǎn)薄腻。元素從尾部添加收捣，從頭部移出。
隊(duì)列有兩種：?jiǎn)侮?duì)列和循環(huán)隊(duì)列庵楷。單隊(duì)里就是最普通的隊(duì)列罢艾，單隊(duì)列對(duì)于空間利用率非常低，因?yàn)殛?duì)頭移出元素后就不能使用了嫁乘，而循環(huán)隊(duì)列是對(duì)他的一種改進(jìn)昆婿。
隊(duì)列一般用于緩存球碉、并發(fā)訪問(wèn)等場(chǎng)景蜓斧。

Java集合的Queue接口繼承自Collection接口，Deque睁冬、LinkedList挎春、PriorityQueue、BlockQueue等都實(shí)現(xiàn)了Queue接口豆拨。
Queue除了提供Collection里面的方法直奋，它又根據(jù)隊(duì)列的特性提供了一些方法。

image.png

Queue對(duì)于添加施禾、刪除脚线、獲取都分別提供了兩個(gè)方法，其中一種操作失敗后直接拋出異常弥搞，另一種是返回特殊值邮绿。

image.png

Queue建議不要添加null元素，如果添加null元素攀例，則拋出NullPointException船逮。這樣做的目的就是為了防止獲取的元素為null時(shí)不知道是對(duì)還是錯(cuò)。Queue下面的實(shí)現(xiàn)類基本都復(fù)合了該要求粤铭，但是LinkedList沒有對(duì)這一要求實(shí)現(xiàn)挖胃。
Insert操作，

Deque

Deque是Double ended queue的縮寫，即雙端隊(duì)列酱鸭。Dequeu支持從兩端添加和刪除元素吗垮。Deque繼承了Queue接口，并且提供的添加凛辣、刪除抱既、訪問(wèn)也都是兩套方法，一種操作失敗直接拋出異常扁誓，一種是返回指定值防泵。

image.png

Deque除了提供Queue中的指定方法外，還分別提供了操作隊(duì)前元素和隊(duì)尾操作的方法蝗敢。

image.png

比如void addFirst(E e)在隊(duì)前添加元素如果失敗則直接拋出異常捷泞，boolean offerFirst(E e)隊(duì)前添加元素，如果失敗則返回false寿谴。同理E removeFirst()和E pollFirst()是一樣的道理锁右。

Deque還提供了堆棧方法，堆棧方法如果操作失敗讶泰，直接拋出異常咏瑟。

//返回隊(duì)頭元素，并且刪除它痪署。如果隊(duì)列為空码泞，則直接拋出NoSuchElementException異常
E poll();
//在隊(duì)頭添加指定元素，如果隊(duì)列已滿狼犯，則直接拋出IllegalStateException異常
void push(E e);

堆棧方法和poll和removeFirst的作用是一樣的余寥，push和addFirst的作用是一樣的。

Deque還提供了兩個(gè)刪除元素的方法悯森，一個(gè)是從隊(duì)頭開始查找指定元素宋舷，找到后將其刪除。另一個(gè)則是相反瓢姻，從隊(duì)尾開始查找祝蝠。

boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);

Deque在最后還定義了一些集合方法：

//刪除雙端隊(duì)列第一個(gè)出現(xiàn)o的元素
boolean remove(Object o)
//判斷隊(duì)列是否存在指定元素
boolean contains(Object o)
//返回隊(duì)列長(zhǎng)度
int size()
//返回隊(duì)列的迭代器
Iterator<E> iterator()
//相反方向的迭代器
Iterator<E> descendingIterator()

Deque很有趣的提供了一個(gè)從隊(duì)尾向前遍歷的迭代器方法。

Dequeu的一般實(shí)現(xiàn)：

• LinkedDeque：大小可變的鏈表雙端隊(duì)列幻碱，允許存儲(chǔ)null绎狭。
• ArrayDeque：大小可變的數(shù)組雙端隊(duì)列，不允許存儲(chǔ)null
• LinkedBlockingDeque：并發(fā)場(chǎng)景收班，如果隊(duì)列為空坟岔，獲取操作將被阻塞，知道有元素摔桦。

ArrayBlockingQueue/

ArrayBlockingQueue是一個(gè)有界的阻塞隊(duì)列社付，

AbstractQueue

AbstractQueue是Queue接口的骨干實(shí)現(xiàn)承疲，它實(shí)現(xiàn)了AbstractCollection抽象類，實(shí)現(xiàn)了Queue接口鸥咖。它定義了添加燕鸽、刪除、獲取拋出異常的實(shí)現(xiàn)啼辣。

    public boolean add(E e) {
        //如果添加失敗啊研，直接拋出異常
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }
    public E remove() {
        E x = poll();
        //如果刪除失敗，直接拋出異常
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
    public E element() {
        E x = peek();
        //獲取元素為空鸥拧，直接拋出異常
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
    public void clear() {
        while (poll() != null)
            ;
    }

可以看到它們還是依賴子類去實(shí)現(xiàn)不拋出異常的方法党远。

ArrayBlockingQueue/LinkedBlockingQueue

對(duì)于Query因?yàn)锳rrayBlockingQueue和LinkedBlockingQueue也可以作為非阻塞是先用(比如offer和poll)方法，所以就沒有單獨(dú)針對(duì)非阻塞Queue進(jìn)行實(shí)現(xiàn)富弦。ArrayBlockingQueue和LinkedBlockingQueue本身也是線程安全的沟娱。

ArrayBlockingQueue

ArrayBlockQueue是一個(gè)阻塞有限隊(duì)列，每次使用時(shí)腕柜，需要指定容量大小济似，也可以指定操作線程順序是否按照FIFO形式。它使用Object[]數(shù)組存儲(chǔ)隊(duì)列元素盏缤，ArrayBlockQueue在使用每個(gè)方法時(shí)使用ReentrantLock鎖來(lái)保證訪問(wèn)砰蠢。
ArrayBlockQueue添加元素時(shí)，如果隊(duì)列滿了則會(huì)阻塞線程等待唉铜。提供了三種添加操作add台舱、offer、put打毛，add添加失敗直接拋出異常柿赊，它底層依賴的是offer俩功。如果隊(duì)列滿了幻枉，offer可以直接返回false，也可以設(shè)置一個(gè)阻塞等待時(shí)間诡蜓。而put方法會(huì)一直阻塞等待熬甫。

    public boolean offer(E e) {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //隊(duì)列滿了直接返回失敗
            if (count == items.length)
                return false;
            else {
                enqueue(e);
                return true;
            }
        } finally {
            lock.unlock();
        }
    }
    
    public boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
        checkNotNull(e);
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            //等待指定的超時(shí)時(shí)間
            while (count == items.length) {
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos);
            }
            enqueue(e);
            return true;
        } finally {
            lock.unlock();
        }
    }
    public void put(E e) throws InterruptedException {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            //無(wú)限阻塞等待
            while (count == items.length)
                notFull.await();
            enqueue(e);
        } finally {
            lock.unlock();
        }
    }

對(duì)應(yīng)的poll也可以直接返回或設(shè)置阻塞等待時(shí)間，take方法則會(huì)無(wú)限等待蔓罚。

添加元素：

• add(E e)=offer(E e)：直接返回
• offer(E e,long timeout, TimeUnit unit)：指定超時(shí)時(shí)間
• put(E e)：無(wú)限阻塞
  刪除元素：
• remove() = poll()：直接返回
• poll(long timeout, TimeUnit unit)：指定超時(shí)時(shí)間
• take()：無(wú)限阻塞
  訪問(wèn)元素：
• element()=peek()：直接返回

LinkedBlockingQueue

LinkedBlockingQueue實(shí)現(xiàn)原理和ArrayBlockQueue原理是一樣的椿肩，只不過(guò)通過(guò)單鏈表進(jìn)行實(shí)現(xiàn)的。通過(guò)一個(gè)隊(duì)頭指針刪除元素豺谈，通過(guò)對(duì)尾指針添加元素郑象。

    static class Node<E> {
        E item;
        Node<E> next;
        Node(E x) { item = x; }
    }
    //隊(duì)頭指針
    transient Node<E> head;
    //隊(duì)尾指針
    private transient Node<E> last;
   
   private void enqueue(Node<E> node) {
        //隊(duì)尾添加元素
        last = last.next = node;
    }
    private E dequeue() {
        //隊(duì)頭指針刪除元素
        //此時(shí)head為空節(jié)點(diǎn)(看下面構(gòu)造方法)
        Node<E> h = head;
        Node<E> first = h.next;
        
        h.next = h; // help GC
        head = first;
        //取出元素返回
        E x = first.item;
        //將隊(duì)頭元素置為null
        first.item = null;
        return x;
    }

注意它是通過(guò)一個(gè)空節(jié)點(diǎn)開始，隊(duì)頭指針和隊(duì)尾指針都開始都指向這個(gè)空節(jié)點(diǎn)茬末。

    public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        //空節(jié)點(diǎn)一直表示隊(duì)頭指針
        last = head = new Node<E>(null);
    }

ArrayBlockingQueue和LinkedBlockingQueue

1. ArrayBlockingQueue采用數(shù)組實(shí)現(xiàn)隊(duì)列厂榛，創(chuàng)建ArrayBlockingQueue必須要指定隊(duì)列大小盖矫。
2. LinkeBlockingQueue可以指定大小也可以不指定，如果不指定默認(rèn)大小時(shí)Integer.MAX_VALUE击奶。
3. 對(duì)于隊(duì)列初始大小不確定的阻塞隊(duì)列可以使用LinkedBlockingQueue辈双，這樣能夠節(jié)省空間。

ArrayDeque/LinkedBlockingDeque

對(duì)于雙端隊(duì)列柜砾，沒有阻塞實(shí)現(xiàn)的Deque實(shí)現(xiàn)湃望，

ArrayDeque

ArrayDeque是一個(gè)容量沒有限制的雙端數(shù)組隊(duì)列，但是ArrayDeque不是線程安全的痰驱，所以不支持多線程并發(fā)訪問(wèn)证芭。ArrayDeque大部分操作都是常量時(shí)間，
ArrayDeque提供了三個(gè)構(gòu)造方法：

    //如果不指定大小担映，則默認(rèn)分配16個(gè)元素大小
    public ArrayDeque() {
        elements = new Object[16];
    }
    //指定元素個(gè)數(shù)
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    //創(chuàng)建包含指定集合的雙端隊(duì)列
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

雙端隊(duì)列的優(yōu)勢(shì)在于能夠操作隊(duì)列兩端檩帐，也就是隊(duì)列兩端都能夠增加元素、刪除元素另萤。ArrayDeque通過(guò)兩個(gè)游標(biāo)head和tail來(lái)實(shí)現(xiàn)這種功能湃密。

LinkedBlockingDeque

鏈表阻塞雙端隊(duì)列，采用雙鏈表進(jìn)行實(shí)現(xiàn)四敞，即節(jié)點(diǎn)即包含指向前節(jié)點(diǎn)的指針泛源，也包含指向后節(jié)點(diǎn)的指針。
LinkedBlockingDeque是線程安全的忿危，同樣使用ReentrantLock鎖來(lái)保證每個(gè)方法的訪問(wèn)达箍。

LinkedBlockingDeque核心方法：

    public boolean offerFirst(E e) {
        if (e == null) throw new NullPointerException();
        //將要添加的元素封裝為鏈表節(jié)點(diǎn)
        LinkedBlockingDeque.Node<E> node = new LinkedBlockingDeque.Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return linkFirst(node);
        } finally {
            lock.unlock();
        }
    }
    private boolean linkFirst(LinkedBlockingDeque.Node<E> node) {
        //如果隊(duì)列長(zhǎng)度超過(guò)指定容量，則直接返回失敗
        if (count >= capacity)
            return false;
        //在鏈表頭部添加一個(gè)節(jié)點(diǎn)
        LinkedBlockingDeque.Node<E> f = first;
        node.next = f;
        first = node;
        if (last == null)
            last = node;
        else
            f.prev = node;
        ++count;
        notEmpty.signal();
        return true;
    }
    public boolean offerLast(E e) {
        if (e == null) throw new NullPointerException();
        LinkedBlockingDeque.Node<E> node = new LinkedBlockingDeque.Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return linkLast(node);
        } finally {
            lock.unlock();
        }
    }
    private boolean linkLast(LinkedBlockingDeque.Node<E> node) {
        
        if (count >= capacity)
            return false;
        //在鏈表尾部添加一個(gè)元素
        LinkedBlockingDeque.Node<E> l = last;
        node.prev = l;
        last = node;
        if (first == null)
            first = node;
        else
            l.next = node;
        ++count;
        notEmpty.signal();
        return true;
    }

真?zhèn)€LinkedBlockingDeque就是外層通過(guò)鎖保證并發(fā)訪問(wèn)铺厨，內(nèi)層就是操作鏈表的常規(guī)操作缎玫。

其它Queue

除了上面說(shuō)的，針對(duì)并發(fā)場(chǎng)景Java操作還提供了ConcurrentLinkedQueue和ConcurrentLinkedDeque解滓，對(duì)于并發(fā)場(chǎng)景我們可以使用上面這兩個(gè)無(wú)界鏈表隊(duì)列(雖然阻塞鏈表隊(duì)列也能夠允許多線程訪問(wèn)赃磨，但是效率很低，因?yàn)樗峭ㄟ^(guò)鎖來(lái)保證訪問(wèn)單一訪問(wèn)的)洼裤。
Java還提供了延遲阻塞隊(duì)列DelayQueue邻辉，隊(duì)頭代表過(guò)期元素，越靠近隊(duì)頭過(guò)期時(shí)間越遠(yuǎn)腮鞍。如果沒有過(guò)期元素值骇，則poll和remove直接返回為空。
下面試DelayQueue類定義移国，可以看到它里面的所有元素必須是Delayed的子類吱瘩。

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {

判斷元素是否過(guò)期的條件是，獲取該元素的getDelay(NANOSECONDS)如果小于等于0則說(shuō)明過(guò)期了迹缀。

同步隊(duì)列SynchronousQueue使碾，這個(gè)隊(duì)列是想要添加元素需要等待另一個(gè)線程執(zhí)行刪除操作才可以添加皱卓，同理相反。這個(gè)隊(duì)列沒有容量概念部逮，貌似就一個(gè)元素娜汁？也不能查看元素。目前不知道這個(gè)隊(duì)列的用途兄朋。