一.線性表

定義:零個(gè)或者多個(gè)元素的有限序列畅哑。
也就是說它得滿足以下幾個(gè)條件:
??①該序列的數(shù)據(jù)元素是有限的汹胃。
??②如果元素有多個(gè)，除了第一個(gè)和最后一個(gè)元素之外，每個(gè)元素只有一個(gè)前驅(qū)元素和一個(gè)后驅(qū)元素疹鳄。
??③第一元素沒有前驅(qū)元素，最后一個(gè)元素沒有后繼元素芦岂。
??④序列中的元素數(shù)據(jù)類型相同瘪弓。
則這樣的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。在復(fù)雜的線性表中禽最，一個(gè)數(shù)據(jù)元素(對象)可以由若干個(gè)數(shù)據(jù)項(xiàng)組成腺怯，組成一張數(shù)據(jù)表，類似于數(shù)據(jù)庫川无。

二.線性表的抽象數(shù)據(jù)類型

1.相關(guān)概念

抽象數(shù)據(jù)類型(abstract data type,ADT)是帶有一組操作的一組對象的集合呛占。這句話表明，線性表的抽閑數(shù)據(jù)類型主要包括兩個(gè)東西:數(shù)據(jù)集合和數(shù)據(jù)集合上的操作集合懦趋。
①數(shù)據(jù)集合:我們假設(shè)型如a0,a1,a2,...an-1的表晾虑，我們說這個(gè)表的大小是N，我們將大小為0的標(biāo)稱為空表仅叫。
②集合上的操作:一般常用的操作包括帜篇，查找，插入诫咱，刪除笙隙，判斷是否為空等等。

2.線性表的順序儲存結(jié)構(gòu)

線性表的順序儲存結(jié)構(gòu)遂跟，指的是用一段地址連續(xù)的儲存單元依次儲存線性表的數(shù)據(jù)元素逃沿。我們可以用一維數(shù)組實(shí)現(xiàn)順序儲存結(jié)構(gòu),并且上述對表的所有操作都可由數(shù)組實(shí)現(xiàn)。但是一維數(shù)組有一個(gè)很大缺點(diǎn)就是它得長度是固定的幻锁，也就是我們創(chuàng)建的額時(shí)候就聲明的長度，一旦我們要存儲的數(shù)據(jù)超出了這個(gè)長度边臼，我們就不得不手動的創(chuàng)建一個(gè)更長的新數(shù)組并將原來數(shù)組中的數(shù)據(jù)拷貝過去哄尔。

    int [] arr = new int[10]
    ......
    int [] newArr = new int[arr.length*2]
    for(int i=0;i<arr;i++){
        newArr[i] = arr[i];
    }
    arr = new Arr;

顯然這樣做非常的不明智，因此java中的ArrayList就應(yīng)用而生了柠并。ArrayList也就是傳說中的動態(tài)數(shù)組,也就是我們可以隨著我們數(shù)據(jù)的添加動態(tài)增長的數(shù)組岭接。
??實(shí)際上不管是簡單數(shù)組也好，動態(tài)數(shù)組也好臼予，在具體的操作中都存在這樣的問題:
??①如果我們在線性表的第i個(gè)位置插入/刪除一個(gè)元素鸣戴，那么我們需要怎么做呢？首先我們得從最后一個(gè)元素開始遍歷粘拾，到第i個(gè)位置窄锅，分辨將他們向后/前移動一個(gè)位置；在i位置處將要插入/刪除的元素進(jìn)行相應(yīng)的插入/刪除操作缰雇；整體的表長加/減1.
??②如果我們在線性表的第一個(gè)位置插入/刪除一個(gè)元素入偷，那么整個(gè)表的所有元素都得向后/向前移動一個(gè)單位追驴，那么此時(shí)操作的時(shí)間復(fù)雜度為O(N);如果我們在線性表的最末位置進(jìn)行上面兩種操作，那么對應(yīng)的時(shí)間復(fù)雜度為O(1)——綜合來看疏之，在線性表中插入或者刪除一個(gè)元素的平均時(shí)間復(fù)雜度為O(N/2)殿雪。
??總結(jié)一下,線性表的缺點(diǎn)——插入和刪除操作需要移動大量的元素；造成內(nèi)存空間的"碎片化"锋爪。這里有些童鞋就說了丙曙，ArrayList是一個(gè)線性表吧，我再ArrayList中添加/刪除一個(gè)元素直接調(diào)用add()/remove()方法就行了啊其骄，也是一步到位啊——這樣想就不對了河泳，如果我們看ArrayList的源碼就會發(fā)現(xiàn)，實(shí)際上他內(nèi)部也是通過數(shù)組來實(shí)現(xiàn)的年栓，remove()/add()操作也要通過上面說的一系列步驟才能完成拆挥，只不過做了封裝讓我們用起來爽。之后我們會通過源碼分析ArrayList等的內(nèi)部的實(shí)現(xiàn)方式某抓。
??當(dāng)然了纸兔，優(yōu)缺點(diǎn)就會有優(yōu)點(diǎn)——由于順序儲存結(jié)構(gòu)的元素?cái)?shù)目，元素相對位置都確定的否副，那么我們在存取確定位置的元素?cái)?shù)據(jù)的時(shí)候就比較方便汉矿，直接返回就行了。

3.線性表的鏈?zhǔn)絻Υ娼Y(jié)構(gòu)

上面我們說過备禀，順序結(jié)構(gòu)的最大不足是插入和刪除時(shí)需要移動大量元素洲拇；造成內(nèi)存空間的"碎片化。那么造成這中缺點(diǎn)的原因是什么呢曲尸？原因就在于這個(gè)線性表中相鄰兩元素之間的儲存位置也就有相鄰關(guān)系赋续，也就是說元素的位置是相對固定的，這樣就造成了"牽一發(fā)而動全身"的尷尬局面另患；同時(shí)纽乱，什么是"碎片化"呢？就是說上述順序結(jié)構(gòu)中昆箕，以數(shù)組為例來說鸦列，如果我們先在內(nèi)存中申請一個(gè)10位長度的數(shù)組，然后隔3個(gè)位置放一個(gè)5位長度的數(shù)組鹏倘，這個(gè)時(shí)候如果再來一個(gè)8位長度的數(shù)組薯嗤，那么顯然不能放在前兩個(gè)數(shù)組之間(他們之間只有三個(gè)空位)，那只能另找地方纤泵，中間的這三個(gè)位置就空下了骆姐，久而久之類似的事情多了就發(fā)生了"碎片化"的現(xiàn)象。

(1)簡單鏈表

為了解決上述兩個(gè)問題，我們前輩的科學(xué)家們就發(fā)明了偉大的"鏈?zhǔn)絻Υ娼Y(jié)構(gòu)"诲锹，也就是傳說中的鏈表(Linked List)繁仁。鏈表的結(jié)構(gòu)有兩大特點(diǎn)：
??①用一組任意的儲存單元儲存線性表的數(shù)據(jù)元素，這組儲存單元可以是連續(xù)的归园，也可以是不連續(xù)的黄虱。這就意味著，這些數(shù)據(jù)元素可以存在內(nèi)存中任意的未被占用的位置庸诱。
??②在上面的順序數(shù)據(jù)結(jié)構(gòu)中捻浦，每個(gè)數(shù)據(jù)元素只要儲存數(shù)據(jù)信息就可以了，但是在鏈表中桥爽，由于數(shù)據(jù)元素之間的位置不是固定的朱灿，因此為了保證數(shù)據(jù)元素之間能相互找到前后的位置，每個(gè)數(shù)據(jù)元素不僅需要保存自己的數(shù)據(jù)信息钠四，還需要保存指向下一個(gè)指針位置的信息盗扒。

簡單鏈表.png

