ArrayList的使用方法

1.ArrayList的初始空間大小

進入ArrayList源碼中可以看到聲明的初始容量(default capacity)

 /**
  * Default initial capacity.
  */
 private static final int DEFAULT_CAPACITY = 10;

從源碼中我們可以得到ArrayList的初始容量為10

2.ArrayList的add()——>append操作(在最后追加)

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
 public boolean add(E e) {
    // 判斷內部容量，為了確保內部容量足夠存放追加的元素(如果容量足夠則容量不做處理，如果容量不夠則會容量擴增一)
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 將新元素追加到集合中
    elementData[size++] = e;
    return true;
 }
==================================================================================
private void ensureCapacityInternal(int minCapacity) {
    // 此處獲取計算容量
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
=================================================================================
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 判斷增加元素當前時間ArrayList中元素是否為初始空值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果增加元素是首次增加則直接返回初始容量
        // Math.max()是獲得兩個數中的最大數
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 如果當前集合中有元素，則直接返回要插入元素的索引(size+1)
    // e.g.
    // 當前集合中元素有3個，那么此時size=3，此時返回的值為3+1=4
    return minCapacity;
}
====================================================================================
private void ensureExplicitCapacity(int minCapacity) {
    // 如果當前集合容量足夠，則不需要進行擴容，只需要修改該數值
    // 這個數值統計了當前集合的結構被修改的次數，主要用于迭代器
    modCount++;

    // overflow-conscious code
    // 如果當前元素插入的位置角標數大于當前集合的長度，則需要進行集合的擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
===================================================================================
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * minCapacity:所需的最小容量值
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新值 = 當前集合長度 + 當前集合長度/2
    // e.g.
    // 當前集合長度為10，那么擴容后的長度就是：10 + 10 / 2 = 15
    // 15 + 15 / 2 = 15 + 7 = 21
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果擴容后的長度還不夠最小需求容量的話直接用最小容量需求值為擴容后的值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果后的值大于Integer最大值-8的話，那么用巨大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 其實就是重新new 一個ArrayList，容量為擴容后的容量，將原有元素拷貝到新集合的操作
    elementData = Arrays.copyOf(elementData, newCapacity);
}
==================================================================================
/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
==================================================================================
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Java中位運算符補充

經常在一些算法中看到 num >>> 1的寫法，num >>> 1，相當于num除以2，為什么不直接寫num除以2呢？因為計算機中的數據是以二進制的形式存儲的，數學運算的加減乘除底層也是二進制移位實現的，直接在二進制上移位，顯然要比數學運算來的更直接。
來看一下Java中的移位運算符，有三種:

<< : 左移運算符，num << 1，相當于num乘以2
>> : 右移運算符，num >> 1，相當于num除以2
>>> : 無符號右移運算符，num >>> 1，相當于num除以2，忽略符號位，空位都以0補齊
示例：
    int num = 8;
    int num1 = num << 1;  //num1 = 16
    int num2 = num >> 1 ;  //num2 = 4
    int num3 = num >>> 1;  //num3 = 4
注意：無符號右移運算符忽略了最高位的符號位，0補最高位，并且無符號右移運算符 >>> 只對32位和64位的數值有意義。Java中只有這三種位移，沒有向左的無符號位移。
    int num = -8;
    int num1 = num << 1;  //num1 = -16
    int num2 = num >> 1 ;  //num2 = -4
    int num3 = num >>> 1;  //num3 = 21 4748 3644
為什么 num3 是 21 4748 3644 這么個數？因為數值在計算機中是以補碼的形式的存儲的，-8的補碼是 [11111111 11111111 11111111 11111000]，右移一位則變成了 [01111111 11111111 11111111 11111100]，最高位的1表示負數，0表示正數，>>> 時0補最高位的符號位，[01111111 11111111 11111111 11111100] 的十進制就是21 4748 3644。在正數位移的時候，>> 和 >>> 是一樣的，在負數位移的時候就不一樣了。

3.ArrayList的add()——>增加到指定位置

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 進行范圍檢查：插入的元素位置是否超出當前容器容量邊界
    // eg:當前集合容量為10，元素個數也是10，那么size=10，此時index只能是0-9，容器自動擴容會在下一步完成
    rangeCheckForAdd(index);
    // 算法通追加元素一致
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 將要插入位置后面的size-index個元素后移
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 將元素插入指定位置
    elementData[index] = element;
    size++;
}
===================================================================================
/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4.ArrayList的remove()——>指定角標

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
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);
    // 讓GC清除
    elementData[--size] = null; // clear to let GC do its work
    // 返回被刪除的元素
    return oldValue;
}

5.ArrayList的remove()——>指定元素

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns <tt>true</tt> if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            // 如果某個元素因為為null
            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;
}
===================================================================
/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
// 該方法不會進行邊界檢查
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; // clear to let GC do its work
}

6.ArrayList的clear()

可見該方法是將所有元素置為null

/**
 * Removes all of the elements from this list.  The list will
 * be empty after this call returns.
 */
public void clear() {
    modCount++;

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

    size = 0;
}