JDK中java.util.ArrayList 類的介紹

1、ArrayList 定義

ArrayList 是一個用數(shù)組實現(xiàn)的集合，支持隨機訪問，元素有序且可以重復。

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

①、實現(xiàn) RandomAccess 接口

這是一個標記接口，一般此標記接口用于 List 實現(xiàn)，以表明它們支持快速（通常是恒定時間）的隨機訪問。該接口的主要目的是允許通用算法改變其行為，以便在應用于隨機或順序訪問列表時提供良好的性能。

比如在工具類 Collections(這個工具類后面會詳細講解)中，應用二分查找方法時判斷是否實現(xiàn)了 RandomAccess 接口：

int binarySearch(List< ? extends Comparable< ? super T >> list, T key) {
        if (list instanceof RandomAccess || list.size()

②、實現(xiàn) Cloneable 接口

這個類是 java.lang.Cloneable，前面我們講解深拷貝和淺拷貝的原理時，我們介紹了淺拷貝可以通過調用 Object.clone() 方法來實現(xiàn)，但是調用該方法的對象必須要實現(xiàn) Cloneable 接口，否則會拋出 CloneNoSupportException異常。

Cloneable 和 RandomAccess 接口一樣也是一個標記接口，接口內無任何方法體和常量的聲明，也就是說如果想克隆對象，必須要實現(xiàn) Cloneable 接口，表明該類是可以被克隆的。

③、實現(xiàn) Serializable 接口

這個沒什么好說的，也是標記接口，表示能被序列化。

④、實現(xiàn) List 接口

這個接口是 List 類集合的上層接口，定義了實現(xiàn)該接口的類都必須要實現(xiàn)的一組方法，如下所示，下面我們會對這一系列方法的實現(xiàn)做詳細介紹。

2、字段屬性

//集合的默認大小
        private static final int DEFAULT_CAPACITY = 10;
        //空的數(shù)組實例
        private static final Object[] EMPTY_ELEMENTDATA = {};
        //這也是一個空的數(shù)組實例，和EMPTY_ELEMENTDATA空數(shù)組相比是用于了解添加元素時數(shù)組膨脹多少
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        //存儲 ArrayList集合的元素，集合的長度即這個數(shù)組的長度
        //1、當 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 時將會清空 ArrayList
        //2、當添加第一個元素時，elementData 長度會擴展為 DEFAULT_CAPACITY=10
        transient Object[] elementData;
        //表示集合的長度
        private int size;

3、構造函數(shù)

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

此無參構造函數(shù)將創(chuàng)建一個 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 聲明的數(shù)組，注意此時初始容量是0，而不是大家以為的 10。

注意 ：根據(jù)默認構造函數(shù)創(chuàng)建的集合，ArrayList list = new ArrayList();此時集合長度是0.

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

初始化集合大小創(chuàng)建 ArrayList 集合。當大于0時，給定多少那就創(chuàng)建多大的數(shù)組；當?shù)扔?時，創(chuàng)建一個空數(shù)組；當小于0時，拋出異常。

public ArrayList(Collection< ? extends E > 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 集合中去。

4、添加元素

通過前面的字段屬性和構造函數(shù)，我們知道 ArrayList 集合是由數(shù)組構成的，那么向 ArrayList 中添加元素，也就是向數(shù)組賦值。我們知道一個數(shù)組的聲明是能確定大小的，而使用 ArrayList 時，好像是能添加任意多個元素，這就涉及到數(shù)組的擴容。

擴容的核心方法就是調用前面我們講過的Arrays.copyOf 方法，創(chuàng)建一個更大的數(shù)組，然后將原數(shù)組元素拷貝過去即可。下面我們看看具體實現(xiàn)：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //添加元素之前，首先要確定集合的大小
        elementData[size++] = e;
        return true;
    }

如上所示，在通過調用 add 方法添加元素之前，我們要首先調用 ensureCapacityInternal 方法來確定集合的大小，如果集合滿了，則要進行擴容操作。

private void ensureCapacityInternal(int minCapacity) {//這里的minCapacity 是集合當前大小+1
        //elementData 是實際用來存儲元素的數(shù)組，注意數(shù)組的大小和集合的大小不是相等的，前面的size是指集合大小
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//如果數(shù)組為空，則從size+1的值和默認值10中取最大的
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;//不為空，則返回size+1
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

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

在 ensureExplicitCapacity 方法中，首先對修改次數(shù)modCount加一，這里的modCount給ArrayList的迭代器使用的，在并發(fā)操作被修改時，提供快速失敗行為（保證modCount在迭代期間不變，否則拋出ConcurrentModificationException異常，可以查看源碼865行），接著判斷minCapacity是否大于當前ArrayList內部數(shù)組長度，大于的話調用grow方法對內部數(shù)組elementData擴容，grow方法代碼如下：

private void grow(int minCapacity) {
        int oldCapacity = elementData.length;//得到原始數(shù)組的長度
        int newCapacity = oldCapacity + (oldCapacity > > 1);//新數(shù)組的長度等于原數(shù)組長度的1.5倍
        if (newCapacity - minCapacity < 0)//當新數(shù)組長度仍然比minCapacity小，則為保證最小長度，新數(shù)組等于minCapacity
            newCapacity = minCapacity;
        //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 = 2147483639
        if (newCapacity - MAX_ARRAY_SIZE > 0)//當?shù)玫降男聰?shù)組長度比 MAX_ARRAY_SIZE 大時，調用 hugeCapacity 處理大數(shù)組
            newCapacity = hugeCapacity(minCapacity);
        //調用 Arrays.copyOf 將原數(shù)組拷貝到一個大小為newCapacity的新數(shù)組（注意是拷貝引用）
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // 
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? //minCapacity > MAX_ARRAY_SIZE,則新數(shù)組大小為Integer.MAX_VALUE
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

對于 ArrayList 集合添加元素，我們總結一下：

①、當通過 ArrayList() 構造一個空集合，初始長度是為0的，第 1 次添加元素，會創(chuàng)建一個長度為10的數(shù)組，并將該元素賦值到數(shù)組的第一個位置。

②、第 2 次添加元素，集合不為空，而且由于集合的長度size+1是小于數(shù)組的長度10，所以直接添加元素到數(shù)組的第二個位置，不用擴容。

③、第 11 次添加元素，此時 size+1 = 11，而數(shù)組長度是10，這時候創(chuàng)建一個長度為10+10*0.5 = 15 的數(shù)組（擴容1.5倍），然后將原數(shù)組元素引用拷貝到新數(shù)組。并將第 11 次添加的元素賦值到新數(shù)組下標為10的位置。

④、第 Integer.MAX_VALUE - 8 = 2147483639，然后 2147483639%1.5=1431655759（這個數(shù)是要進行擴容） 次添加元素，為了防止溢出，此時會直接創(chuàng)建一個 1431655759+1 大小的數(shù)組，這樣一直，每次添加一個元素，都只擴大一個范圍。

⑤、第 Integer.MAX_VALUE - 7 次添加元素時，創(chuàng)建一個大小為 Integer.MAX_VALUE 的數(shù)組，在進行元素添加。

⑥、第 Integer.MAX_VALUE + 1 次添加元素時，拋出 OutOfMemoryError 異常。

注意：能向集合中添加 null 的，因為數(shù)組可以有 null 值存在。

Object[] obj = {null,1};

ArrayList list = new ArrayList();
list.add(null);
list.add(1);
System.out.println(list.size());//2

5、刪除元素

①、根據(jù)索引刪除元素

public E remove(int index) {
        rangeCheck(index);//判斷給定索引的范圍，超過集合大小則拋出異常

        modCount++;
        E oldValue = elementData(index);//得到索引處的刪除元素

        int numMoved = size - index - 1;
        if (numMoved > 0)//size-index-1 > 0 表示 0<= index < (size-1),即索引不是最后一個元素
            //通過 System.arraycopy()將數(shù)組elementData 的下標index+1之后長度為 numMoved的元素拷貝到從index開始的位置
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; //將數(shù)組最后一個元素置為 null，便于垃圾回收

        return oldValue;
    }

remove(int index) 方法表示刪除索引index處的元素，首先通過 rangeCheck(index) 方法判斷給定索引的范圍，超過集合大小則拋出異常；接著通過 System.arraycopy 方法對數(shù)組進行自身拷貝。關于這個方法的用法可以參考這篇博客。

②、直接刪除指定元素

public boolean remove(Object o) {
        if (o == null) {//如果刪除的元素為null
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {//不為null，通過equals方法判斷對象是否相等
            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; // 
    }

remove(Object o)方法是刪除第一次出現(xiàn)的該元素。然后通過System.arraycopy進行數(shù)組自身拷貝。

6、修改元素

通過調用 set(int index, E element) 方法在指定索引 index 處的元素替換為 element。并返回原數(shù)組的元素。

public E set(int index, E element) {
        rangeCheck(index);//判斷索引合法性

        E oldValue = elementData(index);//獲得原數(shù)組指定索引的元素
        elementData[index] = element;//將指定所引處的元素替換為 element
        return oldValue;//返回原數(shù)組索引元素
    }

通過調用 rangeCheck(index) 來檢查索引合法性。

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

當索引為負數(shù)時，會拋出 java.lang.ArrayIndexOutOfBoundsException 異常。當索引大于集合長度時，會拋出 IndexOutOfBoundsException 異常。

7、查找元素

①、根據(jù)索引查找元素

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

        return elementData(index);
    }

同理，首先還是判斷給定索引的合理性，然后直接返回處于該下標位置的數(shù)組元素。

②、根據(jù)元素查找索引

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

注意 ：indexOf(Object o) 方法是返回第一次出現(xiàn)該元素的下標，如果沒有則返回 -1。

還有 lastIndexOf(Object o) 方法是返回最后一次出現(xiàn)該元素的下標。

8、遍歷集合

①、普通 for 循環(huán)遍歷 前面我們介紹查找元素時，知道可以通過get(int index)方法，根據(jù)索引查找元素，那么遍歷同理：

ArrayList list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
for(int i = 0 ; i < list.size() ; i++){
    System.out.print(list.get(i)+" ");
}

②、迭代器 iterator 先看看具體用法：

ArrayList< String > list = new ArrayList<  >();
list.add("a");
list.add("b");
list.add("c");
Iterator< String > it = list.iterator();
while(it.hasNext()){
    String str = it.next();
    System.out.print(str+" ");
}

在介紹 ArrayList 時，我們知道該類實現(xiàn)了 List 接口，而 List 接口又繼承了 Collection 接口，Collection 接口又繼承了 Iterable 接口，該接口有個 Iteratoriterator() 方法，能獲取 Iterator 對象，能用該對象進行集合遍歷，為什么能用該對象進行集合遍歷？我們再看看 ArrayList 類中的該方法實現(xiàn)：

public Iterator< E > iterator() {
         return new Itr();
     }

該方法是返回一個 Itr 對象，這個類是 ArrayList 的內部類。

private class Itr implements Iterator< E > {
        int cursor;       //游標， 下一個要返回的元素的索引
        int lastRet = -1; // 返回最后一個元素的索引; 如果沒有這樣的話返回-1.
        int expectedModCount = modCount;

        //通過 cursor ！= size 判斷是否還有下一個元素
        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];//返回索引為i處的元素，并將 lastRet賦值為i
        }

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

            try {
                ArrayList.this.remove(lastRet);//調用ArrayList的remove方法刪除元素
                cursor = lastRet;//游標指向刪除元素的位置，本來是lastRet+1的，這里刪除一個元素，然后游標就不變了
                lastRet = -1;//lastRet恢復默認值-1
                expectedModCount = modCount;//expectedModCount值和modCount同步，因為進行add和remove操作，modCount會加1
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer< ? super E > consumer) {//便于進行forEach循環(huán)
            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();
        }

        //前面在新增元素add() 和 刪除元素 remove() 時，我們可以看到 modCount++。修改set() 是沒有的
        //也就是說不能在迭代器進行元素迭代時進行增加和刪除操作，否則拋出異常
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

注意在進行 next() 方法調用的時候，會進行 checkForComodification() 調用，該方法表示迭代器進行元素迭代時，如果同時進行增加和刪除操作，會拋出 ConcurrentModificationException 異常。比如：

ArrayList< String > list = new ArrayList<  >();
list.add("a");
list.add("b");
list.add("c");
Iterator< String > it = list.iterator();
while(it.hasNext()){
    String str = it.next();
    System.out.print(str+" ");
    list.remove(str);//集合遍歷時進行刪除或者新增操作，都會拋出 ConcurrentModificationException 異常
    //list.add(str);
    list.set(0, str);//修改操作不會造成異常
}

解決辦法是不調用 ArrayList.remove() 方法，轉而調用 迭代器的 remove() 方法：

Iterator< String > it = list.iterator();
while(it.hasNext()){
    String str = it.next();
    System.out.print(str+" ");
    //list.remove(str);//集合遍歷時進行刪除或者新增操作，都會拋出 ConcurrentModificationException 異常
    it.remove();
}

注意 ：迭代器只能向后遍歷，不能向前遍歷，能夠刪除元素，但是不能新增元素。

③、迭代器的變種 forEach

ArrayList< String > list = new ArrayList<  >();
list.add("a");
list.add("b");
list.add("c");
for(String str : list){
    System.out.print(str + " ");
}

這種語法可以看成是 JDK 的一種語法糖，通過反編譯 class 文件，我們可以看到生成的 java 文件，其具體實現(xiàn)還是通過調用 Iterator 迭代器進行遍歷的。如下：

ArrayList list = new ArrayList();
        list.add("a");
        list.add("b");
        list.add("c");
        String str;
        for (Iterator iterator1 = list.iterator(); iterator1.hasNext(); System.out.print((new StringBuilder(String.valueOf(str))).append(" ").toString()))
            str = (String)iterator1.next();

④、迭代器 ListIterator 還是先看看具體用法：

ArrayList< String > list = new ArrayList<  >();
list.add("a");
list.add("b");
list.add("c");
ListIterator< String > listIt = list.listIterator();

//向后遍歷
while(listIt.hasNext()){
    System.out.print(listIt.next()+" ");//a b c
}

//向后前遍歷,此時由于上面進行了向后遍歷，游標已經指向了最后一個元素，所以此處向前遍歷能有值
while(listIt.hasPrevious()){
    System.out.print(listIt.previous()+" ");//c b a
}

還能一邊遍歷，一邊進行新增或者刪除操作：

ArrayList< String > list = new ArrayList<  >();
list.add("a");
list.add("b");
list.add("c");
ListIterator< String > listIt = list.listIterator();

//向后遍歷
while(listIt.hasNext()){
    System.out.print(listIt.next()+" ");//a b c
    listIt.add("1");//在每一個元素后面增加一個元素 "1"
}

//向后前遍歷,此時由于上面進行了向后遍歷，游標已經指向了最后一個元素，所以此處向前遍歷能有值
while(listIt.hasPrevious()){
    System.out.print(listIt.previous()+" ");//1 c 1 b 1 a 
}

也就是說相比于 Iterator 迭代器，這里的 ListIterator 多出了能向前迭代，以及能夠新增元素。下面我們看看具體實現(xiàn)：

對于 Iterator 迭代器，我們查看 JDK 源碼，發(fā)現(xiàn)還有 ListIterator 接口繼承了 Iterator:

public interface ListIteratorextends Iterator

該接口有如下方法：

我們看在 ArrayList 類中，有如下方法可以獲得 ListIterator 接口：

public ListIterator< E > listIterator() {
        return new ListItr(0);
    }

這里的 ListItr 也是一個內部類。

//注意 內部類 ListItr 繼承了另一個內部類 Itr
    private class ListItr extends Itr implements ListIterator< E > {
        ListItr(int index) {//構造函數(shù)，進行游標初始化
            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();
            }
        }

        //相比于迭代器 Iterator ，這里多了一個新增操作
        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();
            }
        }
    }