如圖，我們畫出了簡單鏈表的示意圖缀去。鏈表由一系列結(jié)點(diǎn)組成侣灶，這些結(jié)點(diǎn)不必再內(nèi)存中相連，每個(gè)結(jié)點(diǎn)含有表元素(數(shù)據(jù)域)和到包含該元素后繼結(jié)點(diǎn)的鏈(link)(指針域)缕碎。
??對于一個(gè)線性表來說褥影，總得有頭有尾，鏈表也不例外咏雌。我們把第一個(gè)鏈表儲存的位置叫做"頭指針"凡怎，整個(gè)鏈表的存取就是從頭指針開始的。之后的每一個(gè)結(jié)點(diǎn)赊抖，其實(shí)就是上一個(gè)結(jié)點(diǎn)的指針域指向的位置统倒。最后一個(gè)結(jié)點(diǎn)由于沒有后繼結(jié)點(diǎn)，因此它的指針域?yàn)镹ULL熏迹。
??有時(shí)我們會在第一個(gè)指針前面加上一個(gè)頭結(jié)點(diǎn)檐薯，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不表示任何數(shù)值，也可以儲存鏈表長度等公共信息注暗，頭結(jié)點(diǎn)的指針域儲存指向第一個(gè)結(jié)點(diǎn)的位置的信息。
??需要注意的是墓猎，頭結(jié)點(diǎn)不是鏈表的必要要素捆昏，但是有了頭結(jié)點(diǎn)，在對第一個(gè)結(jié)點(diǎn)之前的位置添加/刪除元素時(shí)毙沾，就與其他元素的操作統(tǒng)一了骗卜。
(1.1)簡單鏈表的讀取
??在上面的線性表的順序儲存結(jié)構(gòu)中，我們知道它的一個(gè)優(yōu)點(diǎn)就是存取確定位置的元素比較的方便。但是對于鏈?zhǔn)絻Υ娼Y(jié)構(gòu)來說寇仓，假設(shè)我們要讀取i位置上的元素信息举户，但是由于我們事先并不知道i元素到底在哪里，所以我們只能從頭開始找遍烦，知道找到第i個(gè)元素為止俭嘁。由于這個(gè)算法的時(shí)間復(fù)雜度取決于i的位置，最壞的情況就是O(n),即元素在末尾服猪。
??由于單鏈表沒有定義表長供填，所以我們沒有辦法使用for循環(huán)來查找。因此這里查找算法的核心思想是"工作指針后移",也就是當(dāng)前的元素查完之后罢猪，移動到下一個(gè)位置近她，檢查下一個(gè)位置的元素，以此循環(huán)膳帕，直到找到第i個(gè)位置的元素粘捎。
??可以看到，這是鏈表結(jié)構(gòu)的一個(gè)缺點(diǎn)危彩，對于確定位置的元素查找平均時(shí)間復(fù)雜度為O(N/2)攒磨。
(1.2)簡單鏈表的插入與刪除
??當(dāng)然了，有缺點(diǎn)就有優(yōu)點(diǎn)恬砂，我們說過鏈表解決了順序表中"插入和刪除時(shí)需要移動大量元素"的缺點(diǎn)咧纠。也就是說，鏈表中插入刪除元素不需要移動其他的元素泻骤，那么鏈表是怎么做到的呢漆羔？

單鏈表的刪除與插入.png

我們用“.next”表示一個(gè)節(jié)點(diǎn)的后繼指針,X.next = Y表示將X的后繼指針指向Y節(jié)點(diǎn)。這里不得不說一下,由于Java中沒有指針的概念狱掂，而是引用(關(guān)于指針和引用的區(qū)別我們這里不做過多的說明演痒，他們本質(zhì)上都是指向儲存器中的一塊內(nèi)存地址)。在java語言描述的鏈表中,上面所說的“指針域”更準(zhǔn)確的說是“引用域”趋惨，也就是說鸟顺，這里的x.next實(shí)際上是X的下一個(gè)節(jié)點(diǎn)x->next元素的引用。說的更直白一點(diǎn)器虾，我們可以簡單的理解為x.next = x->next,就像我們經(jīng)常做的Button mbutton = new Button();一樣讯嫂，在實(shí)際操作中我們處理mbutton這個(gè)引用實(shí)際上就是在處理new Button()對象。
??我們先說刪除的做法兆沙，如上圖所示欧芽，我們假設(shè)一個(gè)x為鏈表節(jié)點(diǎn)，他的前一個(gè)結(jié)點(diǎn)為x->prev,后一個(gè)結(jié)點(diǎn)為x->next,我們用x.next表示他的后繼引用「鹌裕現(xiàn)在我們要?jiǎng)h除x結(jié)點(diǎn)千扔，需要怎么做呢憎妙？實(shí)際上很簡單，直接讓前一個(gè)結(jié)點(diǎn)元素的后繼引用指向x的下一個(gè)節(jié)點(diǎn)元素(向后跳過x)就可以了x->prev.next = x.next曲楚。
??同理插入一個(gè)節(jié)點(diǎn)呢厘唾？首先我們把Node的后繼節(jié)點(diǎn)Next的變成P的后繼節(jié)點(diǎn)，接著將Node的后繼引用指向P龙誊，用代碼表示就是:P.next = Node.next; Node.next = P;抚垃。解釋一下這兩句代碼，P.next = Node.next;實(shí)際上就是用Node.next的引用覆蓋了P.next的引用载迄，P.next的引用本來是一個(gè)空引用(剛開始還沒插入鏈表不指向任何節(jié)點(diǎn))讯柔，而Node.next本來是指向Next節(jié)點(diǎn)的，這一步操作完之后實(shí)際上P.next這個(gè)引用就指向了Next節(jié)點(diǎn)护昧；這個(gè)時(shí)候Node.next = P;這句代碼中魂迄，我們將Node.next這個(gè)引用重新賦值，也就是指向了P這個(gè)節(jié)點(diǎn)惋耙，這樣整個(gè)插入過程就完成了捣炬。
??為什么我們啰里啰嗦的為兩句代碼解釋了一堆內(nèi)容呢？就是要強(qiáng)調(diào)绽榛，上面兩個(gè)步驟順序是不能顛倒的湿酸！為什么呢？我們不妨顛倒順序看一下——我們首先進(jìn)行Node.next = P;這一步灭美，開始的時(shí)候推溃，P的引用域是空的(或者指向無關(guān)的地址)，此時(shí)如果我們進(jìn)行了這一步届腐，那么Node.next這個(gè)引用就指向了P節(jié)點(diǎn)铁坎，這個(gè)時(shí)候我們再進(jìn)行P.next = Node.next這一步就相當(dāng)于P.next = p,p.next引用域指向自己，這沒有任何意義犁苏。

(2)雙鏈表(LinkedList)

上面我們說了簡單鏈表的各種事項(xiàng)硬萍，但是在實(shí)際的運(yùn)用中，為了我們的鏈表更加靈活(比如既可以工作指針后移向后查找围详，也可以指針向前移動查詢)朴乖，我們運(yùn)用更多的是雙向鏈表，即每個(gè)節(jié)點(diǎn)持有前面節(jié)點(diǎn)和后面節(jié)點(diǎn)的引用助赞。java的雙向鏈表通過LinkedList類實(shí)現(xiàn)买羞，通過閱讀源碼我們在該類中可以看到關(guān)于結(jié)點(diǎn)的定義:

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

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

Java雙鏈表中的結(jié)點(diǎn)是通過一個(gè)靜態(tài)內(nèi)部類定義。一個(gè)結(jié)點(diǎn)包含自身元素(item)雹食，該節(jié)點(diǎn)對后一個(gè)節(jié)點(diǎn)的引用(next)哩都，該節(jié)點(diǎn)對前一個(gè)節(jié)點(diǎn)的引用(prev)。
(2.1)雙鏈表的刪除

雙鏈表的刪除.png

