一、概述
ArrayList底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組扔字，故保持了數(shù)組的基本特點(diǎn)：隨機(jī)訪問(wèn)速度較快育拨，刪除和插入(如果是末尾速度也還好)數(shù)據(jù)速度較慢，因?yàn)橐肧ystem.arraycopy()來(lái)移動(dòng)这橙。默認(rèn)初始容量為10奏窑，超出容量擴(kuò)容按50%增加。
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 = {};
/**
* 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 == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
.........
其中elementData(真正保存數(shù)據(jù)的數(shù)組)屈扎，注意到是transient修飾的埃唯，為什么呢？首先鹰晨，序列化是對(duì)象轉(zhuǎn)為字節(jié)序列的過(guò)程墨叛，反序列化則是字節(jié)序列回復(fù)為對(duì)象的過(guò)程止毕。transient是用來(lái)表示一個(gè)域不是該對(duì)象序行化的一部分，當(dāng)一個(gè)對(duì)象被序行化的時(shí)候漠趁，transient修飾的變量的值是不包括在序行化中的扁凛。elementData用transient修飾的原因在于elementData里面不是所有的元素都有數(shù)據(jù)，因?yàn)槿萘康膯?wèn)題棚潦，elementData里面有一些元素是空的令漂，這種是沒(méi)有必要序列化的。那ArrayList是可以進(jìn)行序列化的丸边，那elementData是怎么進(jìn)行序列化的叠必？ArrayList是通過(guò)其中的兩個(gè)方式實(shí)現(xiàn)的：readObject和writeObject。
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
/**
* Save the state of the <tt>ArrayList</tt> instance to a stream (that
* is, serialize it).
*
* @serialData The length of the array backing the <tt>ArrayList</tt>
* instance is emitted (int), followed by all of its elements
* (each an <tt>Object</tt>) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
二妹窖、主要實(shí)現(xiàn)
1纬朝、構(gòu)造函數(shù)
ArrayList(int initialCapacity) ：構(gòu)造具有初始容量的空列表；
ArrayList()：默認(rèn)構(gòu)造函數(shù)骄呼，提供初始容量為10的空列表共苛；
ArrayList(Collection<? extends E> c)：構(gòu)造一個(gè)包含指定collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的蜓萄。
/**
* 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];
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
super();
this.elementData = 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();
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隅茎、trimToSize
是為了縮小elementData的大小以達(dá)到節(jié)約內(nèi)存的目的，比如某次場(chǎng)景需要擴(kuò)容至100嫉沽，而此后size存儲(chǔ)量基本在10以內(nèi)辟犀，那么就可以用這個(gè)函數(shù)了。另外绸硕，在ArrayList中常用到Arrays.copyof堂竟，其底層實(shí)現(xiàn)是通過(guò)System.arraycopy來(lái)完成的。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
3玻佩、新增元素
add(E e)出嘹、add(int index, E element)、addAll(Collection<? extends E> c)咬崔、addAll(int index, Collection<? extends E> c)税稼、set(int index, E element) ，這里主要分析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;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == 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);
}
/**
* 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
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);
}
上述代碼中重點(diǎn)關(guān)注grow方法垮斯，新增元素如果需要擴(kuò)容郎仆，則增加50%。另外在add和remove中都存在modcount甚脉，修改次數(shù)，在readObject铆农、writeObject牺氨、Itr中的next中都有用到狡耻，在這些方法中如果modcount改變了將會(huì)拋出異常：ConcurrentModificationException()。意思就是在遍歷遍歷的過(guò)程中如果對(duì)數(shù)組進(jìn)行了增刪操作將會(huì)拋出異常猴凹。以Itr舉例夷狰，因?yàn)锳rrayList被設(shè)計(jì)成非同步的，所以如果在遍歷集合過(guò)程中刪除元素不拋出異常郊霎，則會(huì)拋出：ArrayIndexOutOfBoundsException沼头。
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;
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();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
4、刪除
remove(int index)书劝、remove(Object o)进倍、removeRange(int fromIndex, int toIndex)、removeAll()购对。
/**
* 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;
}
查找很簡(jiǎn)單猾昆，就不分析了。
三骡苞、區(qū)別與聯(lián)系
1垂蜗、與LinkedList
1）、ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)解幽，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)贴见。
2）、對(duì)于隨機(jī)訪問(wèn)get和set躲株，ArrayList覺(jué)得優(yōu)于LinkedList片部，因?yàn)長(zhǎng)inkedList要移動(dòng)指針。
3）徘溢、對(duì)于新增和刪除操作add和remove（不是在尾部添加刪除）吞琐，LinkedList比較占優(yōu)勢(shì)，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)然爆。
2站粟、與vector
1）、Vector和ArrayList幾乎是完全相同的,唯一的區(qū)別在于Vector是同步類(synchronized)曾雕，屬于強(qiáng)同步類奴烙。因此開(kāi)銷就比ArrayList要大，訪問(wèn)要慢剖张。正常情況下,大多數(shù)的Java程序員使用ArrayList而不是Vector,因?yàn)橥酵耆梢杂沙绦騿T自己來(lái)控制切诀。
2）、Vector每次擴(kuò)容請(qǐng)求其大小的2倍空間搔弄，而ArrayList是1.5倍幅虑。
3）、Vector還有一個(gè)子類Stack.
