摘要：將之前第位置的元素置空，返回被刪除的元素。平常常用的迭代器方法就是判斷當(dāng)前索引是否等于。最重要的是會(huì)更新，此時(shí)調(diào)用了父類的方法，會(huì)使，所以更新了，讓后續(xù)的檢查不會(huì)拋異常。

本篇主要介紹ArrayList的用法和源碼分析，基于jdk1.8，先從List接口開(kāi)始。

List接口定義了如下方法：

int size();
boolean isEmpty();
boolean contains(Object o);
Iterator iterator();
Object[] toArray();
 T[] toArray(T[] a);
boolean add(E e);
void add(int index, E element);
boolean addAll(Collection c);
boolean addAll(int index, Collection c);
boolean remove(Object o);
E remove(int index);
boolean removeAll(Collection c);
boolean retainAll(Collection c);
void clear();
E get(int index);
E set(int index, E element);
int indexOf(Object o);
int lastIndexOf(Object o);
List subList(int fromIndex, int toIndex);
ListIterator listIterator();
ListIterator listIterator(int index);

乍一看，這么多方法。其實(shí)很多方法是同樣的功能，方法重載而已。
接下來(lái)逐個(gè)介紹下List定義的方法。

size 獲得List元素的個(gè)數(shù)

isEmpty 判斷List是否為空

contains/containsAll 判斷List中是否有該元素，或者有該集合中的所有元素

iterator 獲得迭代器對(duì)象用于迭代

toArray 將List轉(zhuǎn)換成數(shù)組

add/addAll 添加元素至List中，默認(rèn)直接添加到最后，也可以選擇指定的位置，還可以添加整個(gè)集合

remove/removeAll 刪除元素，可以根據(jù)元素刪除，也可以根據(jù)索引刪除,還可以根據(jù)集合刪除

retainAll 取與目標(biāo)集合的交集

clear 清空List的所有元素

get 根據(jù)索引獲得元素

set 覆蓋索引處的元素

indexOf 獲得該元素的索引

lastIndexOf 獲得該元素的索引（從后往前）

subList 獲得子List根據(jù)start 和 end

listIterator 獲得ListIterator對(duì)象

方法名言簡(jiǎn)意賅，基本上都可以從方法名知道方法的目的。
接下來(lái)分析List的常用實(shí)現(xiàn)類：
ArrayList
LinkedList
Vector

本篇介紹ArrayList

在我的理解中，ArrayList是一個(gè)封裝的數(shù)組，提供了一些便利的方法供使用者使用，規(guī)避了使用原生數(shù)組的風(fēng)險(xiǎn)。

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

繼承了AbstractList即成為了List，就要實(shí)現(xiàn)定義的所有方法。
實(shí)現(xiàn)了RandomAccess接口 就是提供了隨機(jī)訪問(wèn)能力，可以通過(guò)下標(biāo)獲得指定元素
實(shí)現(xiàn)了Cloneable接口 代表是可克隆的，需要實(shí)現(xiàn)clone方法
實(shí)現(xiàn)了Serializable接口 代表ArrayList是可序列化的

下面介紹下ArrayList的主要方法

boolean add(E e)
先附上源碼

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

此方法的執(zhí)行邏輯：

判斷數(shù)組長(zhǎng)度是否夠，不夠則擴(kuò)容。默認(rèn)擴(kuò)容1.5倍

elementData[size++] = e;將新元素添加進(jìn)去。

    private void ensureCapacityInternal(int minCapacity) {
            //是否是空List，是則使用初始容量擴(kuò)容
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;    //增加修改次數(shù)
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//擴(kuò)容1.5倍，采用位運(yùn)算
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);//最大容量就是Integer的最大值
        // minCapacity is usually close to size, so this is a win:
        //采用Arrays的copyOf進(jìn)行深拷貝，其中調(diào)用的本地方法System.arraycopy，此方法是在內(nèi)存中操作因此速度會(huì)很快。
        elementData = Arrays.copyOf(elementData, newCapacity);
        //至此擴(kuò)容結(jié)束
    }

void add(int index, E element)方法稍有不同

首先檢查index是否合法

擴(kuò)容

將新元素插入指定位置

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

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //將index -> （size -1）的元素都往后移動(dòng)一位 
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

boolean addAll(Collection c)
boolean addAll(int index, Collection c)
這兩個(gè)方法和上面的add大同小異，第一步都是判斷容量，并擴(kuò)容。
容量大小從1變?yōu)閏的length，elementData[index] = element;賦值也變?yōu)閿?shù)組拷貝，
直接上代碼，秒懂。

    public boolean addAll(Collection c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    public boolean addAll(int index, Collection c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        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;
    }

無(wú)論是哪種add，都需要先執(zhí)行方法 ensureCapacityInternal(size + 1) 進(jìn)行容量判斷及擴(kuò)容，確保之后的操作不會(huì)產(chǎn)生數(shù)組越界。

建議在我們?nèi)粘９ぷ鲿r(shí)，如果大概知道元素的數(shù)量，可以在初始化的時(shí)候指定大小，這樣可以減少擴(kuò)容的次數(shù)，提升性能。