如圖婉徘，我們假設(shè)在一個(gè)雙向鏈表中有一個(gè)節(jié)點(diǎn)X漠嵌，他的前繼節(jié)點(diǎn)是prev，后繼節(jié)點(diǎn)是next.現(xiàn)在我們展示刪除節(jié)點(diǎn)X的源碼（sources/ansroid-24/java/util/LinkedList）:

    public boolean remove(Object o) {         //刪除分為兩種情況盖呼，一種是刪鏈表中的null元素儒鹿，一種是刪正常元素
        if (o == null) {    //刪除的具體操作沒什么區(qū)別，都是從第一個(gè)開始几晤，向后移動工作指針约炎，直到找到符合條件的
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    E unlink(Node<E> x) {   //上面是找元素，這個(gè)方法是真正刪除元素
        final E element = x.item;   //x.item表示當(dāng)前的x節(jié)點(diǎn)
        final Node<E> next = x.next;    //x.next表示x后繼引用蟹瘾，next同
        final Node<E> prev = x.prev;    //x.prev是x的前繼引用圾浅，prev同
        ......

        if (prev == null) { //如果prev為null，則表示x為第一個(gè)結(jié)點(diǎn)憾朴，此時(shí)刪除x的做法只需要將x的
            first = next;   //下一個(gè)節(jié)點(diǎn)設(shè)為第一個(gè)節(jié)點(diǎn)即可狸捕，first表示鏈表的第一節(jié)點(diǎn)。
        } else {
     ①      prev.next = next;   //否則的話众雷，x為普通節(jié)點(diǎn)灸拍。那么只要將x的前一個(gè)結(jié)點(diǎn)(prev)的后繼引用指向x的下一個(gè) 
            x.prev = null;      //節(jié)點(diǎn)就行了,也就是(向后)跳過了x節(jié)點(diǎn)。x的前繼引用刪除砾省，斷開與前面元素的聯(lián)系鸡岗。
        }

        if (next == null) {
            last = prev;    //如果x節(jié)點(diǎn)后繼無人，說明他是最后一個(gè)節(jié)點(diǎn)编兄。直接把前一個(gè)結(jié)點(diǎn)作為鏈表的最后一個(gè)節(jié)點(diǎn)就行
        } else {
     ②      next.prev = prev;   //否則x為普通節(jié)點(diǎn)轩性，將x的下一個(gè)節(jié)點(diǎn)的前繼引用指向x的前一個(gè)節(jié)點(diǎn)，也就是(向前)跳過x.   
            x.next = null;  //x的后繼引用刪除狠鸳，斷了x的與后面元素的聯(lián)系
        }

        x.item = null;  //刪除x自身
        size--;     //鏈表長度減1
        modCount++;
        return element;
    }

我們在在上面的源碼中標(biāo)出了刪除一個(gè)元素所需要的兩個(gè)步驟揣苏，即prev節(jié)點(diǎn)中原本指向X節(jié)點(diǎn)的后繼引用，現(xiàn)在向后越過X碰煌，直接指向next節(jié)點(diǎn)①(prev.next = next;)舒岸；next節(jié)點(diǎn)中原本指向X節(jié)點(diǎn)的前繼引用，現(xiàn)在向前越過X節(jié)點(diǎn)芦圾，直接指向prev節(jié)點(diǎn)蛾派。；然后就是將X的前繼引用和后繼引用都設(shè)置為null个少，斷了他與前后節(jié)點(diǎn)之間的聯(lián)系洪乍；最后將X節(jié)點(diǎn)本身置為null，方便內(nèi)存的釋放夜焦。
(2.2)雙鏈表的插入

雙鏈表的添加.png

這里我們選取較為容易的壳澳，在指定位置添加一個(gè)元素的add方法分析（sources/ansroid-24/java/util/LinkedList）:

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)  //size表示整個(gè)鏈表的長度，如果指定的索引等于鏈表的長度茫经，那么就把這個(gè)元素添加到鏈表末尾
            linkLast(element);
        else        //否則執(zhí)行l(wèi)inkBefore()方法巷波，添加到末尾之前的元素前面
            linkBefore(element, node(index));
    }

這里我們看一下這個(gè)node(index)方法:

    /**
     * Returns the (non-null) Node at the specified element index.返回指定索引處的非空元素
     */
    Node<E> node(int index) {
        if (index < (size >> 1)) {  //size >> 1,表示二進(jìn)制size右移一位萎津，相當(dāng)于size除以2
            Node<E> x = first;
            for (int i = 0; i < index; i++) //如果指定的索引值小于size的一般，那么從第一個(gè)元素開始抹镊，
                x = x.next;         //指針向后移動查找,一直到指定的索引處
            return x;
        } else {            //else,從最后一個(gè)元素開始锉屈，向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {    //e為我們要插入的元素，succ為我們要插入索引處的元素

        final Node<E> pred = succ.prev;     //先將succ的前繼引用(或者前一個(gè)結(jié)點(diǎn)的元素)保存在pred變量中
        final Node<E> newNode = new Node<>(pred, e, succ);  //創(chuàng)建一個(gè)新節(jié)點(diǎn)垮耳，也就是我們要插入的這個(gè)元素
                                    //注意new Node<>(pred, e, succ);這三個(gè)參數(shù)颈渊，可以參照(1.3)處的源碼
     ① succ.prev = newNode; //succ的前繼引用指向NewNode
        if (pred == null)       //如果這個(gè)前繼引用為空，那就說明我們插入的元素是在最前面
            first = newNode;    //直接讓newNode做第一個(gè)元素就行了
        else
    ②       pred.next = newNode;    //否則的話终佛，在讓pred的后繼引用指向newNode節(jié)點(diǎn)
        size++;
        modCount++;
    }

可以看到這里實(shí)際上和簡單鏈表的添加一樣俊嗽，也是分兩步走，而且兩步的順序不能顛倒铃彰。這里需要說明的一點(diǎn)是绍豁，我們在圖上用灰色的點(diǎn)線多畫了兩條箭頭，其中①②分別表示的是新元素的前繼引用和后繼引用分別指向pred和succ的賦值過程豌研。在筆者參考的《大話數(shù)據(jù)結(jié)構(gòu)》中妹田，雙鏈表的添加算上點(diǎn)線的那兩步一共是四步，但實(shí)際上在java中創(chuàng)建newNode的時(shí)候new Node<>(pred, e, succ)這句代碼已經(jīng)一次性做完了上述兩部過程鹃共，真正做事的就是我們在圖中用黑線標(biāo)出的那兩步鬼佣。

三.JAVA中相關(guān)的collection集合

java集合主要由兩個(gè)接口派生而出——Collection接口和Map接口。collection儲存一組類型相同的對象霜浴，且每個(gè)位置只能保存一個(gè)元素晶衷；Map保存的是鍵值對(key-value)。我們本節(jié)重點(diǎn)來說Collection集合阴孟。
??對于collection接口中的方法晌纫，我我們可以通過他的源碼來看:

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

    int size(); //@return the number of elements in this collection
    boolean isEmpty();  //@return <tt>true</tt> if this collection contains no elements
    boolean contains(Object o); //Returns <tt>true</tt> if this collection contains the specified element.
    Object[] toArray(); //Returns an array containing all of the elements in this collection.
    boolean remove(Object o);   //<tt>true</tt> if an element was removed as a result of this call
    boolean add(E e);   //<tt>true</tt> if this collection changed as a result of the call
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    ......
}

上面我們列出了Collection集合的幾個(gè)主要的方法，從注釋中我們可以很清楚的知道他們的用途永丝。

1.Iterable/Iterator接口

我們看上面的collection接口的時(shí)候锹漱，collection接口繼承了Iterable類，我們來看看這個(gè)Iterable類:

