ArrayList是常用的集合類,底層所使用的是數組。其特點相對數組來說可以動态擴充。
構造函數方法:
List<T> list = new ArrayList<>();
List<E> list2 = new ArrayList<>(16);
//常量,一個空的Object數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//指向資料數組的引用
transient Object[] elementData;
//常量,一個空的Object數組,它與DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是有差別的,後面可以看到
private static final Object[] EMPTY_ELEMENTDATA = {};
//無參構造方法
public ArrayList() {
//初始大小為空
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//有初始大小的構造方法
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);
}
}
添加:
boolean add(E e):
//ArrayList包含元素的數量
private int size;
//預設容量
private static final int DEFAULT_CAPACITY = 10;
//容器修改次數,主要用于疊代過程中的快速失敗,後面會看到
protected transient int modCount = 0;
//最大數組長度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public boolean add(E e) {
//【重點】: 判斷是否需要擴容,如果需要,根據特定的算法确定擴容大小
ensureCapacityInternal(size + 1); // Increments modCount!!
//向後追加資料
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//數組為空的兩種情況:(1).new ArrayList() ; (2).new ArrayList(0);
//第一次添加元素時,如果是(1):elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA
//如果是(2):elementData==EMPTY_ELEMENTDATA
//在第一次添加元素時,(1)的情況下,ArrayList的容量從0增加到>=10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//确定ArrayList的容量
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//修改次數加1
modCount++;
//判斷是否需要擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
//原始容量
int oldCapacity = elementData.length;
//在原始容量的基礎擴充50%
int newCapacity = oldCapacity + (oldCapacity >> 1);
//選取minCapacity 和 newCapacity 中的最大值,作為newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果在原始容量的基礎擴充50%,超出了數組的最大長度,則需要根據minCapcity重寫計算
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//建立新的數組對象,同時拷貝原數組中的資料
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
疑問:根據代碼來看,ArrayList的最大長度MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8,最終擴充還是可以到Integer.MAX_VALUE,這樣有什麼考究嗎?如果有大佬知道,請留言,感謝!
删除:
boolean remove(int index):
//根據下标删除元素
public E remove(int index) {
//檢查下标是否合法
rangeCheck(index);
//修改次數加1
modCount++;
//找出對應元素
E oldValue = elementData(index);
//計算所需移動元素的個數
int numMoved = size - index - 1;
//将index+1到size中的元素左移一位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//清除最後一個元素的資料,
//如果最後一個元素是引用類型,可以讓GC回收
elementData[--size] = null;
//傳回移除元素
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
boolean remove(Object o):
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
}
疊代器:
Iterator<E> iterator():
public Iterator<E> iterator() {
return new Itr();
}
//疊代器具體實作
private class Itr implements Iterator<E> {
//下一個元素的下标
int cursor;
//最後一個傳回元素的下标值
int lastRet = -1;
//儲存再周遊之前ArrayList的修改次數
//說明:ArrayList在疊代時,不允許其他線程向集合中添加或删除元素
int expectedModCount = modCount;
//下一個元素下标<size
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;
//取出元素值,同時給lastRet指派
return (E) elementData[lastRet = i];
}
//删除最近一個疊代元素
public void remove() {
//元素還未疊代,無法删除
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//删除最近一個疊代元素
ArrayList.this.remove(lastRet);
//删除後從lastRet+1到size-1的元素向前移動一位
//是以下一個元素下标還是lastRet
cursor = lastRet;
lastRet = -1;
//目前線程可以删除元素,這裡指派就是避免checkForComodification()檢查出錯
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//java8中提供的,用于對剩餘未疊代元素進行處理,處理方式由調用者定制
@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++]);
}
//更新相關資料
cursor = i;
lastRet = i - 1;
checkForComodification();
}
//檢查是否有并發問題
final void checkForComodification() {
//疊代過程中不允許其他線程修改或删除元素
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
ListIterator<E> listIterator(int index):
//ListItr 對Itr疊代器進行擴充,Itr中隻有删除元素的方法,這裡擴充了‘添加/替換’元素的方法
//并且可以指定疊代位置,以及疊代方向,支援向前疊代
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
//繼承Itr疊代器
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向前移動
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();
}
}
}
暫時隻分析到這,可以看到ArrayList的強大,遠不止我們平常所看到的那些。