基于JDK 1.8.0。
簡介：
ArrayList 底層是通過數(shù)組實(shí)現(xiàn)的，相當(dāng)于一個(gè)動(dòng)態(tài)的數(shù)組。
特點(diǎn)：
- 底層實(shí)現(xiàn)：使用數(shù)組實(shí)現(xiàn)。
- 線程安全：線程不安全。
- 擴(kuò)容：可以動(dòng)態(tài)擴(kuò)容。
- 是否可以存放null：可以存放null
- 是否有序：
- 效率：取元素比較快，時(shí)間復(fù)雜度都是O(1) ， 增加刪減元素慢，會導(dǎo)致元素的移動(dòng)。
- 是否可以重復(fù)：可以放入重復(fù)的元素。
源碼分析：
ArrayList 里面最基礎(chǔ)的兩個(gè)屬性 elementData 和 size。elementData 是一個(gè)對象數(shù)組，用于存放元素。size則是表示實(shí)際ArrayList里面的元素個(gè)數(shù)。
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
構(gòu)造函數(shù)：
ArrayList有3個(gè)構(gòu)造函數(shù)
- 可以從源碼看出，傳入一個(gè)整形的初始容量值作為數(shù)組的長度然后new一個(gè)數(shù)組。
/**
* 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) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
2.不傳任何參數(shù)，默認(rèn)10為數(shù)組長度，調(diào)用帶參數(shù)的構(gòu)造函數(shù)來創(chuàng)建。
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
3.傳入一個(gè)Collection集合對象，然后將集合轉(zhuǎn)換為Object數(shù)組。并設(shè)置size屬性為elementData數(shù)組的長度。
/**
* 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();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
在分析添加方法之前，有2個(gè)方法需要了解和分析的。一個(gè)是ensureCapacityInternal()，另一個(gè)是grow()。
ensureCapacityInternal 方法是檢查當(dāng)前對象數(shù)組的容量能否滿足將要裝的元素的最大長度。如果不能滿足，則動(dòng)態(tài)擴(kuò)容。擴(kuò)容方法則是grow方法。
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
if (minCapacity > 0)
ensureCapacityInternal(minCapacity);
}
private void ensureCapacityInternal(int minCapacity) {
//修改次數(shù)+1
modCount++;
// overflow-conscious code
//如果最小容量大于當(dāng)前數(shù)組的長度，就擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow() 方法是對ArrayList的動(dòng)態(tài)擴(kuò)容。操作是，計(jì)算出新的容量，創(chuàng)建新的數(shù)組，然后將舊的數(shù)組元素復(fù)制到新的數(shù)組， 然后使用新的數(shù)組。
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
//獲取當(dāng)前的數(shù)組的長度，即當(dāng)前的容量。
int oldCapacity = elementData.length;
//新容量的計(jì)算 = 舊容量 + 舊容量右移1位
//右移運(yùn)算=對應(yīng)數(shù)字的二進(jìn)制數(shù)的最右補(bǔ)充1位
// 相當(dāng)于 十進(jìn)制 / 2，但不等于，例如 1 右移1位=0
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果舊容量仍然大于新容量，則新容量=舊容量
//如果容量的計(jì)算超出了int的取值范圍，就會導(dǎo)致溢出
//就會導(dǎo)致出現(xiàn)舊容量大于新容量的情況
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于最大數(shù)組大小的話，就調(diào)用獲取巨大容量方法。
//hugeCapacity 返回的最大值其實(shí)也只是 Integer.MAX_VALUE .
//那么就是說，ArrayList的最大容量是 Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//最后調(diào)用copyOf方法創(chuàng)建新的數(shù)組，并且將舊數(shù)組的元素復(fù)制到新數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
添加元素
添加元素方法有兩種，一種是添加單個(gè)元素，一種是添加一個(gè)集合。添加單個(gè)元素使用add()方法，add()方法有1個(gè)重載。 添加集合使用addAll()方法，addAll()方法也有1個(gè)重載。
- 添加一個(gè)元素，不指定位置。雖然是直接將元素添加到數(shù)組的最尾端，不用移動(dòng)數(shù)組。但是我覺得效率還是不太好，因?yàn)槿绻麛?shù)組容量不夠的時(shí)候，擴(kuò)容的時(shí)候還是要將數(shù)組復(fù)制一遍。
/**
* 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) {
//檢查容量是否足夠，如果不足，則會擴(kuò)容。
ensureCapacityInternal(size + 1); // Increments modCount!!
//將新的元素放到數(shù)組的尾部
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) {
//檢查添加的位置是否超出數(shù)組范圍，超出就拋異常。
rangeCheckForAdd(index);
//確認(rèn)數(shù)組的容量，容量不夠的話，則擴(kuò)容。
ensureCapacityInternal(size + 1); // Increments modCount!!
//將指定位置后的元素后移一位。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//將元素插入到數(shù)組指定的位置。
elementData[index] = element;
size++;
}
3.添加一個(gè)集合，不指定位置。直接將集合轉(zhuǎn)換成Object數(shù)組， 然后追加到數(shù)組的最尾端。
/**
* 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) {
//將集合轉(zhuǎn)換成Oibject數(shù)組。
Object[] a = c.toArray();
//獲取要添加的集合的數(shù)組的長度。
int numNew = a.length;
//確認(rèn)新當(dāng)前數(shù)組的容量， 如果不夠，則擴(kuò)容。
ensureCapacityInternal(size + numNew); // Increments modCount
//將對象數(shù)組添加到當(dāng)前ArrayList數(shù)組的尾端。
System.arraycopy(a, 0, elementData, size, numNew);
//size增加。
size += numNew;
return numNew != 0;
}
- 從指定的位置添加一個(gè)集合。
/**
* 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) {
//檢查位置是否在數(shù)組范圍內(nèi)
rangeCheckForAdd(index);
//將需要添加的集合轉(zhuǎn)換成對象數(shù)組
Object[] a = c.toArray();
//獲取對象數(shù)組的長度
int numNew = a.length;
//確認(rèn)當(dāng)前數(shù)組的容量，如果不組，則擴(kuò)容。
ensureCapacityInternal(size + numNew); // Increments modCount
//確定需要移動(dòng)的元素個(gè)數(shù)
int numMoved = size - index;
//如果移動(dòng)的元素個(gè)數(shù)大于0，則先移動(dòng)數(shù)組元素。
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//將對象數(shù)組復(fù)制添加到ArrayList的指定位置。
System.arraycopy(a, 0, elementData, index, numNew);
//添加元素個(gè)數(shù)
size += numNew;
return numNew != 0;
}
刪除元素
刪除元素有5個(gè)公開的方法。刪除單個(gè)元素用remove() ，有1個(gè)重載。刪除集合用removeAll()或者removeRange()。 清空集合使用 clear()。私有方法fastRemove()是執(zhí)行刪除的方法， 判斷要?jiǎng)h除的元素是否處于數(shù)組的末端。如果是則直接將元素指向null，如果不是，則移動(dòng)待刪除元素后的元素覆蓋 待刪除元素， 然后將最后一個(gè)元素指向null。
1.根據(jù)索引刪除一個(gè)元素
/**
* 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);
//增加修改次數(shù)
modCount++;
//獲取指定索引的元素。
E oldValue = elementData(index);
//計(jì)算出需要移動(dòng)的元素個(gè)數(shù)
int numMoved = size - index - 1;
//如果需要移動(dòng)的元素個(gè)數(shù)大于0，則將數(shù)組后面的元素移動(dòng)覆蓋這個(gè)索引元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//數(shù)組的總長度-1，并且將最后一個(gè)元素指向null
elementData[--size] = null; // Let gc do its work
//返回刪除元素
return oldValue;
}
2.根據(jù)元素對象刪除元素。
/**
* 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) {
//如果傳過來的對象是null。
if (o == null) {
//循環(huán)當(dāng)前的數(shù)組，找到等于null的元素，并刪除。
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//如果對象不是null。循環(huán)當(dāng)前數(shù)組，調(diào)用equals方法找到元素，并刪除。
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
//如果找到元素并刪除，就會在之前返回true。如果都沒有找到的話。則沒有對應(yīng)的元素，返回false。
return false;
}
3.removeAll方法，調(diào)用的是私有的batchRemove()方法。
public boolean removeAll(Collection<?> 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];
} 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) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
4.removeRange方法刪除指定范圍的元素。
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
//修改次數(shù)加1
modCount++;
//計(jì)算出需要移動(dòng)的元素。
int numMoved = size - toIndex;
//移動(dòng)元素覆蓋掉要?jiǎng)h除的元素。
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
//計(jì)算出刪除后的數(shù)組的大小。
int newSize = size - (toIndex-fromIndex);
//將已經(jīng)不需要的元素指向null ，讓垃圾收集器進(jìn)行回收。
while (size != newSize)
elementData[--size] = null;
}
- 清空ArrayList。
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
//修改次數(shù)加1
modCount++;
// Let gc do its work
//循環(huán)將所有數(shù)組元素指向null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
獲取元素
ArrayList的優(yōu)勢就在于獲取元素。因?yàn)榈讓邮鞘褂脭?shù)組實(shí)現(xiàn)的。所以獲取任意位置的元素的時(shí)間復(fù)雜度都是 O(1)。 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);
//根據(jù)索引直接返回?cái)?shù)組元素。elementData方法也只是直接返回?cái)?shù)組元素。
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
總結(jié)
ArrayList 的主要方法都沒有做到線程安全。所以單線程的話就使用ArrayList是效率比較高的。