public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
     Iterator<T> iterator();

    /*
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
     default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    ......
}

我們先看一下第二個(gè)函數(shù)forEach(Consumer<? super T> action)慕嚷，在java8中哥牍，Iterator新加了這個(gè)個(gè)forEach循環(huán)(注意與java5中的foreach循環(huán)的區(qū)別，大小寫喝检，用法不同)嗅辣，主要用于更加方便的循環(huán)遍歷集合中的元素并對每一個(gè)元素迭代做出相應(yīng)的處理，其中的參數(shù)Consumer<? super T> action就是我們對集合中的元素所施加的操作挠说。舉例說明具體的用法:
傳統(tǒng)方式循環(huán)List:

    List<String> items = new ArrayList<>();
    items.add("A");
    items.add("B");
    items.add("C");
    items.add("D");
    items.add("E");

    for(String item : items){
        System.out.println(item);
    }

在java8中使用forEach循環(huán)+Lambda表達(dá)式遍歷list：

    List<String> items = new ArrayList<>();
    items.add("A");
    items.add("B");
    items.add("C");
    items.add("D");
    items.add("E");

    //lambda
    //Output : A,B,C,D,E
    items.forEach(item->System.out.println(item));

    //Output : C
    items.forEach(item->{
        if("C".equals(item)){
            System.out.println(item);
        }
    });

回到Iterable類中澡谭，我們可以看到他還返回了一個(gè)Iterator接口的實(shí)例。而這個(gè)接口類是什么呢?

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
     default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

可以看到损俭，該接口類中一共有四個(gè)方法蛙奖。其中forEachRemaining()方法是java8之后新增的方法潘酗，主要的作用和上面我們說過的foreach()循環(huán)是一樣的，用法也基本相同外永。
??Iterator類的作用是一個(gè)迭代器崎脉，主要用于操作colloection集合類中的元素。Iterator類必須依附于Collection對象伯顶，Iterator本身并不提供盛裝對象的能力。如果需要?jiǎng)?chuàng)建Iterator對象骆膝，則必需有一個(gè)被迭代的集合祭衩，如果沒有Colletion集合，Iterator也沒有存在的價(jià)值阅签。
??Iterator類中的結(jié)果方法——hasNext()掐暮，用于判斷在遍歷時(shí)collection集合中是否還有剩下的元素；next()用于返回遍歷時(shí)集合中的下一個(gè)元素政钟，這兩個(gè)方法很好理解路克。唯獨(dú)這個(gè)remove()方法有一些注意事項(xiàng)需要說明一下:
??我們可以先看看這個(gè)方法的注釋:

    /**
     * Removes from the underlying collection the last element returned
     * by this iterator (optional operation).  This method can be called
     * only once per call to {@link #next}.  
     * ......
     *
     * @throws IllegalStateException if the {@code next} method has not
     *         yet been called, or the {@code remove} method has already
     *         been called after the last call to the {@code next}
     *         method
     */

翻譯一下:從底層集合中刪除此迭代器返回的最后一個(gè)元素。這個(gè)方法只能在每一次調(diào)用完next()方法之后調(diào)用一次养交。如果next()方法沒有調(diào)用精算，或者remove()方法在上一次next()方法調(diào)用完了之后，又調(diào)用了一次碎连，則會拋出IllegalStateException異常灰羽。
結(jié)合這段注釋，我們交代一下next()方法調(diào)用的幾個(gè)注意事項(xiàng):
??①remove()只能在next()方法調(diào)用完后緊接著調(diào)用一次鱼辙，此時(shí)他刪除的是在他之前調(diào)用的那個(gè)next()返回的元素
??②remove()在調(diào)用之心完之后廉嚼，只能等待下一次next()方法執(zhí)行完了之后，才可以調(diào)用倒戏。
同時(shí)我們還需要注意:③在使用Iterator迭代的過程中怠噪，我們不能手動修改collection集合中的元素，即不能手動調(diào)用collection類本身的remove(),add()杜跷，clear()等方法傍念，只能調(diào)用Iterator的remove()方法。舉個(gè)例子:

public class IteratorTest{
    public static void main(String[] args){
        ...
        Iterator it = books.iterator();
        while(it.hasNext()){
            String book = (String)it.next();
            if("book.equals("hhhhhh"))
                it.remove();    //刪除上一次next()返回的元素葱椭，也就是"hhhhhh"
            book = "666666";  *
        }
    }
}

上面是一段"正常"的程序捂寿，這里需要說明的一點(diǎn)，上一段代碼星號處我們將book的賦值為“666666”孵运，但是當(dāng)我們再次打印出books的集合時(shí)會發(fā)現(xiàn)集合中的元素沒有什么改變秦陋，還是原來的值。這說明——當(dāng)使用Iterator迭代器進(jìn)行迭代時(shí)治笨，Iterator并不是把集合元素本身傳遞給了迭代變量驳概，而是把集合元素的額值出給了迭代變量赤嚼，因此我們在后邊進(jìn)行的各種賦值并不影響集合本身的元素。

public class IteratorTest{
    public static void main(String[] args){
        ...
        Iterator it = books.iterator();
        while(it.hasNext()){
            String book = (String)it.next();
            if("book.equals("hhhhhh"))
                books.remove(book);     //錯(cuò)誤顺又，在迭代時(shí)調(diào)用了修改集合本身的方法
        }
    }
}

這是一段有問題的代碼更卒。這里還需要注意一點(diǎn)，這個(gè)Iterator中的remove()和collection本身的remove(o)方法是不一樣的稚照，一個(gè)有參數(shù)一個(gè)無參數(shù)蹂空。而且子刪除集合中元素時(shí)，我們優(yōu)先考慮用Iterator的remve()方法果录，因?yàn)樗懈叩男噬险恚瑸槭裁茨匕忝迹窟@里我們先作為一個(gè)遺留問題齐鲤，后面我們再詳細(xì)證明惩嘉。
??同樣我們可以用java5中的foreach循環(huán)來遍歷collection集合中的元素哪审，這個(gè)更加簡潔一些:

public class ForeachTest{
    public static void main(String[] args){
        ...
        for(Object obj : books){
            String book = (String)it.next();    //此處的book也不是變量本身
            if("book.equals("hhhhhh"))
                books.remove(book);     //錯(cuò)誤貌笨，在迭代時(shí)調(diào)用了修改集合本身的方法
        }
    }
}
上面加注釋的兩個(gè)地方智润，是foreach循環(huán)與Iterator迭代類似的地方沐兰。

2.List接口梧喷，ArrayList類义起，LinkedList類

colection接口有三個(gè)子類實(shí)現(xiàn)接口:List(有序集合拉背，元素可以重復(fù))，Queue(對列)并扇，Set(無序集合去团，元素不可重復(fù))，其中List又有兩個(gè)最常見的實(shí)現(xiàn)類：ArrayList(動態(tài)數(shù)組)和LinkedList(雙向鏈表)穷蛹，這兩個(gè)也就是我們前面一直說的線性表的順序儲存結(jié)構(gòu)和鏈?zhǔn)絻Υ娼Y(jié)構(gòu)土陪。List接口作為collection接口的子類，當(dāng)然實(shí)現(xiàn)了collection接口中的所有方法肴熏。并且由于List是有序集合鬼雀，因此List集合中增加了一些根據(jù)元素索引來操作集合的方法。

(1)List源碼解析

public interface List<E> extends Collection<E> {
    ......  //省略一些collection中展示過的方法

    /**同時(shí)List接口定義了一些自己的方來實(shí)現(xiàn)“有序”這一功能特點(diǎn)*/
    /**
     *返回列表中指定索引的元素
     */
    E get(int index);
    /**
     *設(shè)定某個(gè)列表索引的值
     */
    E set(int index, E element);
    /**
     *在指定位置插入元素蛙吏，當(dāng)前元素和后續(xù)元素后移
     *這是可選操作源哩，類似于順序表的插入操作
     */
    void add(int index, E element);
    /**
     * 刪除指定位置的元素(可選操作)
     */
    E remove(int index);
    /**
     * 獲得指定對象的最小索引位置，沒有則返回-1
     */
    int indexOf(Object o);
    /**
     * 獲得指定對象的最大索引位置
     * 可以知道的是若集合中無給定元素的重復(fù)元素下
     * 其和indexOf返回值是一樣的
     */
    int lastIndexOf(Object o);
    /**
     *一種更加強(qiáng)大的迭代器鸦做，支持向前遍歷励烦，向后遍歷插入刪除操作
     */
    ListIterator<E> listIterator();          *
    ListIterator<E> listIterator(int index);    *
    /**
     * 返回索引fromIndex(包括)和toIndex(不包括)之間的視圖。
     */
    List<E> subList(int fromIndex, int toIndex);
}

這里解釋一下ListIterator類泼诱，該類繼承自Iterator類坛掠，提供了專門操作List的方法。ListIterator接口在Iterator接口的基礎(chǔ)上增加了洗下面幾個(gè)關(guān)鍵的方法:

public interface ListIterator<E> extends Iterator<E> {

