Java進階--深入理解ArrayList實現(xiàn)原理

ArrayList簡介

ArrayList就是動態(tài)數(shù)組，用MSDN中的說法，就是Array的復雜版本，它提供了動態(tài)的增加和減少元素，實現(xiàn)了Collection和List接口，可以靈活的設置數(shù)組的大小。要注意的是ArrayList并不是線程安全的，因此一般建議在單線程中使用ArrayList。

ArrayList的繼承關(guān)系

20170519105333354.jpg
public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

由上可知ArrayList繼承AbstractList 并且實現(xiàn)了List和RandomAccess，Cloneable, Serializable接口。

ArrayList的方法使用和源碼解析

①構(gòu)造方法

//1-----------------------
public ArrayList() {
        this(10);
        //調(diào)用ArrayList(10) 默認初始化一個大小為10的object數(shù)組。
    }
    
//2-------------------------
public ArrayList(int initialCapacity) {    
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
         //如果用戶初始化大小小于0拋異常，否則新建一個用戶初始值大小的object數(shù)組。                                      
        this.elementData = new Object[initialCapacity];
    } 
    
//3--------------------------
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // 當c.toArray返回的不是object類型的數(shù)組時，進行下面轉(zhuǎn)化。
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

由上面三種構(gòu)造方法可知，默認情況下使用ArrayList會生成一個大小為10的Object類型的數(shù)組。也可以調(diào)用ArrayList(int initialCapacity) 來初始化Object數(shù)組的大小。并且用戶可以往ArrayList中傳入一個容器只要這個容器是Collection類型的。調(diào)用ArrayList(Collection<? extends E> c)接口的時候會將容器數(shù)組化處理并將這個數(shù)組值賦給Object數(shù)組。

實例：

public static void main(String[] args) {
        ArrayList<Integer> list_2=new ArrayList<Integer>(20);
        //list_2中添加元素
        for(int i=0;i<10;i++)
            list_2.add(i);
            
        ArrayList<Integer> list_3=new ArrayList<Integer>(list_2);
        //輸出list_2中元素
        for(Integer a:list_2)
            System.out.print(a+" ");
        //輸出list_3中元素
        for(Integer a:list_3)
            System.out.print(a+" ");
    }
//輸出
/*
list_2 : 0 1 2 3 4 5 6 7 8 9 
-----------------------
list_3 : 0 1 2 3 4 5 6 7 8 9 
*/

②indexOf(Object o)方法
功能：查找某個元素在ArrayList中第一次出現(xiàn)的位置。

  public int indexOf(Object o) {
  //ArrayList中的元素可以為null，如果為null返回null的下標
        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;
        }
        //如果沒有找到對應的元素返回-1。
        return -1;
    }

對于indexof方法做幾點說明：ArrayList中可以存放null元素，indexof是返回elementData數(shù)組中值相同的首個元素的下標，indexof中比較方法是equals而equals是比較元素的值，因此必須對null單獨查找。如果未找到該元素則返回-1 。


public static void main(String[] args) {
        
        ArrayList<Integer> list=new ArrayList<Integer>();
        
        list.add(1);        
        list.add(2);        
        list.add(null);     
        list.add(2);
        list.add(3);
        
        System.out.println("null: "+list.indexOf(null));
        System.out.println("-------------------------");
        System.out.println("2: "+list.indexOf(2));
        System.out.println("-------------------------");
        System.out.println("4: "+list.indexOf(4));
    }
    //輸出
    /*
    null: 2
    -------------------------
    2: 1
    -------------------------
    4: -1
    */

③lastIndexOf(Object o)方法
功能：查找某個元素在ArrayList中最后出現(xiàn)的位置。