E remove(int index)

檢查是否索引不正確。

計(jì)算移動(dòng)的元素的個(gè)數(shù)，數(shù)組往前移動(dòng)。

將之前第size位置的元素置空，返回被刪除的元素。

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        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

        return oldValue;
    }

boolean remove(Object o)

區(qū)分要?jiǎng)h除的元素是null還是非null。

找到該元素的索引，執(zhí)行上面方法邏輯的2、3步。

    public boolean remove(Object o) {
        if (o == null) {
            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
    }

這種方法依賴元素的equals方法，循環(huán)遍歷數(shù)組，因?yàn)锳rrayList是允許null元素的，所以無(wú)論是使用if (o.equals(elementData[index])) 還是 if (elementData[index].equals(o)) 均可能產(chǎn)生空指針，所以多帶帶對(duì)null進(jìn)行處理，邏輯都是一樣的。
奇怪的是這個(gè)fastRemove方法，原本以為會(huì)有些特殊處理，結(jié)果發(fā)現(xiàn)代碼和上面remove(int index)中的一模一樣，為什么上面的remove中不調(diào)用這個(gè)fastRemove呢？難道寫兩個(gè)remove方法的不是同一人？邏輯不影響，只是代碼冗余了一點(diǎn)。

boolean removeAll(Collection c)

    public boolean removeAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

刪除存在于目標(biāo)集合的方法，使用了batchRemove(Collection c, boolean complement)這個(gè)方法，這個(gè)方法作了封裝，在retainAll(Collection c)取并集這個(gè)方法也有使用。
retainAll中是這樣使用的：

return batchRemove(c, true);

和我們的removeAll只差第二個(gè)參數(shù)boolean complement，remove是false，retail是true，那到底是什么意思呢？complement的原意的補(bǔ)充，在這里我理解為保留，remove就不保留，retail就保留，接著我們分析batchRemove這個(gè)方法。

 
    private boolean batchRemove(Collection c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

定義了 r 和 w兩個(gè)int，r用于遍歷原來(lái)的數(shù)組，w的意思是新的數(shù)組的size。
假如定義2個(gè)數(shù)組用于舉例，
數(shù)組1，五個(gè)元素 1，2，3，4，5
數(shù)組2，五個(gè)元素 3，4，6，7，8

數(shù)組1調(diào)用removeAll（數(shù)組2）
此時(shí)進(jìn)入batchRemove，我們來(lái)一步一步走看r，w如何變化
此時(shí)complement是false，即數(shù)組2中沒(méi)有數(shù)組1中第r個(gè)元素才滿足if條件

r = 0, w = 0， elementData[r] = 1, c.contains(elementData[r]) = false.
執(zhí)行elementData[w++] = elementData[r]，
數(shù)組1：1，2，3，4，5

r = 1, w = 1， elementData[r] = 2, c.contains(elementData[r]) = false.
執(zhí)行elementData[w++] = elementData[r]，
數(shù)組1：1，2，3，4，5

r = 2, w = 2， elementData[r] = 3, c.contains(elementData[r]) = true.
此時(shí)if條件不滿足了，w不自增了,代表elementData[r]要不存在與新數(shù)組中，要被刪除，所以跳過(guò)了。

r = 3, w = 2， elementData[r] = 4, c.contains(elementData[r]) = true.
if條件依舊不滿足,w不自增，此元素也是要?jiǎng)h除。

r = 4, w = 2， elementData[r] = 5, c.contains(elementData[r]) = false.
執(zhí)行elementData[w++] = elementData[r],
數(shù)組1：1，2，5，4，5
此時(shí)for循環(huán)結(jié)束，elementData數(shù)組目前是這樣的，接著執(zhí)行finally中的代碼，

首先執(zhí)行

            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }

我們的情況是 r=size，那什么時(shí)候r會(huì)不等于size呢，jdk中寫了注釋，就是在if判斷時(shí)，調(diào)用數(shù)組2的contains方法,可能會(huì)拋空指針等異常。這時(shí)數(shù)組還沒(méi)有遍歷完，那r肯定是小于size的。
那沒(méi)判斷的那些數(shù)據(jù)還要不要處理？保守起見(jiàn)jdk還是會(huì)將他保存在數(shù)組中，因?yàn)樽罱Kw是作為新的size，所以w加上了沒(méi)處理過(guò)的個(gè)數(shù)size - r。

接著執(zhí)行下面一段

            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }

這段代碼意圖很清晰，w因?yàn)槭切碌膕ize值，所以將w及其之后的都置位null，增加修改次數(shù)，
給size賦予新值之后就結(jié)束了。