    boolean hasNext();
    E next();
    void remove();

    /**下面是在Iterator基礎(chǔ)上增加的方法*/
    boolean hasPrevious();  //是否還有前繼元素
    E previous();   //返回前一個(gè)元素
    int nextIndex();    //返回下一個(gè)元素的索引
    int previousIndex();    //返回前一個(gè)元素的索引
    void set(E e);  //替換由上一次next()或者previous()方法返回的元素.
    void add(E e);  //在上一次由next()方法返回的元素之前，或者在上一次previous()方法返回的元素之后屉栓，添加一個(gè)元素
}

可以看到舷蒲，ListIterator增加了向前迭代的功能(Iterator只能向后迭代)，而且ListIterator可以通過add()方法向List中添加元素(Iterator只能刪除)友多。

(2)ArrayList源碼解析

(2.1)ArrayList類的頭部:

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

RandomAccess：RandmoAccess是一個(gè)標(biāo)記接口牲平，用于被List相關(guān)類實(shí)現(xiàn)。他主要的作用表明這個(gè)相關(guān)類支持快速隨機(jī)訪問域滥。在ArrayList中纵柿，我們即可以通過元素的序號快速獲取元素對象——這就是快速隨機(jī)訪問。稍后骗绕，我們會比較List的“快速隨機(jī)訪問”和“通過Iterator迭代器訪問”的效率藐窄。
Cloneable:實(shí)現(xiàn)該接口的類可以對該類的實(shí)例進(jìn)行克隆（按字段進(jìn)行復(fù)制）
Serializable：ArrayList支持序列化酬土，能通過序列化去傳輸。
(2.2)ArrayList屬性

    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;     //默認(rèn)的初始容量
    private static final Object[] EMPTY_ELEMENTDATA = {};   //共享的空數(shù)組實(shí)例
    /**
     * 儲存ArrayList元素的數(shù)組緩沖區(qū)格带。ArrayList的容量就是該緩沖數(shù)組的長度撤缴。任何以EMPTY_ELEMENTDATA作為
     * 數(shù)據(jù)元素的空ArrayList，在他們添加第一個(gè)元素的時(shí)候叽唱，都將被擴(kuò)展至DEFAULT_CAPACITY(默認(rèn)為10)長度屈呕。
     */
    transient Object[] elementData;
    private int size;   //ArrayList的大小,即他所包含的元素的個(gè)數(shù)

從ArrayList的屬性元素我們可以看出，他的內(nèi)部是由一個(gè)數(shù)組(elementData)實(shí)現(xiàn)的棺亭。這里需要說明一下transient Object[] elementData;這句中的transient關(guān)鍵字：
??我們都知道一個(gè)對象只要實(shí)現(xiàn)了Serilizable接口虎眨，這個(gè)對象就可以被序列化，java的這種序列化模式為開發(fā)者提供了很多便利镶摘，我們可以不必關(guān)系具體序列化的過程嗽桩，只要這個(gè)類實(shí)現(xiàn)了Serilizable接口，這個(gè)類的所有屬性和方法都會自動序列化凄敢。
??然而在實(shí)際開發(fā)過程中碌冶，我們常常會遇到這樣的問題，這個(gè)類的有些屬性需要序列化涝缝，而其他屬性不需要被序列化扑庞，打個(gè)比方，如果一個(gè)用戶有一些敏感信息（如密碼拒逮，銀行卡號等）罐氨，為了安全起見，不希望在網(wǎng)絡(luò)操作（主要涉及到序列化操作滩援，本地序列化緩存也適用）中被傳輸栅隐，這些信息對應(yīng)的變量就可以加上transient關(guān)鍵字。換句話說，這個(gè)字段的生命周期僅存于調(diào)用者的內(nèi)存中而不會寫到磁盤里持久化约啊。
??總之邑遏，java 的transient關(guān)鍵字為我們提供了便利，你只需要實(shí)現(xiàn)Serilizable接口恰矩，將不需要序列化的屬性前添加關(guān)鍵字transient记盒，序列化對象的時(shí)候，這個(gè)屬性就不會序列化到指定的目的地中外傅。
(3.1)ArrayList構(gòu)造方法

    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;   //EMPTY_ELEMENTDATA等于10纪吮，前面說過
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

可以看到ArrayList有三種構(gòu)造方法:
??①指定長度的初始化
??②初始化一個(gè)空ArrayList,此時(shí)會自動將該初始化的ArrayList長度變?yōu)槟J(rèn)長度10。
??③將指定的集合作為參數(shù)提供給初始化的ArrayList萎胰，并在該構(gòu)造函數(shù)內(nèi)部碾盟，先通過toArray將該集合強(qiáng)制轉(zhuǎn)化為Object類型，然后通過Arrays.copyOf方法將其賦給elementData技竟，也就是ArrayList緩存元素的地方冰肴。
(3.4)ArrayList的增加

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //   擴(kuò)容檢查，確保當(dāng)前數(shù)組在擴(kuò)容之后可以容納它的參數(shù)個(gè)大小的元素
        elementData[size++] = e;    // 將e增加至list的數(shù)據(jù)尾部榔组，容量+1
        return true;
    }

    public void add(int index, E element) {     //在指定位置添加一個(gè)元素
        if (index > size || index < 0)      //判斷是否越界
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        // 對數(shù)組進(jìn)行復(fù)制處理熙尉，目的就是空出index的位置插入element，并將index后的元素位移一個(gè)位置
        ensureCapacityInternal(size + 1);  // 擴(kuò)容檢查
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;   //將元素添加到指定的位置
        size++;         //容量+1
    }

    public boolean addAll(Collection<? extends E> c) {  //將整個(gè)collection集合和添加到List結(jié)尾
        Object[] a = c.toArray();   //將c轉(zhuǎn)化成Object類數(shù)組
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  //擴(kuò)容檢查
        System.arraycopy(a, 0, elementData, size, numNew);  //將c添加到list尾部
        size += numNew;     //更新當(dāng)前容器大小
        return numNew != 0;
    }

    public boolean addAll(int index, Collection<? extends E> c) {   //在指定額索引處添加整個(gè)集合
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // 擴(kuò)容檢查

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

這里我們需要注意的是~~在數(shù)組的增加過程中搓扯，有兩個(gè)過程是是比較耗費(fèi)性能的：數(shù)組擴(kuò)容(ensureCapacityInternal)與數(shù)組復(fù)制(System.arraycopy),這兩個(gè)步驟在上面四個(gè)添加方法中都存在检痰，待會我們會詳細(xì)分析。
(3.5)ArrayList的刪除

    public E remove(int index) {    //根據(jù)索引位置刪除元素
        if (index >= size)      //越界檢查
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];    //去除要?jiǎng)h除的元素锨推，該方法最終會返回這個(gè)值

        int numMoved = size - index - 1;    //計(jì)算數(shù)組要復(fù)制的值的數(shù)量
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);    //復(fù)制數(shù)組
        //數(shù)組最后一個(gè)元素置空铅歼，讓垃圾回收器工作。因?yàn)閯h了一個(gè)元素换可，index之后的元素都往前移動了一個(gè)位置
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

    public boolean remove(Object o) {   //根據(jù)內(nèi)容刪除椎椰，只刪除匹配的那個(gè)
        if (o == null) {    //對要?jiǎng)h除的元素進(jìn)行是否為null的判斷
            for (int index = 0; index < size; index++)  //遍歷數(shù)組，掘地三尺找這個(gè)要?jiǎng)h除的null元素
                if (elementData[index] == null) {   //找到null值了.(注意這個(gè)null值需要用"=="判斷)
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) { //非null是用.equals()比較
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;    //計(jì)算要復(fù)制的數(shù)組容量
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

增加和刪除使我們在ArrayLisy中比較常用的兩個(gè)方法锦担。下面我們來說說上面遺留的那個(gè)關(guān)于擴(kuò)容和復(fù)制的問題俭识。首先我們來看看ensureCapacityInternal方法的源碼:

    private void ensureCapacityInternal(int minCapacity) {  //minCapacity就是我們需要的最小容量
        if (elementData == EMPTY_ELEMENTDATA) { //如果此時(shí)elementData等于空數(shù)組
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  //如果minCapacity比默認(rèn)值10小，則
                                //minCapacity為10洞渔，否則為他自己套媚。
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        //如果當(dāng)前的數(shù)組長度小于我們所需要的minCapacity值(當(dāng)前數(shù)組長度不夠)，則進(jìn)行擴(kuò)容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;   //oldCapacity等于當(dāng)前數(shù)組的長度
        //oldCapacity >> 1磁椒，表示二進(jìn)制的向右移一位堤瘤，相當(dāng)于十進(jìn)制的除以2
        int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity = 1.5 * oldCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;  //如果此時(shí)newCapacity還是小于我們所需要的minCapacity，那就讓他等于minCapacity
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //以這個(gè)新的長度為標(biāo)準(zhǔn)重新創(chuàng)建浆熔，將原來數(shù)組中的元素拷貝一份到新的數(shù)組中去本辐。Arrays.copyOf底層實(shí)現(xiàn)是System.arrayCopy()
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

擴(kuò)容的方法中包含三個(gè)個(gè)過程:
??①判斷需要的大小(minCapacity)是否超出了默認(rèn)長度10.
??②超出了就開始擴(kuò)容，用他的1.5倍長度去和minCapacity作比較(有些java版本是2.5倍)。
??③如果1.5倍大小還是小于所需要的minCapacity大小慎皱，那就將原來的元素復(fù)制到一個(gè)以minCapacity為長度的新數(shù)組中老虫，并將elementData引用指向這個(gè)新數(shù)組。
??可以看到茫多，擴(kuò)容的過程伴隨著數(shù)組的復(fù)制祈匙。如果數(shù)組初試容量過小，假設(shè)為默認(rèn)的10個(gè)大小天揖，而我們使用ArrayList的操作時(shí)需要不斷的增加元素夺欲。在這種場景下，不斷的增加今膊，意味著數(shù)組需要不斷的進(jìn)行擴(kuò)容些阅，擴(kuò)容的過程就是數(shù)組拷貝System.arraycopy的過程，每一次擴(kuò)容就會開辟一塊新的內(nèi)存空間和數(shù)據(jù)的復(fù)制移動(但是數(shù)組復(fù)制不需要開辟新內(nèi)存空間斑唬，只需將數(shù)據(jù)進(jìn)行復(fù)制)市埋，這樣勢必對性能造成影響。那么在這種以寫為主（寫會擴(kuò)容恕刘，刪不會縮容）場景下腰素，提前預(yù)知性的設(shè)置一個(gè)大容量，便可減少擴(kuò)容的次數(shù)雪营，提高了性能。需要注意一點(diǎn)的是ensureCapacity()方法是public的衡便，我們可以通過它手動的增加容量献起。
??增加元素可能會進(jìn)行擴(kuò)容，而刪除元素卻不會進(jìn)行縮容镣陕，如果在以刪除為主的場景下使用list谴餐，一直不停的刪除而很少進(jìn)行增加，或者數(shù)組進(jìn)行一次大擴(kuò)容后呆抑，我們后續(xù)只使用了幾個(gè)空間岂嗓，那就會造成控件的極大浪費(fèi)。這個(gè)時(shí)候我們就可以將底層的數(shù)組elementData的容量調(diào)整為當(dāng)前實(shí)際元素的大小(縮容)鹊碍，來釋放空間厌殉。

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

總結(jié)一下:
??ArrayList底層以數(shù)組實(shí)現(xiàn)，允許重復(fù)侈咕，默認(rèn)第一次插入元素時(shí)創(chuàng)建數(shù)組的大小為10公罕，超出限制時(shí)會增加50%的容量，每次擴(kuò)容都底層采用System.arrayCopy()復(fù)制到新的數(shù)組耀销，初始化時(shí)最好能給出數(shù)組大小的預(yù)估值(采用給定值初始化)楼眷。
(3.6)ArrayList的遍歷方式
ArrayList支持三種遍歷方式
①通過迭代器Itertor去遍歷
②隨機(jī)訪問，通過索引值去遍歷,由于ArrayList實(shí)現(xiàn)了RandomAccess接口，它支持通過索引值去隨機(jī)訪問元素罐柳。
③foreach循環(huán)遍歷
??下面我們用三段程序來測試這三種遍歷方法哪一個(gè)效率最高掌腰，同時(shí)展示三種遍歷的寫法。為了測量更為精準(zhǔn),我們新建三個(gè)類分別測試——randomAccessTest.java张吉；iteratorTest.java齿梁；foreachTest.java。同時(shí)我們采用多次測量(筆者用的eclipse測試時(shí)芦拿，測試結(jié)果經(jīng)常跳票)并采用納秒計(jì)時(shí)(毫秒誤差慘不忍睹)士飒。

public class randomAccessTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        randomAccess(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("randomAccessTime = " + time + "ns");
    }

    public static void randomAccess(List list){
        for(int i=0; i<list.size(); i++){

        }
    }
}

public class iteratorTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        iterator(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("iteratorTime = " + time + "ns");
    }

    public static void iterator(List list){
        Iterator iter = list.iterator();
        while( iter.hasNext()) {
            iter.next();
        }
    }
}

public class foreachTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        foreach(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("foreachTime = " + time + "ms");
    }

    public static void foreach(List list){
        for(Object obj:list) {

        }
    }
}

最終的結(jié)果大致穩(wěn)定為:

randomAccessTime = 7x10^5 ns
iteratorTime = 6x10^6ns
foreachTime = 5x10^6ns

可以看到，雖然結(jié)果經(jīng)常跳票蔗崎，但八九不離十酵幕，randomAccessTime顯然是用時(shí)最快的，畢竟少了一個(gè)數(shù)量級缓苛，這點(diǎn)機(jī)器還是沒有算錯(cuò)的芳撒。也就是說遍歷ArrayList時(shí)，使用隨機(jī)訪問(即未桥，通過索引序號訪問)效率最高,這點(diǎn)毋庸置疑笔刹，使用迭代器遍歷的效率最低(這點(diǎn)是網(wǎng)上的答案，由于兩者的測試結(jié)果處于同一個(gè)數(shù)量級冬耿，加上機(jī)器誤差舌菜，這點(diǎn)筆者很難證實(shí)，讀者可以自行驗(yàn)證)亦镶。
??其實(shí)產(chǎn)生上面結(jié)果日月，我們并不感到意外，因?yàn)殛P(guān)于randomAccessTime這個(gè)接口的注釋中就已經(jīng)很明確的說明了這個(gè)問題:

/**
 * ......
 * As a rule of thumb, a
 * <tt>List</tt> implementation should implement this interface if,
 * for typical instances of the class, this loop:
 * <pre>
 *     for (int i=0, n=list.size(); i < n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>
 * /
 * 根據(jù)經(jīng)驗(yàn)缤骨，一個(gè)list類的實(shí)現(xiàn)類應(yīng)當(dāng)實(shí)現(xiàn)這個(gè)接口爱咬，對于典型的該類的實(shí)例，上面的循環(huán)快于下面的循環(huán)绊起。

(3)LinkedList源碼解析

上面我們在講雙鏈表的時(shí)候已經(jīng)講了linkedList的remove(),add()等關(guān)鍵方法精拟，以及LinkedList的一個(gè)結(jié)點(diǎn)(Node)的構(gòu)成。下面我們來講一下LinkedList剩余的一些知識點(diǎn):
(3.1)LinkedList的頭

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

可以看到LinkedList是一個(gè)繼承自AbstractSequentialList的雙鏈表虱歪，他可以被當(dāng)做堆棧蜂绎，隊(duì)列(實(shí)現(xiàn)了List接口)，
雙端隊(duì)列(實(shí)現(xiàn)了Deque接口)使用实蔽。同時(shí)LinkedList 實(shí)現(xiàn)了Cloneable接口荡碾，即覆蓋了函數(shù)clone()，能克隆局装。LinkedList 實(shí)現(xiàn)java.io.Serializable接口坛吁，這意味著LinkedList支持序列化劳殖，能通過序列化去傳輸。
(3.2)LinkedList的屬性元素

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

其中size就是list的數(shù)量拨脉，和ArrayList一樣哆姻。這個(gè)Node<E> first和Node<E> last就是節(jié)點(diǎn)的前繼引用和后繼引用，Node表示鏈表上的一個(gè)結(jié)點(diǎn)玫膀。這里再貼一遍代碼矛缨，免得你忘了:

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

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

(3.3)LinkedList的構(gòu)造函數(shù)

    /**構(gòu)造一個(gè)空的構(gòu)造函數(shù)，這個(gè)構(gòu)造函數(shù)帖旨，也真夠空的**/
    public LinkedList() {
    }

    /**構(gòu)造一個(gè)包含指定collection元素的表箕昭，這些元素按照collection的迭代器返回的順序排列**/
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

LinkedList就兩個(gè)構(gòu)造函數(shù)，一個(gè)空構(gòu)造函數(shù)解阅，一個(gè)包含指定collection的構(gòu)造函數(shù)落竹。
(3.4)LinkedList的增加方法
上面我們在講雙鏈表的時(shí)候講過在指定位置插入元素的add(int index, E element)方法，現(xiàn)在我們補(bǔ)充一下其他幾種添加方法:
①在雙鏈表的尾部添加一個(gè)元素:

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last; //last表示雙鏈表中的最后一個(gè)元素货抄，l表示指向最后一個(gè)元素的引用
        final Node<E> newNode = new Node<>(l, e, null); //新建一個(gè)后繼引用為空的新節(jié)點(diǎn)述召，后繼為空，意味著他是最后一個(gè)元素
        last = newNode; //直接讓這個(gè)新建的元素作為鏈表的最后一個(gè)元素就行了
        if (l == null)  //指向原本鏈表最后一個(gè)元素的引用l為空蟹地，說明原來的鏈表是一個(gè)空鏈表积暖。
            first = newNode;    //此時(shí)讓這個(gè)新建的結(jié)點(diǎn)元素最為第一個(gè)結(jié)點(diǎn)(就他一個(gè)啊)
        else
            l.next = newNode;   //否則的話，讓原鏈表的后繼引用指向我們新建的這個(gè)節(jié)點(diǎn)怪与，插入完成
        size++;
        modCount++;
    }

