基本概念

數(shù)組是一種線性表數(shù)據(jù)結構。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)。
隨機訪問時間復雜度O(1),添加和刪除時間復雜度O(n)。
添加和刪除最好的情況是添加和刪除最后一位，時間復雜度O(1)，最壞情況，移動整個數(shù)組，時間復雜度O(n)。

插入和刪除改進思想

插入

如果數(shù)組中的數(shù)據(jù)是有序的，我們在某個位置插入一個新的元素時，就必須按照剛才的方法搬移k之后的數(shù)據(jù)。
但是，如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當作一個存儲數(shù)據(jù)的集合。
假設數(shù)組 a[10]中存儲了如下 5 個元素：a，b，c，d，e。
我們現(xiàn)在需要將元素 x 插入到第 3 個位置。我們只需要將 c 放入到 a[5]，將 a[2]賦值為 x 即可。最后，數(shù)組中的元素如下： a，b，x，d，e，c。
這種插入方式會將O（n）降到O（1）

刪除

復雜度與插入完全一致
數(shù)組 a[10]中存儲了 8 個元素：a，b，c，d，e，f，g，h?，F(xiàn)在，我們要依次刪除 a，b，c 三個元素。
我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除。當數(shù)組沒有更多空間存儲數(shù)據(jù)時，我們再觸發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導致的數(shù)據(jù)搬移。

內(nèi)存尋址公式

對于一維長度為k的數(shù)組，a[k]的地址為：

a[k]_address = base_address + k * type_size

對于 m * n 的數(shù)組，a [ i ][ j ] (i < m,j < n)的地址為：

address = base_address + ( i * n + j) * type_size

ArrayList源碼

添加

添加元素到尾部

public boolean add(E e) {
    // 數(shù)組大小是否足夠，不夠就擴容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 直接賦值
    elementData[size++] = e;
    return true;
}

擴容代碼

1. 初始化數(shù)組大小時，是否有給定初始值，以給定的大小為準，沒有給默認擴容到10.
2. 期望的最小容量大于當前數(shù)組的長度，那么就擴容。
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 擴容后的數(shù)組容量是原先的1.5倍，擴大了1/2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果擴容后的容量依然小于期望的最小容量，那么擴容后的值就等于期望值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果擴容后的值 > jvm 所能分配的數(shù)組的最大值，那么就用 Integer 的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
   
   // 將原先數(shù)組的值拷貝到新數(shù)組
    elementData = Arrays.copyOf(elementData, newCapacity);
}

在指定位置添加元素

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    /**
     * @param src     被拷貝的數(shù)組
     * @param srcPos  從數(shù)組那里開始
     * @param dest    目標數(shù)組
     * @param destPos 從目標數(shù)組那個索引位置開始拷貝
     * @param length  拷貝的長度 
     * 此方法是沒有返回值的，通過 dest 的引用進行傳值
     */
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}

刪除

給定要刪除的元素的index

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // index之后的全部數(shù)據(jù)往前移一位
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
        // 最后一位置空，方便垃圾回收
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

給定要刪除的元素

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //和上面的remove(int index)處理方式基本一致
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

迭代器

用的三個方法：
hasNext 還有沒有值可以迭代
next 如果有值可以迭代，迭代的值是多少
remove 刪除當前迭代的值

hasNext

public boolean hasNext() {
   //cursor 表示下一個元素的位置，size 表示實際大小，如果兩者相等，說明已經(jīng)沒有元素可以迭代了，如果不等，說明還可以迭代
  return cursor < limit;
}

next

public E next() {
    // 注意這個，由上面源碼可知，修改和刪除都會引起modCount變化
    // 如果在迭代器遍歷的時候?qū)线M行修改就會報錯
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // 本次迭代元素的索引值
    int i = cursor;
    if (i >= limit)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    // 為下一次迭代做準備
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

remove

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();

    try {
        // 通過給定index刪除元素
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        // 防止重復刪除元素
        lastRet = -1;
          // 刪除元素時 modCount 的值已經(jīng)發(fā)生變化，在此賦值給 expectedModCount
        // 這樣下次迭代時，兩者的值是一致的了
        expectedModCount = modCount;
        limit--;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}