01.20 專題：ArrayList

1、簡述

ArrayList是java集合框架中比較長見的集合容器。其底層數據結構實現是容量大小動態變化的數組。從系統結構圖中可知，ArrayList實現了List、RandomAccess、Cloneable、Serializable接口，繼承了AbstractList抽象類。實現RandomAccess接口，提升對數據的查詢效率。實現Cloneable接口，覆蓋clone()函數，能被克隆。實現Serializable接口，可以支持序列化傳輸。

ArrayList體系結構圖

2、成員變量

<code>//序列化版本
private static final long serialVersionUID = 8683452581122892189L;
//默認初始容量10
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;/<code>

3、構造函數

<code>//無參構造函數
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//初始化一個容量為initialCapacity個來構造ArrayList
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);
    } 

}
//指定Collection來構造ArrayList
public ArrayList(Collection extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}/<code>

4、Add方法（擴容機制）

<code>//添加元素（每次添加元素前都會判斷容量否需要擴容）
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity); 

}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
/<code>

簡述ArrayList的擴容機制：

數組在添加元素之前，會去判斷數組容量值需不需要擴增。如果容量值不夠，就會在原有容量的基礎之上增加0.5倍的容量值。之後將老的數組複製到新的數組裡面。無參構造創建的ArrayList，容量值默認是10。

5、ArrayList常用核心方法：

<code>//元素個數
public int size() {...}
//集合是否為空
public boolean isEmpty() {...}
//是否包含元素“...”
public boolean contains(Object o) {...}
//返回元素“...”的第一次出現的索引
public int indexOf(Object o) {...}
//返回元素“...”的最後一次出現的索引
public int lastIndexOf(Object o) {...}
//根據索引獲取元素
public E get(int index) {...}
//更新元素 

public E set(int index, E element) {...}
//添加元素
public boolean add(E e) {...}
//指定索引處添加元素
public void add(int index, E element) {...}
//添加所有集合元素
public boolean addAll(Collection extends E> c) {...}
//指定索引處添加所有集合元素
public boolean addAll(int index, Collection extends E> c) {...}
//移除指定索引下的元素
public E remove(int index) {...}
//移除“...”元素
public boolean remove(Object o) {...}
//移除集合下的元素
public boolean removeAll(Collection> c) {...}
//轉換為Object類型數組
public Object[] toArray() {...}
//轉換為T類型數組
public  T[] toArray(T[] a) {...}/<code>

6、總結

1.ArrayList數據是有序、和重複、可為Null。

2.非同步線程，線程不安全。

3.底層結構是數組，初始容量是10，每次擴容是增加0.5值。

4.查詢訪問快，新增刪除慢。

閱讀更多 Monykeyup 的文章

關鍵字: 數據結構 長見 集合