②在指定索引處插入一個(gè)集合

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);  //越域判斷

        Object[] a = c.toArray();
        int numNew = a.length;      // 要插入元素的個(gè)數(shù)
        if (numNew == 0)
            return false;

        Node<E> pred, succ;     //申明兩個(gè)節(jié)點(diǎn)類的前繼夺刑，后繼引用(這個(gè)循環(huán)就是在找出原列表中插入索引處的前后引用)
        if (index == size) {    //索引等于鏈表的長度，說明是要求插在鏈表的最后面
            succ = null;
            pred = last;        //此時(shí)后繼引用為空分别，前繼引用指向原鏈表的最后一個(gè)元素
        } else {
            succ = node(index); //否則后繼引用指向原鏈表索引處的元素性誉。node()方法我們之前講過，二分法查找索引處元素
            pred = succ.prev;   //前繼引用指向原鏈表索引處元素的前一個(gè)元素茎杂，完成插入
        }

        for (Object o : a) {    //遍歷我們要插入的這個(gè)集合
            E e = (E) o;
            //新建一個(gè)結(jié)點(diǎn)，以pred作為前繼引用纫雁，該for循環(huán)中每次遍歷得到的collection集合中的e作為結(jié)點(diǎn)本身元素煌往，
            //null作為后繼引用。在第一次進(jìn)行該循環(huán)時(shí)轧邪，通過上一個(gè)if的賦值刽脖，pred指向原鏈表中指定索引處的前一個(gè)元素。
            Node<E> newNode = new Node<>(pred, e, null);    //在第一次循環(huán)遍歷的時(shí)候忌愚，這個(gè)新節(jié)點(diǎn)就是collection集合的第一個(gè)元素
            if (pred == null)   //如果pred為空曲管，說明原鏈表為空
                first = newNode;    //新節(jié)點(diǎn)等于第一個(gè)節(jié)點(diǎn)
            else
                pred.next = newNode;    //否則，原鏈表中指定索引處的前一個(gè)元素 的后繼引用指向這個(gè)新節(jié)點(diǎn)硕糊。
            pred = newNode; //然后將這個(gè)pred指向這個(gè)新的節(jié)點(diǎn)(在第一次循環(huán)中院水，這個(gè)新節(jié)點(diǎn)表示collection集合中的第一個(gè)元素)腊徙，相當(dāng)于工作指針后移，然后重復(fù)上述過程檬某。
        }

        //上述循環(huán)結(jié)束后撬腾，pred指針已經(jīng)指向了collection集合的最后一個(gè)元素，此時(shí)由于succ沒動過恢恼，因此他還是指向原鏈表中指定索引處的后一個(gè)元素
        if (succ == null) { //如果succ為null民傻，和第一個(gè)if中的情況一樣，說明這是在原鏈表的末尾插入元素
            last = pred;    //直接讓此時(shí)的pred也就是collection中的最后一個(gè)元素作為插入后鏈表的最后一個(gè)元素就可以了
        } else {        //否則的話說明是在原鏈表中間插入元素
            pred.next = succ;   //此時(shí)讓collection中最后一個(gè)元素的后繼指針指向 原鏈表索引處的后一個(gè)元素场斑，完成差誒工作
            succ.prev = pred;   //同時(shí)讓succ的前繼指針指向collection的最后一個(gè)元素漓踢，完成雙向鏈表的建立
        }

        size += numNew; //增加鏈表長度
        modCount++;
        return true;
    }

