1. 簡(jiǎn)介

List是一種支持插入、刪除、查找，元素可重復(fù)，可為null的數(shù)據(jù)結(jié)構(gòu)，在JDK中有不同的實(shí)現(xiàn)類(lèi)，其中ArrayList基于數(shù)組實(shí)現(xiàn)，支持隨機(jī)訪問(wèn)，非線程安全，插入與刪除時(shí)間復(fù)雜度為O(n)。

2. 實(shí)現(xiàn)

ArrayList內(nèi)部是使用數(shù)組來(lái)實(shí)現(xiàn)的，所以可以做到隨機(jī)訪問(wèn)時(shí)間為O(1)，如果不一開(kāi)始設(shè)置好最終的大小，可能在不斷添加元素的過(guò)程中多次擴(kuò)容而導(dǎo)致效率問(wèn)題。

屬性

//默認(rèn)容量
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};
//數(shù)組最大大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//元素存放的數(shù)組，設(shè)置為transient的目的是序列化對(duì)象時(shí)忽略該數(shù)組，因?yàn)閿?shù)組可能不是存滿(mǎn)的，我們只序列化必要的對(duì)象以節(jié)省空間時(shí)間。
transient Object[] elementData; // non-private to simplify nested class access
//已經(jīng)添加的元素?cái)?shù)量
private int size;

構(gòu)造函數(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);
    }
}

// 如果未給出大小，默認(rèn)大小是數(shù)組大小10，只不過(guò)這個(gè)大小為10的數(shù)組是延遲到添加元素創(chuàng)建的，所以這里
// 一開(kāi)始數(shù)組大小是0。
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

擴(kuò)容函數(shù)

private void ensureCapacityInternal(int minCapacity) {
    // 這里就是默認(rèn)大小數(shù)組延遲創(chuàng)建的開(kāi)始部分了
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}


private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 判斷是否需要擴(kuò)容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新數(shù)組的大小為舊數(shù)組的1.5倍
    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);
}

增刪改查方法

// 獲取指定位置上的元素
public E get(int index) {
        //范圍檢查，index超出范圍拋出異常
        rangeCheck(index);
        return elementData(index);
}

// 修改指定位置上的元素并返回舊元素
public E set(int index, E element) {
    rangeCheck(index);

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

// 添加元素到列表尾部
public boolean add(E e) {
    // 判斷是否需要擴(kuò)容，如需要?jiǎng)t擴(kuò)容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 添加元素到指定索引位置
public void add(int index, E element) {
    // 范圍檢查
    rangeCheckForAdd(index);
    // 判斷是否需要擴(kuò)容，如需要?jiǎng)t擴(kuò)容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 移動(dòng)元素
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
    elementData[index] = element;
    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;
}

// 若存在對(duì)象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;
    }

// 清空所有對(duì)象
public void clear() {
    modCount++;

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

    size = 0;
}

toArray方法

// 復(fù)制出一個(gè)具有原數(shù)組所有元素的新數(shù)組
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

subList方法

創(chuàng)建出一個(gè)子List，對(duì)該List的操作將作用于到原List上

public List<E> subList(int fromIndex, int toIndex) {
    // 檢查索引范圍是否合法
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

sort方法

List接口中存在默認(rèn)的sort方法，只不過(guò)該方法是為L(zhǎng)inkedList非基于數(shù)組實(shí)現(xiàn)的List準(zhǔn)備的，所以ArrayList重寫(xiě)了sort方法，通過(guò)調(diào)用Arrays.sort()方法直接對(duì)數(shù)組進(jìn)行排序效率比默認(rèn)的高。

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

3. 適用場(chǎng)景

• ArrayList內(nèi)部基于數(shù)組實(shí)現(xiàn)，查找效率非常高，但是當(dāng)出現(xiàn)大量的插入或刪除操作，每次都要移動(dòng)大量元素，明顯效率很低。所以ArrayList應(yīng)該適合于那種查找操作多于插入刪除操作的場(chǎng)景。
• ArrayList比LinkedList節(jié)省空間，因?yàn)锳rrayList核心就是一個(gè)存儲(chǔ)該類(lèi)元素的數(shù)組。在64位虛擬機(jī)下，不開(kāi)啟指針壓縮情況下：
  • ArrayList存儲(chǔ)元素消耗的空間為 24字節(jié)（數(shù)組對(duì)象頭）+ 數(shù)組長(zhǎng)度 * 8字節(jié)
  • LinkedList存儲(chǔ)元素消耗的空間為 元素?cái)?shù)量 * 40字節(jié)（結(jié)點(diǎn)對(duì)象頭 + 前后結(jié)點(diǎn)指針 + 元素指針）
  • 總的來(lái)說(shuō)，每存儲(chǔ)一個(gè)元素，ArrayList平均消耗8個(gè)字節(jié)的引用空間，而LinkedList除了消耗8個(gè)字節(jié)的引用空間還要32字節(jié)的空間（結(jié)點(diǎn)對(duì)象頭 + 前后結(jié)點(diǎn)指針）