1. 概述
2. 快速上手
ArrayList支持泛型，創建 ArrayList 的時候可以指定元素的類型：
ArrayList<String> names = new ArrayList<String>();
ArrayList<Student> students = new ArrayList<Student>();ArrayList常用方法：
// JDK 10.0.2
// 追加元素
void add(E e);
// 刪除元素
E remove();
// 是否包含元素
boolean contains(Object o);
// 設置指定索引的值
E set(int index,E element);
// 清空列表
void clear();
// 從前往後查找指定元素的索引，基於equals
int indexOf(Object o);
// 從後往前查找指定元素的索引
int lastIndexOf(Object o);
// 返回列表元素的數量
int size();
// 判斷元素是否為空,size == 0
int isEmpty();
// 返回此對象的迭代器
Interator<E> iterator();
// 將ArrayList轉成數組，返回的是Object的數組
Object[] toArray();
// 將ArrayList轉換成指定類型的數組
<T> T[] toArray(T[] a);
// 將元素添加到指定的索引
void add(int index,E element);
// 刪除指定索引的元素
E remove(int index);
// 截取從 fromIndex(包含) 到 toIndex(不包含) 範圍的元素列表
List<E> subList(int fromIndex, int toIndex);上面的代碼中演示了 ArrayList 比較常用的 API，接下來我們可以看一個示例：
ArrayList<String> names = new ArrayList<String>();
names.add("James");
names.add("Shaw");
names.add(1,"Rod");
for(int i = 0; i < names.size(); i++) {
System.out.println(names.get(i));
}
names.contains("shaw");
names.isEmpty();
names.size();
Object[] obj = names.toArray();
String[] strArr = name.toArray(new String());
List<String> nameList = names.subList(1,names.size())3. 基本原理
3.1 屬性
Object[] elementData
private int size;
protected transient int modCount = 0;ArrayList內部有一個elementData，作為數據的容器，接下來就是size屬性它記錄了當前實際保存數據的數量，最後就是modCount它記錄了 elementData 內部結構修改的次數（增加，修改，刪除）等。
3.2 add方法
我們可以看下add和remove方法的主要實現：
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}add方法首先對modCount一次自增操作- 接着
add方法調用了重載的add(E e, Object[] elementData, int s)方法，傳入了 需要添加的元素、保存元素的數組以及 當前保存的元素的數量 - 最後返回
true
我們可以追蹤一下 add(E e, Object[] elementData, int s) ：
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}它首先判斷了傳入的參數size和保存元素的數組elementData的length屬性是否相等，如果不相等它會直接將需要添加的元素放到elementData的size位置，然後對size做一次自增操作；如果相等會調用grow()方法，將擴容後的數組賦值給elementData，我們可以來看一下grow()方法的實現：
private Object[] grow() {
return grow(size + 1);
}這個方法很簡單，它調用了grow(int minCapacity)方法返回了擴容後的數組：
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}它首先調用了Arrays.copyOf方法，然後將elementData以及newCapacity(int minCapacity)方法返回的參數作為參數傳遞給了Arrays.copyOf，我們可以來看一下newCapacity(int minCapacity)方法的代碼：
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 1.5 倍擴容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴容後容量小於參數需要的最小容量
if (newCapacity - minCapacity <= 0) {
// 如果是第一次添加
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 返回 Math.max(DEFAULT_CAPACITY,minCapacity)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 返回 newCaiacity
return minCapacity;
}
// 否則判斷是否超過了限制，如果沒有的話返回 newCapacity
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}3.3 remove
我們接下來看remove方法：
public E remove(int index) {
// 索引檢查
Objects.checkIndex(index, size);
// 取出所有元素
final Object[] es = elementData;
// 獲取即將刪除的元素
E oldValue = (E) es[index];
// 刪除方法
fastRemove(es, index);
// 返回
return oldValue;
}它首先對參數index進行了一個校驗由於方法實現比較簡單，所以不再過多闡述，我們主要來看一下fastRemove(Object[] es, int i)方法實現：
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
// 如果size - 1 > i(判斷是不是最後一個元素)，進行移為刪除
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
// 末尾刪除，直接賦值為null
es[size = newSize] = null;
}它首先對modCount進行了自增操作，緊接着判斷刪除的是不是末尾刪除，如果不是的會話會調用System.arrayCopy(Object src, int srcPos,Object dest, int destPos,int length)對元素進行移位。es[size=newSize]=null這行代碼對size進行減1，然後將最後一個元素賦值為null。設置為null之後不再引用原對象，如果對象不再被其他對象引用，那麼就可以被垃圾回收。
4. 迭代
剛才我們大概的講述了一下ArrayList的常用 API以及基本原理，接下來我們來看一下 ArrayList 的迭代。我們來一個簡單的例子，循環 ArrayList 中的每一個元素，ArrayList支持foreach語法：
ArrayList<String> names = new ArrayList<String>();
names.add("Shaw");
names.add("James");
names.add("Rod");
for(String name : names) {
System.out.println(name);
}當然，ArrayList也支持通過索引的方式訪問：
for(int i = 0; i < names.size(); i++) {
System.out.println(names.get(i));
}看上去foreach的語法更加的簡潔，而且也適用與其他容器，更加的通用。這種foreach語法的實現是什麼樣子的呢？其實，編譯之後，它會轉換成類似這樣的代碼：
Iterator<String> iterator = names.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}4.1 Iterable
要了解foreach背後的原理之前，我們需要先了解Iterable接口，ArrayList實現了Iterable接口，它的字面意思就是表示可迭代，它的定義如下：
public interface Iterable<T> {
Iterator<T> iterator();
}它的定義很簡單，就是要求實現iterator方法，返回一個Iterator迭代器接口對象，Iterator接口定義如下：
public interface Iterator<E> {
boolean hasNext();
E next();
void remove()；
}hasNext判斷是否是否還有元素可以訪問next返回迭代的下一個元素remove刪除最後返回的元素
只要對象實現了iterator接口就可以使用foreach語法，編譯器會自動調用iterator和iterable接口的方法。可能對iterable和iterator這兩個接口有點繞，我們可以來看下它們的關係：
Iterable表示對象可迭代，iterator方法要求返回一個Iterator對象，實際通過Iterator接口的方法進行遍歷- 如果對象實現了
Iterable接口，就可以使用foreach語法 - 類可以不實現
Iterable接口，也可以創建Iterator對象
4.2 ListIterable
除了iterator，ArrayList還實現了List接口的listIterator方法：
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);ListIterator接口繼承了Iterator接口，增加了一些方法，如向前遍歷、添加元素、修改元素、返回索引位置等，方法定義如下：
void add(E e);
int nextIndex();
E previous();
int previousIndex();
void set(E e);listIterator方法返回的迭代器從0開始，而listIterator(int index)返回的迭代器從指定索引index開始。比如，從末尾向前遍歷，代碼為：
ListIterator<String> listIt = names.listIterator(names.size());
while(listIt.hashPrevios) {
System.out.println(listIt.prevsious());
}4.3 迭代器的坑
關於迭代器有一種常見的失誤操作，就是在迭代的中間調用容器的刪除方法，比如，要刪除 ArrayList 中所有小於100的數，直覺上，代碼可以這樣寫：
public void remove(ArrayList<Integer> list) {
for(Integer element : list) {
if(element < 100){
element.remove();
}
}
}但是在運行時會拋出異常：java.util.ConcurrentModificationException發生了併發修改異常，這是為什麼呢？因為迭代器內部會維護一些索引位置相關的數據，要求在迭代的過程中，容器不能發生結構性變化，否則索引位置就失效了。所謂結構性變化就是添加、刪除、插入元素，只是修改元素不會發生結構性變化。
如何避免發生異常呢？可以使用迭代器的remove方法，如下所示：
public void remove(ArrayList<Integer> list) {
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
if(iterator.next() < 100) {
iterator.remove();
}
}
}迭代器是如何知道發生了結構性變化，並拋出異常？它自己的remove方法為何又可以使用？我們可以簡單來了解一下迭代器的原理。
4.4 迭代實現的原理
我們可以來看一下ArrayList中iterator方法的實現，代碼為：
public Iterator<E> iterator() {
return new Itr();
}它返回了內部類Itr的對象，Itr實現了Iterator接口，聲明為：
private class Itr implements Iterator<E> {}它有三個實例變量，為：
// 下一個要返回的元素的索引
int cursor; // index of next element to return
// 返回的最後一個元素的索引，如果沒有，則為-1
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;cursor表示下一個要返回的位置，lastRet表示最後一個返回的索引位置，expectedModCount表示期望修改的次數，初始化為外部類當前修改次數modCount，回顧一下；成員內部類可以訪問外部類的實例變量，每次發生結構性變化的時候modCount都會自增，而每次迭代器操作的時候都會檢查expectedModCount是否與modCount相等，這樣就能檢測出結構性變化。
我們可以具體的來一下，它是如何實現Iterator接口中的每個方法的，先看hasNext()，代碼為：
public boolean hasNext() {
return cursor != size;
}代碼很簡單，當前cursor指向元素的索引不等於size則表示還有下一個元素。我們再來看next方法：
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}它首先調用了checkForComodification()方法，檢查ArrayList是否發生了結構性變化，如果發生了結構性變化則拋出ConcurretModificationException，方法定義如下：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}如果沒有發生變化，就更新cursor和lastRet的值使其保持語義，然後返回對應的元素。最後我們來看一下remove方法的實現：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}它調用了ArrayList的remove方法，有同時更新了cursor、lastRet、expectedModCount的值，所以它可以正確的刪除。不過，需要注意的是，調用remove方法前必須先調用next，比如，通過迭代器刪除所有元素，直覺上，可以這麼寫：
public static void removeAll(ArrayList<Integer> list) {
Iterator<Integer> it = list.iterator();
while(it.hasNext()) {
it.remove();
}
}實際運行，會拋出java.lang.IllegalStateException，正確寫法是：
public static void removeAll(ArrayList<Integer> list) {
Iterator<Integer> it = list.iterator();
while(it.hasNext()) {
it.next();
it.remove();
}
}調用next()方法是為了更新內部屬性，保持語義，否則的話lastRet的值就是-1就會拋出java.lang.IllegalStateException異常。
當然咯，要刪除所有元素，ArrayList有現成的方法clear()。
listIterator的實現使用了另一個內部類ListItr，它繼承自Itr，基本思路類似，不在闡述。
4.5 迭代器的好處
- 通用，適用於各種容器類，提供一致性的方式訪問
- 關注點分離，不需要關注數據的組織方式，將數據的實際組織方式和數據的迭代編譯方式相分離，是一種常見的設計模式
- 從封裝的角度來説，迭代器封裝了數組組織方式的迭代操作，提供了簡單和一致的接口
5. Array List實現的接口
Java的各種容器類都有一個共性操作，這些共性以接口的方式體現，剛才介紹的Iterator接口就是，此外，ArrayList還實現了主要三個接口：Collection、List、RandomAccess，我們逐個介紹。
5.1 Collection
Collection表示一個數據集合，數據間沒有位置或順序的概念，定義為：
public interface Collection<E> extends Iterable<E> {
// 返回這個集合的元素數量
int size();
// 這個集合是否包含元素
boolean isEmpty();
// true: 這個集合包含指定的元素,false 反之
boolean contains(Object o);
// 返回此集合中元素的迭代器
Iterator<E> iterator();
// 返回包含此集合所有元素的數組
Object[] toArray();
// 返回包含此集合中所有元素指定類型的數組
<T> T[] toArray(T[] a);
// 添加到末尾
boolean add(E e);
// 刪除指定元素
boolean remove(Object o);
// 是否包含指定元素
boolean containsAll(Collection<?> c);
// 添加集合
boolean addAll(Collection<? extends E> c);
// 按集合刪除
boolean removeAll(Collection<?> c);
// 將刪除的條件對外提供
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
// 包含指定元素
boolean retainAll(Collection<?> c);
// 清空集合
void clear();
boolean equals(Object o);
int hashCode();
// 分隔
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
// Stream流
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}retainAll表示只保留參數容器中的元素，其他元素則會刪除。Java 8對Collection添加了幾個默認方法，包括removeIf、stream、splierator等。
抽象類AbstractCollection對一些方法提供了默認實現，實現的方式是通過迭代器方法逐個操作。我們可以來看一下這幾個方法：
public boolean isEmpty() {
return size() == 0;
}
public boolean contains(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}
public Object[] toArray() {
// Estimate size of array; be prepared to see more or fewer elements
Object[] r = new Object[size()];
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) // fewer elements than expected
return Arrays.copyOf(r, i);
r[i] = it.next();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
public boolean remove(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext()) {
if (it.next()==null) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (o.equals(it.next())) {
it.remove();
return true;
}
}
}
return false;
}
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}5.2 List
List表示有序可重複支持按索引訪問的集合，它繼承了Collection，增加了以下方法：
boolean addAll(int index, Collection<? extends E> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
static <E> List<E> of() {
return ImmutableCollections.List0.instance();
}
static <E> List<E> of(E e1) {
return new ImmutableCollections.List1<>(e1);
}
static <E> List<E> of(E e1, E e2) {
return new ImmutableCollections.List2<>(e1, e2);
}
static <E> List<E> of(E... elements) {
switch (elements.length) { // implicit null check of elements
case 0:
return ImmutableCollections.List0.instance();
case 1:
return new ImmutableCollections.List1<>(elements[0]);
case 2:
return new ImmutableCollections.List2<>(elements[0], elements[1]);
default:
return new ImmutableCollections.ListN<>(elements);
}
}
static <E> List<E> copyOf(Collection<? extends E> coll) {
if (coll instanceof ImmutableCollections.AbstractImmutableList) {
return (List<E>)coll;
} else {
return (List<E>)List.of(coll.toArray());
}
}這些方法都與位置相關，容易理解，不做闡述。Java 8對List接口增加了幾個默認方法，包括sort、replaceAll和spliterator；Java 9增加了多個重載的of方法，可以根據一個或多個元素生成一個不變的List，具體不介紹，可以看API文檔。
5.3 Random Access
RamdomAccess的定義為：
public interface RandomAccess {
}沒有定義任何方法，這是為什麼呢？因為RandomAccess是一個Marker interface標記接口，用於代表類的一種屬性或者説類具備某種功能。
例如，在一些底層實現中會去判斷接口有沒有實現RandomAccess，如果實現了RandomAccess會使用索引進行查找，反之使用迭代器。比如Collections類中的binarySearch方法。
6. 相關方法
6.1 Arrays.asList
Arrays.asList用於將一個數組轉換為一個List集合，需要注意的是的返回的這個List集合並不是ArrayList對象，而是Arrays內部的ArrayList對象，它表示一個不允許發生結構性變化的ArrayList對象，比如對這個返回的對象調用add方法，會發生java.lang.UnsupportedOperationException異常，代碼示例如下：
String[] names = new String[]{"zs", "ls", "ww"};
ArrayList<String> nameList = Arrays.asList(names);
nameList.add("zl");Arrays內部的ArrayList繼承了AbstractList，它表示一個不可修改的列表，如果想要數組轉換後的ArrayList是可變的或者説是可修改的，可以這麼做：
String[] names = new String[]{"zs", "ls", "ww"};
ArrayList<String> nameList = new ArrayList<String>(Arrays.asList(names));
nameList.add("zl");在這個內部類中，內部的數組使用的就是傳入的數組，沒有拷貝，也沒有動態改變大小，對數組的修改也會反應到List當中。
6.2 ArrayList.toArray
Arraylist.toArray()可以將ArrarList對象轉換成Object數組：
ArrayList<String> names = new ArrayList<String>();
names.add("zs");
names.add("ls");
names.add("ww");
Object[] objs = new Object[names.size()];
objs = nameList.toArray();如果希望將ArrayList對象轉換後的數組是初始化ArrayList時候指定的泛型類型，可以這麼做：
ArrayList<String> names = new ArrayList<String>();
names.add("zs");
names.add("ls");
names.add("ww");
String[] objs = new String[namesList.size()];
objs = nameList.toArray(new String[0]);7. 特點分析
- 支持隨機訪問，如果按照索引查找內容，速度是O(1)，一步到位
- 不是一個線程安全的集合，考慮線程安全可以使用
Vector，CopyOnWriteArrayList，Vector與ArrayList實現類似，使用synchronized實現了線程安全
