關注點 | 結論
---|---
ArrayList是否允許空 | 允許
ArrayList是否允許重復數據 | 允許
ArrayList是否有序 | 有序
ArrayList是否線程安全 | 非線程安全
#### 1. 繼承的父類和實現的接口
```java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
```
> ArrayList 繼承了 AbstractList 類，此類提供了 List 接口的骨干實現，繼承此類的子類適合用于“隨機訪問”數據存儲（如數組），Vector 也是此類的子類。
> 與 AbstractList 類對應的類是 AbstractSequentialList 類，繼承該類的子類適合用于“連續訪問”數據存儲（如鏈接列表），代表的子類如 LinkedList 。
> ArrayList 實現了 List 接口，List 接口通常表示一個列表（數組、隊列、鏈表、棧等），其中的元素可以重復，代表的實現類有 ArrayList、LinkedList、Stack、Vector。
> ArrayList 實現了 RandomAccess 接口，該接口為標記接口，用來表明其支持快速隨機訪問。
> ArrayList 實現了 Cloneable 接口，以指示 Object.clone() 方法可以合法地對該類實例進行按字段復制。
> ArrayList 實現了 Serializable 接口，因此它支持序列化，能夠通過序列化傳輸。
#### 2. 屬性
```java
/**
* 序列版本號
*/
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默認容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 無參的空數組常量
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 有參的空數組
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存放元素的數組，從這可以發現ArrayList的底層實現就是一個Object數組
*/
transient Object[] elementData;
/**
* 當前的實際元素個數
*/
private int size;
```
#### 3. 構造函數
```java
//用初始容量作為參數的構造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//初始容量大于0，實例化數組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//初始容量等于0，賦予空數組
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//無參的構造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```
> 從構造方法中我們可以看見，默認情況下，elementData是一個大小為0的空數組，當我們指定了初始大小的時候，elementData的初始大小就變成了我們所指定的初始大小了。
#### 4. get，set方法
```java
//返回指定索引的值
public E get(int index) {
//檢查索引值是否越界
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
//將制定索引上的值替換為新值，并返回舊值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
```
> 因為ArrayList是采用數組結構來存儲的，所以它的get方法非常簡單，先是判斷一下有沒有越界，之后就可以直接通過數組下標來獲取元素了，所以get的時間復雜度是O(1)。
> set方法的作用是把下標為index的元素替換成element，跟get非常類似，所以就不在贅述了，時間復雜度度為O(1)。
#### 5. add
```java
//將指定的元素添加到列表的尾部
public boolean add(E e) {
//動態數組
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
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;
//默認是擴大為原來的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//1.5倍還是不夠的話，直接用傳進來的minCapacity作為容量值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//自己傳進來的值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;
}
//將元素添加到指定位置
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy(被復制的數組，從第幾個元素開始復制，要復制到的數組，從第幾個元素開始粘貼，一共需要復制的元素個數)
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
```
> ArrayList的add方法也很好理解，在插入元素之前，它會先檢查是否需要擴容，然后再把元素添加到數組中最后一個元素的后面。在ensureCapacityInternal方法中，我們可以看見，如果當elementData為空數組時，它會使用默認的大小去擴容。所以說，通過無參構造方法來創建ArrayList時，它的大小其實是為0的，只有在使用到的時候，才會通過grow方法去創建一個大小為10的數組。
> 第一個add方法的復雜度為O(1)，雖然有時候會涉及到擴容的操作，但是擴容的次數是非常少的，所以這一部分的時間可以忽略不計。如果使用的是帶指定下標的add方法，則復雜度為O(n)，因為涉及到對數組中元素的移動，這一操作是非常耗時的
> grow方法是在數組進行擴容的時候用到的，從中我們可以看見，ArrayList每次擴容都是擴1.5倍，然后調用Arrays類的copyOf方法，把元素重新拷貝到一個新的數組中去。
#### 6. remove
```java
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//arraycopy(被復制的數組，從第幾個元素開始復制，要復制到的數組，從第幾個元素開始粘貼，一共需要復制的元素個數)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
```
> remove方法與add帶指定下標的方法非常類似，也是調用系統的arraycopy方法來移動元素，時間復雜度為O(n)。
#### 7. size(),isEmpty()
```java
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
```
> size方法非常簡單，它是直接返回size的值，也就是返回數組中元素的個數，時間復雜度為O(1)。這里要注意一下，返回的并不是數組的實際大小。
#### 8.indexOf()和lastIndexOf()
```java
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;
}
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
```
> indexOf方法的作用是返回第一個等于給定元素的值的下標。它是通過遍歷比較數組中每個元素的值來查找的，所以它的時間復雜度是O(n)。
> lastIndexOf的原理跟indexOf一樣，而它僅僅是從后往前找起罷了。
#### 9. removeRange()
```java
//刪除fromIndex到toIndex之間的全部元素
protected void removeRange(int fromIndex, int toIndex)
{
modCount++;
//numMoved為刪除索引后面的元素個數
int numMoved = size - toIndex;
//將刪除索引后面的元素復制到以fromIndex為起始位置的存儲空間中去
System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);
int newSize = size - (toIndex-fromIndex);
//將ArrayList后面(toIndex-fromIndex)個元素置為null
for (int i = newSize; i < size; i++)
{
elementData[i] = null;
}
size = newSize;
}
```
#### 10. Vector
> vector因為很多方法都跟ArrayList一樣，只是多加了個synchronized來保證線程安全罷了。如果照著ArrayList的方式再將一次就顯得沒意思了，所以只把Vector與ArrayList的不同點提一下就可以了。
Vector比ArrayList多了一個屬性：
> protected int capacityIncrement;
這個屬性是在擴容的時候用到的，它表示每次擴容只擴capacityIncrement個空間就足夠了。該屬性可以通過構造方法給它賦值。先來看一下構造方法：
```java
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
```
從構造方法中，我們可以看出Vector的默認大小也是10，而且它在初始化的時候就已經創建了數組了，這點跟ArrayList不一樣。再來看一下grow方法：
```java
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
```
從grow方法中我們可以發現，newCapacity默認情況下是兩倍的oldCapacity，而當指定了capacityIncrement的值之后，newCapacity變成了oldCapacity+capacityIncrement。
#### 10. 總結
> 注意擴充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1個，也可能是一組）時，都要調用該方法來確保足夠的容量。當容量不足以容納當前的元素個數時，就設置新的容量為舊的容量的1.5倍，如果設置后的新容量還不夠，則直接新容量設置為傳入的參數（也就是所需的容量），而后用Arrays.copyof()方法將元素拷貝到新的數組（詳見下面的第3點）。從中可以看出，當容量不夠時，每次增加元素，都要將原來的元素拷貝到一個新的數組中，非常之耗時，也因此建議在事先能確定元素數量的情況下，才使用ArrayList，否則建議使用LinkedList。
> 1、ArrayList創建時的大小為0；當加入第一個元素時，進行第一次擴容時，默認容量大小為10。
> 2、ArrayList每次擴容都以當前數組大小的1.5倍去擴容。
> 3、Vector創建時的默認大小為10。
> 4、Vector每次擴容都以當前數組大小的2倍去擴容。當指定了capacityIncrement之后，每次擴容僅在原先基礎上增加capacityIncrement個單位空間。
> 5、ArrayList和Vector的add、get、size方法的復雜度都為O(1)，remove方法的復雜度為O(n)。
> 6、ArrayList是非線程安全的，Vector是線程安全的。
> 7. ArrayList不是線程同步的，在多線程下可以考慮使用 Collections.synchronizedList 方法將該列表“包裝”起來。這最好在創建時完成，以防止意外對列表進行不同步的訪問：代碼如下：
```java
List list = Collections.synchronizedList(new ArrayList(...));
```