public int lastIndexOf(Object o) {
        if (o == null) {
        //如果o為null從后往前找到第一個為null的下標
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
        //從后往前找到第一個值為o的下標
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

上面代碼做幾點說明：lastIndexOf(Object o)在ArrayList中從后往前找到第一個跟要查找值相同的元素的下標，因為是按值查找所以對于 null 要單獨查找。如果未找到則返回-1；

④get(int index)方法
功能：返回ArrayList中指定下標為index的元素。

public E get(int index) {
 //檢查index的值是否大于ArrayList的大小
        rangeCheck(index);
 //返回index下標的元素       
        return elementData(index);
    }
    
   E elementData(int index) {
        return (E) elementData[index];
    }  
 //這里值檢查index >= size的情況，因為index<0時會自動拋出異常，所以并未檢查index<0的情況。
 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

對上面代碼做幾點說明：上面代碼中只檢查了index>=size的情況，在index<0的情況下也會拋出異常，只是這個異常是由系統(tǒng)拋出的。index>=size要檢查的原因是有可能數(shù)組的大小大于index，然而有效里面的元素<index這時不拋異常就會返回無效值。舉個例子ArrayList的初始化大小為10，現(xiàn)在往里面放5個元素，如果index>=5時，應該要拋出異常，而不是返回 null。因為null 是可以主動放在ArrayList中的。

⑤set(int index, E element)方法
功能：將element放到ArrayList下標為index的位置，如果index<0或index>=size 拋異常，set(int index, E element)只能覆蓋ArrayList中原來的元素，返回值為被覆蓋的元素。

//1
public E set(int index, E element) {
//檢查index是否小于size，如果不是拋異常
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        //覆蓋ArrayList中index上的元素。
        return oldValue;
        //返回被覆蓋的元素。
    }
//2    
 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

⑥add(E e)方法
功能：往ArrayList中添加元素。

//1-----------------------
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 加入元素前檢查數(shù)組的容量是否足夠
        elementData[size++] = e;
        return true;
    }
//2----------------------- 
private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // 如果添加元素后大于當前數(shù)組的長度，則進行擴容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    } 
//3-----------------------  
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //將數(shù)組的長度增加原來數(shù)組的一半。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            //如果擴充一半后仍然不夠，則 newCapacity = minCapacity;minCapacity實際元素的個數(shù)。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            //數(shù)組最大位2^32
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

add方法比較復雜，涉及到擴充數(shù)組容量的問題。其中要弄清楚size和elementData.length的區(qū)別，size指的是數(shù)組中存放元素的個數(shù)，elementData.length表示數(shù)組的長度，當new一個ArrayList系統(tǒng)默認產(chǎn)生一個長度為10的elementData數(shù)組，elementData.length=10，但是由于elementData中還未放任何元素所有size=0。如果加入元素后數(shù)組大小不夠會先進行擴容，每次擴容都將數(shù)組大小增大一半比如數(shù)組大小為10一次擴容后的大小為10+5=10;ArrayList的最大長度為 2^32 .

⑦add(int index, E element)方法
功能：往ArrayList指定index上添加元素，添加元素后ArrayList的大小增1。index及以后的元素都會向后移一位。

//1-------------------------
public void add(int index, E element) {
        rangeCheckForAdd(index);
//檢查index的值是否在0到size之間，可以為size。
        ensureCapacityInternal(size + 1);  // 看elementData的長度是否足夠，不夠擴容
 //將elementData從index開始后面的元素往后移一位。       
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
//2-------------------------
private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 //3-------------------------  
 private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

add(int index, E element)往指定index中加入元素，加入元素之前先檢查數(shù)組的大小，如果小了在原來基礎上增大一半，將ArrayList只能怪index及以后的元素往后移一位，將element放到index位置。

⑧remove(int index)方法
功能：刪除ArrayList指定位置的元素。

public E remove(int index) {
        rangeCheck(index);
//如果index>=size拋出異常
        modCount++;
        E oldValue = elementData(index);
//獲取刪除元素的值
        int numMoved = size - index - 1;
        //將index后面所有的元素往前移一位。
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
//返回要刪除的原數(shù)。
        return oldValue;
    }

⑨remove(Object o)方法
功能：刪除ArrayList中值為o的元素

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;
    }
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容