概要

• 類繼承關(guān)系

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.ArrayList<E>

• 定義

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

實現(xiàn)

• 創(chuàng)建

public ArrayList() {    
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

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);    
  }
}

由代碼可知，ArrayList采用數(shù)組方式存放對象。無參構(gòu)造器創(chuàng)建一個空Object數(shù)組

private static final Object[] EMPTY_ELEMENTDATA = {};

• 插入：add(E)
  add方法其實就是給數(shù)組中某元素賦值為傳入的對象，但add時有個明顯的問題是，數(shù)組滿了怎么辦？我們接著往下看。

public boolean add(E e) {    
  ensureCapacityInternal(size + 1);  // Increments modCount!!    
  elementData[size++] = e;    
  return true;
}

ensureCapacityInternal函數(shù)的作用是保證數(shù)組大小是夠用的。

private void ensureCapacityInternal(int minCapacity) {    
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    
  }    
  ensureExplicitCapacity(minCapacity);
}

參數(shù)傳入數(shù)組的size + 1， 如果數(shù)組為空數(shù)組，則將minCapacity設(shè)為10或者minCapacity中的大值

private static final int DEFAULT_CAPACITY = 10;

函數(shù)ensureExplicitCapacity用來產(chǎn)生明確的容量, 如果minCapacity大于數(shù)組大小，則進行擴容。

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

  // overflow-conscious code    
  if (minCapacity - elementData.length > 0)        
    grow(minCapacity);
}

擴容代碼如下：

private void grow(int minCapacity) {    
  // overflow-conscious code    
  int oldCapacity = elementData.length;    
  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);
}

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

首先產(chǎn)生新的數(shù)組大小為原來的1.5倍，若新的容量仍小于minCapacity，則minCapacity為新的容量，得出新的容量值后，調(diào)用Arrays.copyOf來生成新的數(shù)組對象，如想調(diào)整容量的生長策略，可繼承ArrayList, 并覆寫ensureCapacity方法。

在Collection中增加對象時，ArrayList還提供add(int, E)這樣的方法，允許將元素直接插入到int位置。它要將當(dāng)前數(shù)組的對象進行一次復(fù)制，即將目前index及其后的數(shù)據(jù)都往后挪一位，該方式要多一次復(fù)制數(shù)組的代價。

public void add(int index, E element) {    
  rangeCheckForAdd(index);    
  ensureCapacityInternal(size + 1);  // Increments modCount!!    
  System.arraycopy(elementData, index, elementData, index + 1, size - index);    
  elementData[index] = element;    size++;
}

• 刪除：remove(E)
  先上代碼：

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;
}

如果要刪除的對象為null, 循環(huán)遍歷整個數(shù)組，找到為null值的元素，調(diào)用fastRemove刪除相應(yīng)位置的對象。

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
}

又代碼可知，fastRemove是一次數(shù)組的復(fù)制，將index后的對象統(tǒng)一向前移動一位，將最后一位設(shè)為null, 釋放此對象的引用。

若對象非null, 則通過equals來進行比較，同樣通過fastRemove來刪除元素。

• 獲取單個對象：get(int)

public E get(int index) {    
  rangeCheck(index);    
  return elementData(index);
}

先做數(shù)組范圍檢查，在返回對象。

• 遍歷對象：iterator

public Iterator<E> iterator() {    return new Itr();}

每次調(diào)用iterator方法時，都會new一個Itr的實例。
當(dāng)調(diào)用此實例的hasNext方法時，比較當(dāng)前指向的數(shù)組的位置是否和數(shù)組中已有元素大小相等，如相等返回false，否則返回true。
、、、
public boolean hasNext() {
return cursor != size; // cursor標識下一個返回元素的位置
}
、、、

當(dāng)調(diào)用實例的next方法時，首先比較在創(chuàng)建此Iterator時獲取的modCount與當(dāng)前的modCount，如果不等，則說明在獲取next元素時，發(fā)生了對集合大小產(chǎn)生影響（新增、刪除）的動作。當(dāng)發(fā)生這種情況時，則拋出ConcurrentModificationException。

• 判斷對象時候存在：contains(E)

public boolean contains(Object o) {    return indexOf(o) >= 0;}

public int indexOf(Object o) {    
  if (o == null) {        
    for (int i = 0; i < size; i++)            
      if (elementData[i]==null)                
        return i;    
  } else {        
    for (int i = 0; i < size; i++)            
      if (o.equals(elementData[i]))                
        return i;    
  }    
  return -1;
}

如果E為null,則直接判斷已有元素是否為null, 否則通過判斷E.equals和元素是否相等。

• transient

transient Object[] elementData; // non-private to simplify nested class access

聲明為transient后，這個字段不會被序列化。

• SuppressWarnings

@SuppressWarnings("unchecked")

告訴編譯器，對特定類型的warning保持沉默。

注：

1. ArrayList基于數(shù)組實現(xiàn)，無容量的限制。
2. ArrayList插入元素時可能要擴容，刪除時并不會減小數(shù)組的容量。
3. 若希望縮小數(shù)組容量，可以調(diào)用ArrayList的trimToSize()

public void trimToSize() {    
  modCount++;    
    if (size < elementData.length) {        
      elementData = (size == 0)          
        ? EMPTY_ELEMENTDATA          : Arrays.copyOf(elementData, size);    
    }
}

4. ArrayList非線程安全。