刪除元素盡量使用指定下標(biāo)的方法，性能好。

每次刪除都會(huì)進(jìn)行數(shù)組移動(dòng)（除非刪除最后一位），如果頻繁刪除元素，請(qǐng)使用LinkedList

boolean contains(Object o)
contains 底層調(diào)用的是indexOf方法

     public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

int indexOf(Object o)

    public int indexOf(Object o) {
        if (o == null) {
            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;
    }

就是循環(huán)遍歷，一個(gè)個(gè)比對(duì)，有則返回對(duì)應(yīng)下標(biāo)，無(wú)則返回-1
對(duì)應(yīng)的lastIndexOf是從最后往前遍歷。

    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;
    }

E get(int index)

        rangeCheck(index);

        return elementData(index);

先檢查index，再返回?cái)?shù)組對(duì)應(yīng)元素。

E set(int index, E element)

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

先檢查index，在覆蓋index的元素，返回舊元素。

void clear()

        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;

增加修改次數(shù)，將所有元素置空，size設(shè)置為0，需要注意的是，數(shù)組的大小是沒(méi)有變化的。

int size()
size方法就是直接將size變量直接返回

    public int size() {
        return size;
    }

boolean isEmpty()
判斷size是否等于0

    public boolean isEmpty() {
        return size == 0;
    }

Iterator iterator()

    public Iterator iterator() {
        return new Itr();
    }

如代碼所示，創(chuàng)建了一個(gè)Itr對(duì)象并返回，接下來(lái)看Itr類的定義

    private class Itr implements Iterator {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

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

首先介紹下三個(gè)成員變量

cursor，代表下一個(gè)訪問(wèn)元素的在elementData數(shù)組中的索引，初始值是0。

lastRet，代表上一個(gè)訪問(wèn)元素在elementData數(shù)組中的索引，初始值是-1。

expectedModCount,預(yù)期的modcount的值，在Itr對(duì)象創(chuàng)建的時(shí)候從父類ArrayList的modcount獲得，用于判斷在使用該對(duì)象迭代時(shí)，有么有對(duì)數(shù)組進(jìn)行修改，有則會(huì)拋出ConcurrentModificationException。

平常常用的迭代器方法
hasNext()
就是判斷當(dāng)前索引是否等于size。

E next()
首先檢查list是否被修改過(guò)，expectedModCount是在創(chuàng)建對(duì)象時(shí)就獲得了，如果在之后對(duì)list進(jìn)行了其他修改操作的話，modCount就會(huì)增加，就會(huì)拋出ConcurrentModificationException。
沒(méi)有異常就按下表返回坐標(biāo)，cursor自增，lastRet也自增。

void remove()

首先判斷是否能刪除，若能則調(diào)用父類的remove方法，刪除元素，接著會(huì)更新cursor和lastRet。
最重要的是會(huì)更新expectedModCount，此時(shí)調(diào)用了父類的remove方法，會(huì)使modCount+1，所以更新了 expectedModCount，讓后續(xù)的檢查不會(huì)拋異常。

ListIterator listIterator

listIterator和iterator一樣，只不過(guò)listIterator有更多的方法，相當(dāng)于iterator的加強(qiáng)版。
定義如下

    private class ListItr extends Itr implements ListIterator {
        ListItr(int index) {
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public E previous() {
            checkForComodification();
            try {
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor-1;
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                AbstractList.this.add(i, e);
                lastRet = -1;
                cursor = i + 1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

沒(méi)有什么需要注意的地方，基本的方法都從Iterator中繼承過(guò)來(lái)并添加一些方法。

List subList(int fromIndex, int toIndex)

這又是一個(gè)內(nèi)部類

class SubList extends AbstractList {
    private final AbstractList l;
    private final int offset;
    private int size;

    SubList(AbstractList list, int fromIndex, int toIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        this.modCount = l.modCount;
    }
    。
    。
    。
}

持有了父類的引用，內(nèi)部的所有方法都是通過(guò)父類的這個(gè)引用去完成的，
所以需要注意的是，subList不是返回一個(gè)新的List，還是原來(lái)的引用，所以改變subList的數(shù)據(jù)，原有的數(shù)據(jù)也會(huì)更改。

終于把基本的方法都介紹完了，從源碼的角度分析了所有的方法，感覺(jué)對(duì)ArrayList知根知底了，用它時(shí)肯定會(huì)更加得心應(yīng)手了，看了源碼才有原來(lái)實(shí)現(xiàn)都這么簡(jiǎn)單啊這樣的感覺(jué)，不過(guò)從中也學(xué)習(xí)到了大牛規(guī)范的代碼風(fēng)格，良好的結(jié)構(gòu)，可讀性很高。下篇分析List的另一個(gè)實(shí)現(xiàn)類，LinkedList。