ArrayList是一個容量能夠動態增漲的數組,它是java集合框架中一個重要的類,繼承抽象類AbstractList,實現了List介面。 實現了RandomAccess介面,該介面為標記介面,即提供了隨機訪問功能。 實現了Cloneable介面,可以調用Object的clone方法,返回對象的淺 ...
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList是一個容量能夠動態增漲的數組,它是java集合框架中一個重要的類,繼承抽象類AbstractList,實現了List介面。
實現了RandomAccess介面,該介面為標記介面,即提供了隨機訪問功能。
實現了Cloneable介面,可以調用Object的clone方法,返回對象的淺拷貝。
實現了java.io.Serializable介面,可以進行序列化功能。
ArrayList的屬性
private static final int DEFAULT_CAPACITY = 10; //預設大小 private static final Object[] EMPTY_ELEMENTDATA = {}; //空的數組 private transient Object[] elementData; //存放ArrayList內元素的數組,定義了transient在實現Serializable序列化時,不會被串列化 private int size; //ArrayList的大小,成員變數,系統預設初始化0, 存在堆記憶體中,實際為ArrayList存放元素的個數
ArrayList的構造方法
public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; //初始化一個initialCapacity大小的數組 } public ArrayList() { super(); //ArrayList(10) jdk1.6該構造方法的實現,預設就創建10個大小的數組 this.elementData = EMPTY_ELEMENTDATA; //將elementData的引用指向定義的空數組(本文基於jdk1.7) } public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; if (elementData.getClass() != Object[].class) //返回若不是Object[]將調用Arrays.copyOf方法將其轉為Object[] elementData = Arrays.copyOf(elementData, size, Object[].class); }
ArrayList的方法
add方法
//直接添加元素,添加至數組末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e; //把元素追加到數組最後一個,size+1
return true;
}
//通過下標添加元素,假如當前數組大小為10,數組裡有5個元素,下標傳參只能<=5,
//index=5 則元素直接添加至末尾
//index<5 index原位置元素及後續所有元素都往後移一個單位,新元素插入原index元素位置
//eg: 此時有arraylist有[1,2,3,4,5,6,7,8]size:8,我想在索引為5的時候插入1個數字1
//add(5,1) ,arrayList最後是[1,2,3,4,5,1,6,7,8]
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++;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) { //假如elementDate是個空的數組,即沒有容量大小
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //比較大小,返回大的那個數值,作為初始化數組的大小
}
ensureExplicitCapacity(minCapacity); //檢查容量是否夠,不夠就擴容
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; ////AbstractList里所定義,假如使用迭代器將會用到
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //假設當前的ArrayList大小為12,即oldCapacity大小為12
//12二進位為1100,右移一個單位,即0110,十進位就是6,newCapacity即為18
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//MAX_ARRAY_SIZE=Integer.MAX_VALUE-8 Integer.MAX_VALUE = 2147483647
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); //創建一個原來大小1.5倍的數組,將原數組數據複製過去
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError(); //小於0則報記憶體溢出
//當天arrayList大小假如大於定義的MAX_ARRAY_SIZE大小,則返回Integer的最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private void rangeCheckForAdd(int index) { //檢查數組下標是否越界
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
關於方法:擴容方法grow()里Arrays.copyOf(elementData, newCapacity),就是根據class的類型來決定是new 還是反射去構造一個泛型數組,同時利用System.arraycopy函數,批量賦值元素至新數組中。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
remove方法
public E remove(int index) {
rangeCheck(index); //檢查數組下標越界
modCount++;
E oldValue = elementData(index); //讀出要刪除的值
//eg:假設當前數組值為{1,2,3,4,5,6,7,8},size為8,要刪除index為5的值,在數組裡是6
int numMoved = size - index - 1; //numMoved = 8 - 5 -1 = 2
if (numMoved > 0)
//eg:System.arraycopy(elementData,5+1,elementData,5,2)
//eg:從數組elementData中的第6個位置開始複製2個數,複製到elementData中,從elementData中的5位置開始存放
//eg:{1,2,3,4,5,7,8}
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
//刪除該元素在數組中第一次出現的位置上的數據。 如果有該元素返回true,如果false。
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 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
}
//for迴圈使數組裡每一個元素為null
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
//從2個集合中刪除重疊的數據
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);
}
//從2個集合中獲取重疊的數據
public boolean retainAll(Collection<?> c) {
return batchRemove(c, true);
}
//
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData; //獲得當前對象的所有元素
int r = 0, w = 0; //w:標記兩個集合公共元素的個數
boolean modified = false;
try {
for (; r < size; r++) ////遍歷集合A
if (c.contains(elementData[r]) == complement) //判斷集合B中是否包含集合A中的當前元素
elementData[w++] = elementData[r]; //如果包含則直接保存。
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) { //出現異常會導致 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; //記錄集合中元素的改變(add/remove)
size = w;
modified = true;
}
}
return modified;
}
set方法
public E set(int index, E element) {
rangeCheck(index); //檢查數組下標越界
E oldValue = elementData(index); //取出原來的元素
elementData[index] = element; //替換元素
return oldValue; //返回原來的元素
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
get方法
public E get(int index) {
rangeCheck(index); //檢查數組下標越界
return elementData(index);
}
iterator
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; //預設0
int lastRet = -1; //上次返回的元素
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; //游標+1
return (E) elementData[lastRet = i];//返回元素,並將記錄上次返回元素的下標
}
public void remove() { //remove掉上次next的元素
if (lastRet < 0) //判斷有沒有執行過next方法
throw new IllegalStateException();
checkForComodification(); //
try {
ArrayList.this.remove(lastRet); //刪除上次next的元素,會修改modCount
cursor = lastRet; //被刪除位置賦值給游標
lastRet = -1; //不能連續刪除
expectedModCount = modCount; //更新expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() { //Fail-Fast 機制
if (modCount != expectedModCount) //因此如果在使用迭代器的過程中有其他線程修改了modCount,就會拋ConcurrentModificationException()
throw new ConcurrentModificationException();
}