ArrayList簡介
ArrayList概述
- ArrayList是可以動態(tài)增長和縮減的索引序列,它是基于數組實現的List類。
- ArrayList封裝了一個動態(tài)再分配的Object[]數組,每一個類對象都有一個capacity屬性,表示它們所封裝的Object[]數組的長度,當向ArrayList中添加元素時,該屬性值會自動增加。如果想ArrayList中添加大量元素,可以使用ensureCapacity方法一次性增加capacity,可以減少增加重新分配的次數提高性能。
- ArrayList和Vector作為List類的兩個典型實現,完全支持List中的全部功能。ArrayList和Vector的顯著區(qū)別是,ArrayList的線程不安全的,當多個線程訪問同一個ArrayList集合時,如果超過一個線程修改ArrayList集合,則程序必須手動保證該集合的同步性;但Vector是線程安全的。
- ArrayList UML類圖

ArrayList的數據結構
分析一個類的時候,數據結構往往是它的靈魂所在,理解底層的數據結構其實就是理解這個類的實現思路。
ArrayList的數據結構其實就是數組,數組元素類型為Object類型,即可以存放所有類型的數據。所以我們對ArrayList類所有實例的操作底層都是基于數組的操作。
ArrayList源碼分析
ArrayList類繼承結構和層次關系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
從代碼片段和之前放上去的類圖可以發(fā)現,ArrayList繼承AbstractList,AbstractList繼承AbstractCollection并且實現List。這里有一個思想,接口中全部都是抽象的方法,而抽象類可以有抽象方法,還可以有具體的實現方法,正是利用這一點,讓AbstractList是實現List接口中一些通用的方法,而具體的類ArrayList就繼承這個AbstractList,拿到一些通用的方法,然后自己再實現自己需要定制的方法,這樣一來,讓代碼層次結構更清晰。減少重復代碼。
ArrayList類中實現的接口
-
List<E>:查閱資料好像是當時作者的一個錯誤,因為不影響使用就保留到現在了。 -
RandomAccess:這是一個標記性接口,通過查看API文檔,它的作用就是用來快速隨機存取,有關效率的問題,在實現了該接口的話,那么使用普通的for循環(huán)來遍歷,性能更高,例如ArrayList。而沒有實現該接口的話,使用Iterator來迭代,這樣性能更高,例如LinkedList。所以這個標記性接口只是為了讓我們知道我們用什么樣的方式去獲取數據性能更好。 -
Cloneable:實現了該接口,就可以使用Object.clone()方法了。 -
Serializable:實現該序列化接口,表面該類可以被序列化,什么是序列化?簡單的說,就是能夠從類變成字節(jié)流傳輸,然后還能從字節(jié)流變成原來的類。
ArrayList中的屬性
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 版本號
private static final long serialVersionUID = 8683452581122892189L;
/**
* 缺省容量
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空對象數組
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 缺省控對象數組
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 實際元素數組
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 實際元素數組大小
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* 最大數組容量
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
ArrayList中的構造方法
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;
}
}
無參構造方法
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
雖然構造函數的注解上顯示說明默認的構造函數會將初始化容量設置為10,但是實際上從代碼看,初始化出來是一個空的Object數組,就是這個elementData。
有參構造方法
/**
* 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);
}
}
這個構造函數會給定一個初始化容量大??;若這個初始化容量大小大于0,則把參數當成初始化數組的大小,若這個初始化容量等于0,則初始化一個空的數組,否則則報出非法數據異常。
有參構造方法二
/**
* 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;
}
}
這個其實是將Collection轉換為ArrayList。
ArrayList中的核心方法
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++;
}
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
- boolean add(E e)
/**
* 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;
}
描述:默認直接在集合末尾添加元素。
分析:
- ensureCapacityInternal(size + 1)
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));// 確定內部容量方法
}
- calculateCapacity(Object[] elementData, int minCapacity)
// 計算容量大小
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
這里有兩種情況分別需要分析:
第一種情況:elementData初始化時是空的數組,那么第一次add的時候,minCapacity=size+1;也就是說minCapacity=1,這是就會將初始化容量設置為DEFAULT_CAPACITY,也就是minCapacity=10。
第二種情況:elementData不是一個空數組,那么在add的時候,minCapacity=size+1;也就是minCapacity代表著elementData中增加之后的實際數據的個數情況,后面會拿著它去和elementData的length比較,如果length不夠用,那么肯定要擴大容量,不然增加這個元素就會溢出。
- ensureExplicitCapacity(int minCapacity)
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 后面解釋
// overflow-conscious code
if (minCapacity - elementData.length > 0) // 判斷minCapacity的長度是不是大于elementData的數組長度length,如果大于0,則說明數組長度這時候已經不夠用了。則需要對數組進行擴容。
grow(minCapacity); // 確定數組容量大小,并改變容量大小
}
- grow(int minCapacity)
// 核心方法,擴展數組容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // elementData的長度賦給oldCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1); // 計算新的elementData的大小,就是1.5倍的oldCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; // 這里是為了適應elementData就是空數組的時候,length=0,那么這個時候newCapacity和oldCapacity都為0,所以這里的判斷成立了,這里將newCapacity設置為10
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity); // 如果newCapacity超過了最大的容量限制,就調用hugeCapacity,也就是能夠給的最大值的newCapacity。
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); // 最后將數組的容量已經確定好,直接拷貝就可以了。
}
補充:
之前有一個modCount屬性沒有說明,現在來解釋一下。我們發(fā)現在父類AbstractList中定義了一個int型的屬性:modCount,記錄了ArrayList結構性變化的次數。
protected transient int modCount = 0;
在ArrayList的所有涉及結構變化的方法中都增加modCount的值,包括:add()、remove()、addAll()、removeRange()及clear()方法。這些方法每調用一次,modCount的值就加1。
AbstractList中的iterator()方法(ArrayList直接繼承了這個方法)使用了一個私有內部成員類Itr,生成一個Itr對象(Iterator接口)返回:
public Iterator iterator() { return new Itr(); }
Itr實現了Iterator()接口,其中也定義了一個int型的屬性:expectedModCount,這個屬性在Itr類初始化時被賦予ArrayList對象的modCount屬性的值。
int expectedModCount = modCount;
注:內部成員類Itr也是ArrayList類的一個成員,它可以訪問所有的AbstractList的屬性和方法。理解了這一點,Itr類的實現就容易理解了。
在Itr.hasNext()方法中:
public boolean hasNext() { return cursor != size(); }
調用了AbstractList的size()方法,比較當前光標位置是否越界。
在Itr.next()方法中,Itr也調用了定義在AbstractList中的get(int)方法,返回當前光標處的元素:
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
注意,在next()方法中調用了checkForComodification()方法,進行對修改的同步檢查:
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
現在對modCount和expectedModCount的作用應該非常清楚了。在對一個集合對象進行跌代操作的同時,并不限制對集合對象的元素進行操作,這些操作包括一些可能引起跌代錯誤的add()或remove()等危險操作。在AbstractList中,使用了一個簡單的機制來規(guī)避這些風險。 這就是modCount和expectedModCount的作用所在。
- void add(int index, E element)
/**
* 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在插入位置后的所有元素往后面移動一位。
elementData[index] = element;
size++;
}
描述:在集合特定位置添加元素。
分析:
- rangeCheckForAdd(index):檢查index插入的位置是否合理。
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
插入的位置肯定不能大于size和小于0;如果是,則拋出IndexOutOfBoundsException異常。
- boolean addAll(Collection<? extends E> c)
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
描述:將集合c中的所包含的元素都插入到集合中。
- boolean addAll(int index, Collection<? extends E> c)
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
描述:將集合c中所包含的元素都插入到集合的index處。
remove方法
- E remove(int index)
/**
* 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); // 檢查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; // 返回刪除的元素
}
描述:刪除集合指定位置上的元素,并返回刪除的元素。
- boolean remove(Object o)
/**
* 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;
}
描述:刪除集合中第一個特定的對象。這里我們發(fā)現ArrayList是可以存在null值的。
- void clear()
/**
* 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;
}
描述:將elementData中的每個元素都賦值為null,并且等待垃圾回收,且將size設置為0。
- boolean removeAll(Collection<?> c)
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
描述:批量刪除集合中的元素。
分析:
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r]; // false情況取不在c集合中的元素
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
set方法
- E set(int index, E element)
/**
* 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; // 返回舊的值
}
描述:將index索引處的元素替換成element對象,返回被替換的舊元素。
indexOf方法
- int indexOf(Object o)
/**
* 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;
}
描述:返回對象o在集合中第一次出現的位置索引,如果沒有則返回-1。
get方法
- E get(int index)
/**
* 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);
}
描述:返回集合index索引處的元素。
總結
- ArrayList可以存放null值。
- ArrayList本質上是一個elementData數組。
- ArrayList與數組的本質區(qū)別就在于能夠自動擴展,其中自動擴展容量為1.5倍原來容量大小。
- ArrayList由于本質是數組,所以它在數據查詢方面會很快,但是對于數據的插入和刪除,性能會下降很多,因為需要移動數據才能達到插入的效果。
- ArrayList實現了RandomAccess,所以遍歷推薦使用for循環(huán)。