摘要：雖然迭代器不常用，但是里面的一些知識(shí)點(diǎn)，設(shè)計(jì)模式我們還是要學(xué)習(xí)以下的。需要注意的是，在使用迭代器期間，若使用非迭代器對(duì)容器進(jìn)行數(shù)據(jù)結(jié)構(gòu)上的改變，將會(huì)通過(guò)報(bào)錯(cuò)。

ArrayList底層數(shù)據(jù)結(jié)構(gòu)使用的是數(shù)組，也就是線性表的順序存儲(chǔ)結(jié)構(gòu)，是一段連續(xù)的存儲(chǔ)單元。具有存取快，增刪慢的特點(diǎn)。ArrayList不是線程安全的

從類(lèi)定義上看，arrayList是支持泛型的,繼承自AbstractList,實(shí)現(xiàn)了List接口。同時(shí)實(shí)現(xiàn)了Serializable接口，因?yàn)樗С中蛄谢?，支持序列化傳輸。?shí)現(xiàn)了Cloneable接口，可以被克隆。實(shí)現(xiàn)了RandomAccess接口，可以被快速訪問(wèn)，實(shí)際上就是通過(guò)下標(biāo)進(jìn)行訪問(wèn),RandomAccess只是一個(gè)標(biāo)記，無(wú)任何定義。

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

private static final long serialVersionUID = 8683452581122892189L;

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;

private int size;

serialVersionUID：是實(shí)現(xiàn)了Serializable可自動(dòng)生成的。簡(jiǎn)單來(lái)說(shuō)，Java的序列化機(jī)制是通過(guò)在運(yùn)行時(shí)判斷類(lèi)的serialVersionUID來(lái)驗(yàn)證版本一致性的。在進(jìn)行反序列化時(shí)，JVM會(huì)把傳來(lái)的字節(jié)流中的serialVersionUID與本地相應(yīng)實(shí)體（類(lèi)）的serialVersionUID進(jìn)行比較，如果相同就認(rèn)為是一致的，可以進(jìn)行反序列化，否則就會(huì)出現(xiàn)序列化版本不一致的異常。

EMPTY_ELEMENTDATA & DEFAULTCAPACITY_EMPTY_ELEMENTDATA :其實(shí)兩個(gè)都是一個(gè)空數(shù)組，只不過(guò)再明確長(zhǎng)度為0時(shí)，會(huì)用EMPTY_ELEMENTDATA，無(wú)參構(gòu)造調(diào)用會(huì)用DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

DEFAULT_CAPACITY:當(dāng)沒(méi)有指定容量，第一次添加元素,arraylist的初始容量.

elementData:arraylist的buffer，arrayList的容量就是elementData的容量。當(dāng)arraylist為空時(shí)，elementData就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，當(dāng)添加第一個(gè)元素的時(shí)候，會(huì)自動(dòng)擴(kuò)容DEFAULT_CAPACITY(10)長(zhǎng)度.注意到，它被transient修飾，也就是不參與序列化，只存在調(diào)用者的內(nèi)存當(dāng)中。

size:arraylist含有元素的個(gè)數(shù)。

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

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

public ArrayList(Collection c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

arraylist一共定義了三個(gè)構(gòu)造函數(shù)。

構(gòu)造一個(gè)指定大小的elementData

初始化一個(gè)默認(rèn)數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA

將一個(gè)集合Collection初始化為arrayList

/**
trim就是去除兩段空格的意思，這個(gè)方法是用來(lái)給elementdata瘦身用，將占據(jù)的多余的空間給釋放掉
*/
public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

/**
確保容器容量，若為空,minCapacity去當(dāng)前值和默認(rèn)容量的最大值，然后判斷是否進(jìn)行擴(kuò)容
*/
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

/**
minCapacity大于數(shù)組長(zhǎng)度，則調(diào)用grow函數(shù)進(jìn)行擴(kuò)容
*/
private void ensureExplicitCapacity(int minCapacity) {
        /**
        modCount:是父類(lèi)AbstractList的變量。集合中所有用到modCount的都是線程不安全的。在做對(duì)線性表結(jié)構(gòu)修改的操作會(huì)對(duì)modCount進(jìn)行+1，當(dāng)我們調(diào)用iterator，會(huì)檢測(cè)modCount是不是我們期望的，如果在調(diào)用期間modCount又發(fā)生了變化，iterator將拋出異常.
        */
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

/**
獲取到數(shù)組長(zhǎng)度，對(duì)其進(jìn)行擴(kuò)容，增加將近一半的容量，使用Arrays.copyOF進(jìn)行擴(kuò)容
*/
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

//返回容器元素個(gè)數(shù)
public int size() {
        return size;
    }

//判斷是否為空
public boolean isEmpty() {
        return size == 0;
    }

/**
兩個(gè)方法都是判斷索引正否越界
*/
private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * A version of rangeCheck used by add and addAll.
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

/**
* 此方法用戶(hù)往線性表最后一位插入元素，若容器容量足夠，則時(shí)間復(fù)雜度是O（1），若需要擴(kuò)容，則時(shí)間復(fù)雜度是O（n）
*/
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
/**
* 此方法用于向指定位置插入元素，時(shí)間復(fù)雜度為O(n)
*    1.判斷角標(biāo)是否越界  2.保證數(shù)組容量足夠，不夠通過(guò)新建數(shù)組擴(kuò)容 3.從數(shù)組指定索引復(fù)制直到最后一位，全*部加一
*/
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

//刪除制定索引元素，需算出位移量，將index之后的其他元素提前一位，其復(fù)雜度為o(n)
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;
    }
    //遍及elementData，若值相同，則調(diào)用fastRemove移除
    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;
    }
    //此方法和remove大致相同，只是少了判斷索引越界的問(wèn)題，因?yàn)樵诒徽{(diào)用前已經(jīng)通過(guò)遍歷方式驗(yàn)證了
    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
    }

什么是迭代器呢？其實(shí)就是用來(lái)遍歷容器內(nèi)部分或全部元素的對(duì)象，每個(gè)迭代器代表容器中確定的地址，我們把具有類(lèi)似行為的都叫迭代器。雖然迭代器不常用，但是里面的一些知識(shí)點(diǎn)，設(shè)計(jì)模式我們還是要學(xué)習(xí)以下的。arraylist迭代器分為Iterator和ListIterator。Iterator接口只定義了遍歷和刪除的職責(zé)，ListIterator繼承于Iterator,新增了add和set方法，方便我們?cè)诘臅r(shí)候增加刪除元素。需要注意的是，在使用迭代器期間，若使用非迭代器對(duì)容器進(jìn)行數(shù)據(jù)結(jié)構(gòu)上的改變，將會(huì)通過(guò)checkForComodification()報(bào)錯(cuò)。

ListIterator的實(shí)現(xiàn)如下:

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

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

        public int nextIndex() {
            return cursor;
        }

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

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

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

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

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

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

arraylist源碼方法實(shí)在是過(guò)多，無(wú)法一一向大家解釋?zhuān)贿^(guò)相信大家理解上面的，再去研究剩下的內(nèi)容應(yīng)該沒(méi)有多大問(wèn)題。通過(guò)學(xué)習(xí)源碼，我們可以更清楚的知道arraylist在操作時(shí)，底層結(jié)構(gòu)發(fā)生了哪些變化，為什么arraylist適合存取，不適合增刪.