之前已經(jīng)分析了HashMap的源碼，知道HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹。相對于HashMap，ArrayList的內(nèi)部實(shí)現(xiàn)方法和操作都簡單的多。之前在看《Thinking In Java》的時(shí)候已經(jīng)知道：ArrayList內(nèi)部是用數(shù)組實(shí)現(xiàn)的，所以對于隨機(jī)查詢，效率會很高。但是對于在數(shù)組中間插入數(shù)據(jù)，和刪除中間元素時(shí)，會導(dǎo)致后續(xù)元素的移動(dòng)。

jkd源碼版本為1.8.0_05

類的結(jié)構(gòu)

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

繼承了AbstractList抽象類，其中實(shí)現(xiàn)了List需要的絕大多數(shù)公共方法。實(shí)現(xiàn)List, Cloneable, Serializable接口。還有一個(gè)RandomAccess接口，這是一個(gè)空的接口，代表這個(gè)類支持快速隨機(jī)訪問。

構(gòu)造函數(shù)

//使用一個(gè)指定的初始化容量構(gòu)造ArrayList
public ArrayList(int initialCapacity) {
  super();
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  this.elementData = new Object[initialCapacity];
}
//初始化一個(gè)空數(shù)組
public ArrayList() {
  super();
  this.elementData = EMPTY_ELEMENTDATA;
}
//接受一個(gè)Collection類型的參數(shù)，轉(zhuǎn)化為數(shù)組之后進(jìn)行復(fù)制
public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();
  size = elementData.length;
  // c.toArray might (incorrectly) not return Object[] (see 6260652)
  if (elementData.getClass() != Object[].class)
    elementData = Arrays.copyOf(elementData, size, Object[].class);
}

成員字段

//初始化的默認(rèn)容量
private static final int DEFAULT_CAPACITY = 10;
//共享空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//ArrayList中的元素?cái)?shù)組
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList中含有元素的個(gè)數(shù)
private int size;

這里對“共享空數(shù)組” Shared empty array instance 不是很理解。

關(guān)鍵方法

添加—add()

/**
 * 將特定的元素添加到數(shù)組的尾部
 */
public boolean add(E e) {
  //檢查空間大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}

private void ensureCapacityInternal(int minCapacity) {
  //如果當(dāng)前的數(shù)據(jù)元素是空數(shù)組，那么需要的容量和默認(rèn)容量的最大值作為需要的容量
  if (elementData == EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  //檢查是否需要擴(kuò)容
  ensureExplicitCapacity(minCapacity);
}

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

  // overflow-conscious code 如果需要的容量大于當(dāng)前數(shù)組的長度，進(jìn)行一次擴(kuò)容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  //擴(kuò)容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:
  //然后將數(shù)組元素放到新的數(shù)組中
  elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 *插入一個(gè)指定的元素到特定的位置。將右邊的所有元素向右移動(dòng)一位
 */
public void add(int index, E element) {
  //針對與添加元素，檢查是否越界。
  rangeCheckForAdd(index);
  //檢查是否需要擴(kuò)容
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //將index---size的元素，拷貝到index+1---size+1的位置上
  System.arraycopy(elementData, index, elementData, index + 1,size - index);
  //插入數(shù)據(jù)
  elementData[index] = element;
  size++;
}
private void rangeCheckForAdd(int index) {
  if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

刪除—remove()

//刪除指定位置的元素，將右邊的所有元素左移一位。
public E remove(int index) {
  //index不能超過size
  rangeCheck(index);

  modCount++;
  E oldValue = elementData(index);
  //需要移動(dòng)的元素個(gè)數(shù)
  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,numMoved);
  //復(fù)制之后將size--，然后把最后一位賦值null
  elementData[--size] = null; // clear to let GC do its work

  return oldValue;
}

private void rangeCheck(int index) {
  if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}


public boolean remove(Object o) {
  if (o == null) {
    //遍歷，刪除第一個(gè)為null的元素
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true;
      }
  } else {
    //遍歷，刪除第一個(gè)和o相等的元素，用equals來判斷
    for (int index = 0; index < size; index++)
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
}

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
}