9、SubList

在 ArrayList 中有這樣一個方法：

public List< E > subList(int fromIndex, int toIndex) {
         subListRangeCheck(fromIndex, toIndex, size);
         return new SubList(this, 0, fromIndex, toIndex);
     }

作用是返回從 fromIndex(包括) 開始的下標，到 toIndex(不包括) 結束的下標之間的元素視圖。如下：

ArrayList< String > list = new ArrayList<  >();
list.add("a");
list.add("b");
list.add("c");

List< String > subList = list.subList(0, 1);
for(String str : subList){
    System.out.print(str + " ");//a
}

這里出現(xiàn)了 SubList 類，這也是 ArrayList 中的一個內部類。

注意：返回的是原集合的視圖，也就是說，如果對 subList 出來的集合進行修改或新增操作，那么原始集合也會發(fā)生同樣的操作。

ArrayList< String > list = new ArrayList<  >();
list.add("a");
list.add("b");
list.add("c");

List< String > subList = list.subList(0, 1);
for(String str : subList){
    System.out.print(str + " ");//a
}
subList.add("d");
System.out.println(subList.size());//2
System.out.println(list.size());//4,原始集合長度也增加了

想要獨立出來一個集合，解決辦法如下：

ListsubList = new ArrayList<>(list.subList(0, 1));

10、size()

public int size() {
        return size;
    }

注意：返回集合的長度，而不是數(shù)組的長度，這里的 size 就是定義的全局變量。

11、isEmpty()

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

返回 size == 0 的結果。

12、trimToSize()

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

該方法用于回收多余的內存。也就是說一旦我們確定集合不在添加多余的元素之后，調用 trimToSize() 方法會將實現(xiàn)集合的數(shù)組大小剛好調整為集合元素的大小。

注意 ：該方法會花時間來復制數(shù)組元素，所以應該在確定不會添加元素之后在調用。

13、小結

好了，這就是JDK中java.util.ArrayList 類的介紹。