這段代碼中，注釋已經(jīng)寫的很詳細(xì)了漏隐，難點(diǎn)就是for (Object o : a)這個(gè)foreach循環(huán)中,我們插入的collection元素是如何建立雙鏈表聯(lián)系的喧半，讀者務(wù)必要仔細(xì)分析流程。
(3.5)LinkedList的刪除方法
??刪除的方法我們上面講雙鏈表的時(shí)候已經(jīng)說的很詳細(xì)了锁保，這個(gè)沒有什么好說的薯酝，大家可以翻上去復(fù)習(xí)一下。這里我們通過LinkedList的remove()方法的幾種形式爽柒，來講一下算法選型的問題吴菠。
??這個(gè)例子的來源于《數(shù)據(jù)結(jié)構(gòu)與算法分析(java語言描述)》這本書，筆者覺得很典型浩村。題目的要求是做葵，給出一個(gè)線性表，將表中所有偶數(shù)項(xiàng)全部刪除心墅。
①首先第一種算法酿矢，使用普通for循環(huán):

public class usuallyforTest {
    private static long startTime;
    private static long endTime;
    private static final int SIZE = 10000;

    public static void main(String[] args){

        List<Integer> arraylist = new ArrayList<Integer>(SIZE);
        List<Integer> linkedlist  = new LinkedList<Integer>();
        for(int i=0; i<SIZE; i++){
            linkedlist.add(i);
            arraylist.add(i);
        }
        startTime = System.currentTimeMillis();
        usuallyfor(linkedlist);
        endTime = System.currentTimeMillis();
        long linkedlistTime = endTime - startTime;
        System.out.println("usuallyforLinkedlistTime = " + linkedlistTime + "ms");

        startTime = System.currentTimeMillis();
        usuallyfor(arraylist);
        endTime = System.currentTimeMillis();
        long arraylistTime = endTime - startTime;
        System.out.println("usuallyforArraylistTime = " + arraylistTime + "ms");
    }

