ArrayList簡介
ArrayList 是一個數組隊列，相當于 動态數組。與Java中的數組相比，它的容量能動态增長。它繼承于AbstractList，實作了List, RandomAccess, Cloneable, java.io.Serializable這些接口。
ArrayList 繼承了AbstractList，實作了List。它是一個數組隊列，提供了相關的添加、删除、修改、周遊等功能。
ArrayList 實作了RandmoAccess接口，即提供了随機通路功能。RandmoAccess是java中用來被List實作，為List提供快速通路功能的。在ArrayList中，我們即可以通過元素的序号快速擷取元素對象；這就是快速随機通路。稍後，我們會比較List的“快速随機通路”和“通過Iterator疊代器通路”的效率。
ArrayList 實作了Cloneable接口，即覆寫了函數clone()，能被克隆。
ArrayList 實作java.io.Serializable接口，這意味着ArrayList支援序列化，能通過序列化去傳輸。
和Vector不同，ArrayList中的操作不是線程安全的！是以，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList。
ArrayList源碼
ArrayList屬性
// 序列化id
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 = {};
// 目前資料對象存放地方，目前對象不參與序列化
transient Object[] elementData;
// 目前數組長度
private int size;
// 數組最大長度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
} ArrayList構造函數
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
} - 如果不傳入參數，則使用預設無參建構方法建立ArrayList對象，此時我們建立的ArrayList對象中的elementData中的長度是0，size是0,當進行第一次add的時候，elementData将會變成預設的長度：10.
- 如果傳入int類型參數，則代表指定ArrayList的初始數組長度，傳入參數如果是大于等于0，則使用使用者的參數初始化，如果使用者傳入的參數小于0，則抛出異常。
- 如果傳入帶Collection對象，将collection對象轉換成數組，然後将數組的位址的賦給elementData。更新size的值，同時判斷size的大小，如果是size等于0，直接将空對象EMPTY_ELEMENTDATA的位址賦給elementData。如果size的值大于0，則執行Arrays.copy方法，把collection對象的内容（可以了解為深拷貝）copy到elementData中。
- 注意：this.elementData = arg0.toArray(); 這裡執行的簡單指派時淺拷貝，是以要執行Arrays,copy 做深拷貝
add方法
/**
* 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;
}
/**
* 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) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
} add的方法有兩個，一個是帶一個參數的，一個是帶兩個參數的，下面我們一個個講解。
add(E e) 方法
add主要的執行邏輯如下：
- 確定數組已使用長度（size）加1之後足夠存下 下一個資料
- 修改次數modCount 辨別自增1，如果目前數組已使用長度（size）加1後的大于目前的數組長度，則調用grow方法，增長數組，grow方法會将目前數組的長度變為原來容量的1.5倍。
- 確定新增的資料有地方存儲之後，則将新元素添加到位于size的位置上。
- 傳回添加成功布爾值。
添加元素方法入口：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
} 確定添加的元素有地方存儲，當第一次添加元素的時候this.size+1 的值是1，是以第一次添加的時候會将目前elementData數組的長度變為10（具體細節請深入calculateCapacity方法）：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
} 将修改次數（modCount）自增1，判斷是否需要擴充數組長度,判斷條件就是用目前所需的數組最小長度與數組的長度對比，如果大于0，則增長數組長度。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
} 如果目前的數組已使用空間（size）加1之後 大于數組長度，則增大數組容量，擴大為原來的1.5倍(int newCapacity = oldCapacity + (oldCapacity >> 1))
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);
} add(int index, E element)方法
這個方法其實和上面的add類似，該方法可以按照元素的位置，指定位置插入元素，具體的執行邏輯如下：
- 確定數插入的位置小于等于目前數組長度，并且不小于0，否則抛出異常
- 確定數組已使用長度（size）加1之後足夠存下 下一個資料
- 修改次數（modCount）辨別自增1，如果目前數組已使用長度（size）加1後的大于目前的數組長度，則調用grow方法，增長數組
- grow方法會将目前數組的長度變為原來容量的1.5倍。
- 確定有足夠的容量之後，使用System.arraycopy 将需要插入的位置（index）後面的元素統統往後移動一位。
-
将新的資料内容存放到數組的指定位置（index）上
注意：使用該方法的話将導緻指定位置後面的數組元素全部重新移動，即往後移動一位。
/**
* 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) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
} get方法
傳回指定位置上的元素，較為簡單，不再闡述
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
} set方法
確定set的位置小于目前數組的長度（size）并且大于0，擷取指定位置（index）元素，然後放到oldValue存放，将需要設定的元素放到指定的位置（index）上，然後将原來位置上的元素oldValue傳回給使用者。
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
} contains方法
調用indexOf方法，周遊數組中的每一個元素作對比，如果找到對于的元素，則傳回true，沒有找到則傳回false
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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;
} remove方法
根據索引remove
- 判斷索引有沒有越界
- 自增修改次數
- 将指定位置（index）上的元素儲存到oldValue
- 将指定位置（index）上的元素都往前移動一位
- 将最後面的一個元素置空，好讓垃圾回收器回收
-
将原來的值oldValue傳回
注意：調用這個方法不會縮減數組的長度，隻是将最後一個數組元素置空而已。
/**
* 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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
} 根據對象remove
循環周遊所有對象，得到對象所在索引位置，然後調用fastRemove方法，執行remove操作
fastRemove方法:定位到需要remove的元素索引，先将index後面的元素往前面移動一位（調用System.arraycooy實作），然後将最後一個元素置空
/**
* 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 ? get(i)==null : 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++)
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
} clear方法
添加操作次數（modCount），将數組内的元素都置空，等待垃圾收集器收集，不減小數組容量
/**
* 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;
} subList方法
我們看到代碼中是建立了一個ArrayList 類裡面的一個内部類SubList對象，傳入的值中第一個參數時this參數，其實可以了解為傳回目前list的部分視圖，真實指向的存放資料内容的地方還是同一個地方，如果修改了sublist傳回的内容的話，那麼原來的list也會變動。
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
} trimToSize方法
- 修改次數加1
- 将elementData中空餘的空間（包括null值）去除，例如：數組長度為10，其中隻有前三個元素有值，其他為空，那麼調用該方法之後，數組的長度變為3.
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
} iterator方法
interator方法傳回的是一個内部類，由于内部類的建立預設含有外部的this指針，是以這個内部類可以調用到外部類的屬性。
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
} 一般的話，調用完iterator之後，我們會使用iterator做周遊，這裡使用next做周遊的時候有個需要注意的地方，就是調用next的時候，可能會引發ConcurrentModificationException，當修改次數，與期望的修改次數（調用iterator方法時候的修改次數）不一緻的時候，會發生該異常，詳細我們看一下代碼實作：
@SuppressWarnings("unchecked")
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];
} expectedModCount這個值是在使用者調用ArrayList的iterator方法時候确定的，但是在這之後使用者add，或者remove了ArrayList的元素，那麼modCount就會改變，那麼這個值就會不相等，将會引發ConcurrentModificationException異常，這個是在多線程使用情況下，比較常見的一個異常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
} 以下為Itr全部源碼
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
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];
}
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();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* An optimized version of AbstractList.ListItr
*/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
} System.arraycopy 方法
| 參數 | 說明 |
| src | 原數組 |
| srcPos | 原數組 |
| dest | 目标數組 |
| destPos | 目标數組的起始位置 |
| length | 要複制的數組元素的數目 |
Arrays.copyOf方法
//基本資料類型（其他類似byte，short···）
public static int[] copyOf(int[] original, int newLength) {
int[] copy = new int[newLength];
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
} 小結
- ArrayList自己實作了序列化和反序列化的方法，因為它自己實作了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
- ArrayList基于數組方式實作，無容量的限制（會擴容）
- 添加元素時可能要擴容（是以最好預判一下），删除元素時不會減少容量（若希望減少容量，trimToSize()），删除元素時，将删除掉的位置元素置為null，下次gc就會回收這些元素所占的記憶體空間。
- 線程不安全
- add(int index, E element)：添加元素到數組中指定位置的時候，需要将該位置及其後邊所有的元素都整塊向後複制一位
- get(int index)：擷取指定位置上的元素時，可以通過索引直接擷取（O(1)）
- remove(Object o)需要周遊數組
- remove(int index)不需要周遊數組，隻需判斷index是否符合條件即可，效率比remove(Object o)高
- contains(E)需要周遊數組
- 使用iterator周遊可能會引發多線程異常
![資料結構之 數組資料結構之 數組[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)