    public static void usuallyfor(List<Integer> list){
        for(int i=0; i<list.size(); i++){
            if(list.get(i) % 2 == 0){
                list.remove(i);
            }
        }
    }
}

運(yùn)行的結(jié)果是:

usuallyforLinkedlistTime = 57ms
usuallyforArraylistTime = 7ms

如果我們將其中的線性表大小SIZE改為20000(擴(kuò)大兩倍)，得到結(jié)果為:

usuallyforLinkedlistTime = 232ms
usuallyforArraylistTime = 29ms

很顯然怎燥，對于ArrayList和LinkedList而言瘫筐，這個(gè)算法都是時(shí)間復(fù)雜度為O(N^2)的二次算法。

    public static void usuallyfor(List<Integer> list){
        for(int i=0; i<list.size(); i++){
            if(list.get(i) % 2 == 0){
                list.remove(i);
            }
        }
    }

這段代碼中铐姚，對于LinkedList而言策肝，list.get(i)方法是O(N)時(shí)間，慢在尋址隐绵；而他的remove()方法確實(shí)O(1)的之众。對于ArrayList而言，他的get(i)方法是O(1)的依许，但是remove(i)方法卻是O(N)的棺禾，因?yàn)橹灰獎(jiǎng)h除一個(gè)元素，后面的元素都要跟著向前移位峭跳，并伴隨著數(shù)組的復(fù)制拷貝等耗時(shí)操作膘婶；但是他的get(i)卻是O(1)的缺前。
??所以無論對誰，這種算法都不是明智的選擇竣付。但是整體上來看诡延，ArrayList用時(shí)更少一些(1/8的量)。
②使用迭代器Iterator

public class iteratorTest {
    private static long startTime;
    private static long endTime;
    private static final int SIZE = 10000;

    public static void main(String[] args){

        List<Integer> arraylist = new ArrayList<Integer>(SIZE);
        List<Integer> linkedlist  = new LinkedList<Integer>();
        for(int i=0; i<SIZE; i++){
            linkedlist.add(i);
            arraylist.add(i);
        }
        startTime = System.currentTimeMillis();
        iterator(linkedlist);
        endTime = System.currentTimeMillis();
        long linkedlistTime = endTime - startTime;
        System.out.println("iteratorLinkedlistTime = " + linkedlistTime + "ms");

        startTime = System.currentTimeMillis();
        iterator(arraylist);
        endTime = System.currentTimeMillis();
        long arraylistTime = endTime - startTime;
        System.out.println("iteratorArraylistTime = " + arraylistTime + "ms");
    }

    public static void iterator(List<Integer> list){
        Iterator<Integer> iter = list.iterator();
        while( iter.hasNext()) {
            if(iter.next() % 2 == 0){
                iter.remove();
            }
        }
    }
}

結(jié)果為:

iteratorLinkedlistTime = 2ms
iteratorArraylistTime = 10ms

將其中的線性表大小SIZE改為20000(擴(kuò)大兩倍)古胆，得到結(jié)果為:

iteratorLinkedlistTime = 4ms
iteratorArraylistTime = 34ms

顯然肆良，此時(shí)LikedList變成了O(N)一次時(shí)間，而ArrayList變成了O(N^2)二次時(shí)間逸绎，并且LinkedList所用的時(shí)間大大小于ArrayList所用的時(shí)間惹恃。為什么呢？因?yàn)榇藭r(shí)用迭代器循環(huán)遍歷時(shí)棺牧，對于linkdList的next()方法巫糙，是O(1)時(shí)間關(guān)系，remove()也是一次時(shí)間關(guān)系颊乘；但是對于ArrayList而言参淹，rwmove()仍然是O(N)時(shí)間關(guān)系。
??從這兩個(gè)例子中我們可以體驗(yàn)到乏悄，算法的強(qiáng)大之處浙值，實(shí)現(xiàn)同樣功能，采用不同的算法檩小，成敗異變开呐，功業(yè)相反~~妙哉！

3.總結(jié)——ArrayList和LinkedList的比較

寫的太多了规求，不知道該怎么總結(jié)筐付，這里直接照搬一下Java集合干貨系列-（二）LinkedList源碼解析這篇文章最后的總結(jié)，這篇文章寫得很好阻肿，推薦讀者去看一下
??(1)順序插入速度ArrayList會比較快瓦戚，因?yàn)锳rrayList是基于數(shù)組實(shí)現(xiàn)的，數(shù)組是事先new好的丛塌，只要往指定位置塞一個(gè)數(shù)據(jù)就好了伤极；LinkedList則不同，每次順序插入的時(shí)候LinkedList將new一個(gè)對象出來姨伤，如果對象比較大，那么new的時(shí)間勢必會長一點(diǎn)庸疾，再加上一些引用賦值的操作乍楚，所以順序插入LinkedList必然慢于ArrayList
??(2)基于上一點(diǎn)，因?yàn)長inkedList里面不僅維護(hù)了待插入的元素届慈，還維護(hù)了Entry的前置Entry和后繼Entry徒溪，如果一個(gè)LinkedList中的Entry非常多忿偷，那么LinkedList將比ArrayList更耗費(fèi)一些內(nèi)存
??(3)數(shù)據(jù)遍歷的速度，看最后一部分臊泌，這里就不細(xì)講了鲤桥，結(jié)論是：使用各自遍歷效率最高的方式，ArrayList的遍歷效率會比LinkedList的遍歷效率高一些
??(4)有些說法認(rèn)為LinkedList做插入和刪除更快渠概，這種說法其實(shí)是不準(zhǔn)確的：
??①LinkedList做插入茶凳、刪除的時(shí)候，慢在尋址播揪，快在只需要改變Node前后引用
??②ArrayList做插入贮喧、刪除的時(shí)候，慢在數(shù)組元素的批量copy猪狈，快在尋址
??所以箱沦，如果待插入、刪除的元素是在數(shù)據(jù)結(jié)構(gòu)的前半段尤其是非彻兔恚靠前的位置的時(shí)候谓形，LinkedList的效率將大大快過ArrayList，因?yàn)锳rrayList將批量copy大量的元素疆前；越往后寒跳，對于LinkedList來說，因?yàn)樗请p向鏈表峡继，所以在第2個(gè)元素后面插入一個(gè)數(shù)據(jù)和在倒數(shù)第2個(gè)元素后面插入一個(gè)元素在效率上基本沒有差別冯袍，但是ArrayList由于要批量copy的元素越來越少，操作速度必然追上乃至超過LinkedList碾牌。

從這個(gè)分析看出康愤，如果你十分確定你插入、刪除的元素是在前半段舶吗，那么就使用LinkedList征冷；如果你十分確定你刪除、刪除的元素在比較靠后的位置誓琼，那么可以考慮使用ArrayList检激。如果你不能確定你要做的插入、刪除是在哪兒呢腹侣？那還是建議你使用LinkedList吧叔收，因?yàn)橐粊鞮inkedList整體插入、刪除的執(zhí)行效率比較穩(wěn)定傲隶，沒有ArrayList這種越往后越快的情況饺律；二來插入元素的時(shí)候，弄得不好ArrayList就要進(jìn)行一次擴(kuò)容跺株，記住复濒，ArrayList底層數(shù)組擴(kuò)容是一個(gè)既消耗時(shí)間又消耗空間的操作脖卖。

站在巨人的肩膀上摘蘋果:
Java集合干貨系列-（一）ArrayList源碼解析
Java集合干貨系列-（二）LinkedList源碼解析
《大話數(shù)據(jù)結(jié)構(gòu)》
《數(shù)據(jù)結(jié)構(gòu)與算法分析(java語言描述)》
《瘋狂java講義》