一. 構(gòu)造函數(shù)
二. 添加元素
2.1 添加一個元素到末尾
2.2 將指定的元素插入此列表中的指定位置
2.3 將一個指定collection中的所有元素添加到此列表的尾部
2.4 從指定的位置開始显蝌，將指定collection中的所有元素插入到此列表中
三. 用指定的元素替代此列表中指定位置上的元素
四. 刪除元素
4.1 移除此列表中指定位置上的元素
4.2 移除此列表中首次出現(xiàn)的指定元素 (如果存在)
4.3 從指定collection1中移除與指定collection2中相同的所有元素;
五. 調(diào)整數(shù)組容量
六. 將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實(shí)際元素的大小
七. 總結(jié)
一. 構(gòu)造函數(shù)
ArrayList是List接口的可變數(shù)組的實(shí)現(xiàn)曼尊，實(shí)現(xiàn)了所有可選列表操作骆撇，并允許包括 null 在內(nèi)的所有元素父叙；底層使用數(shù)組保存所有元素，其操作基本上是對數(shù)組的操作，無序不唯一鲸匿；
transient Object[] elementData;
// ArrayList的大凶杓纭（所包含元素的個數(shù)）
private int size;
// 用于空實(shí)例的共享空數(shù)組實(shí)例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默認(rèn)的空數(shù)組
private static final Object[] DEFAULTCAPACITY_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);
}
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
// 給elementData賦值,ArrayList實(shí)際存放元素的數(shù)組
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
從 ArrayList 的構(gòu)造函數(shù)中可以看到當(dāng)沒有給初始大小時, 默認(rèn)給初始數(shù)組賦值的是一個空數(shù)組;
二. 添加元素
2.1 添加一個元素到末尾
private static final int DEFAULT_CAPACITY = 10;
public boolean add(E e) {
// 父類中的變量 用于檢測判斷 ConcurrentModificationException
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
// 判斷是否應(yīng)該進(jìn)行擴(kuò)容
if (s == elementData.length)
// 對數(shù)組進(jìn)行擴(kuò)容的函數(shù)
// 數(shù)組里面沒有元素時,第一次調(diào)grow()方法進(jìn)行擴(kuò)容,默認(rèn)大小為10;
// 后面數(shù)組滿每次進(jìn)行擴(kuò)容時,每次擴(kuò)容原數(shù)組大小的1/2;
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
// 將舊的數(shù)組元素復(fù)制到新的數(shù)組中,新的數(shù)組長度是10或者是擴(kuò)容后的數(shù)組長度;
return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}
private int newCapacity(int minCapacity) {
int oldCapacity = elementData.length;
// 每次擴(kuò)容增加百分之五十的容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 只有第一次添加元素擴(kuò)容時這里才會走進(jìn)來
// 取數(shù)組容量和默認(rèn)容量10之間的最大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0)
throw new OutOfMemoryError();
return minCapacity;
}
// MAX_ARRAY_SIZE為Integer的最大取值
// 將擴(kuò)容后的數(shù)組大小返回(非實(shí)際所存元素的個數(shù))
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity : hugeCapacity(minCapacity);
}
在 ArrayList 添加第一個元素時, 會調(diào) grow() 函數(shù)對初始數(shù)組進(jìn)行第一次擴(kuò)容并且大小為10, 也就是說ArrayList 此時的容量大小是10 但是它當(dāng)前所存儲的元素個數(shù)不一定是10;
后面數(shù)組滿, 每次進(jìn)行擴(kuò)容時, 每次會擴(kuò)大原容量大小的1/2;
2.2 將指定的元素插入此列表中的指定位置
public void add(int index, E element) {
// 對 index 索引進(jìn)行越界檢測
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// 將舊數(shù)組復(fù)制到一個加大的新數(shù)組 并且從指定位置開始元素發(fā)生移位
System.arraycopy(elementData, index,elementData, index + 1,s - index);
elementData[index] = element;
size = s + 1;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2.3 將一個指定collection中的所有元素添加到此列表的尾部
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// 判斷是否需要擴(kuò)容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
// 對數(shù)組 elementData 進(jìn)行復(fù)制元素進(jìn)去的操作
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
2.4 從指定的位置開始柒室，將指定collection中的所有元素插入到此列表中
public boolean addAll(int index, Collection<? extends E> c) {
// 檢測索引是否越界
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// 判斷是否需要擴(kuò)容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
// 對數(shù)組 elementData 進(jìn)行復(fù)制元素進(jìn)去的操作
if (numMoved > 0)
System.arraycopy(elementData, index,elementData, index + numNew,numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
三. 用指定的元素替代此列表中指定位置上的元素
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
// 重新賦值
elementData[index] = element;
// 返回舊元素
return oldValue;
}
四. 刪除元素
4.1 移除此列表中指定位置上的元素
public E remove(int index) {
// 對索引進(jìn)行檢測
Objects.checkIndex(index, size);
final Object[] es = elementData;
// 用變量保存index位置的元素 用于刪除成功后返回
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
// 刪除一個元素后的數(shù)組需要進(jìn)行移位操作, ArrayList里都是復(fù)制到一個新的數(shù)組中;
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
4.2 移除此列表中首次出現(xiàn)的指定元素 (如果存在)
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
4.3 從指定collection1中移除與指定collection2中相同的所有元素;
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// 第一個循環(huán)檢測兩個集合中是否有相同的元素
for (r = from;; r++) {
if (r == end)
return false;// 兩個集合是沒有相同的元素
if (c.contains(es[r]) != complement)
break;
}
// 有相同的元素會繼續(xù)執(zhí)行
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
示例測試
ArrayList<String> list = new ArrayList<>();
list.add("rzc");
list.add("rzc01");
list.add("rzc02");
list.add("rzc03");
ArrayList<String> list2 = new ArrayList<>();
list2.add("rzc");
list2.add("rzc01");
list2.add("rzc04");
list2.removeAll(list);
list.addAll(list2);
System.out.println(list.toString());
System.out.println(list2.toString());
打印結(jié)果
[rzc, rzc01, rzc02, rzc03, rzc04]
[rzc04]
五. 調(diào)整數(shù)組容量
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
所需最小容量與數(shù)組大小作比較，大于需要擴(kuò)容囤屹，從前面的代碼中可以看出擴(kuò)容實(shí)際上是new了一個新的數(shù)組逢渔，然后將舊的數(shù)組中的元素復(fù)制到新的數(shù)組中；
六. 將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實(shí)際元素的大小
public void trimToSize() {
// 父類中的變量 用于檢測判斷 ConcurrentModificationException
modCount++;
// 將實(shí)際存儲的元素個數(shù)與真實(shí)容量做比較
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
// 復(fù)制到一個容量更小的數(shù)組中
: Arrays.copyOf(elementData, size);
}
}
七. 總結(jié)
- 每個 ArrayList 實(shí)例都有一個容量智厌，該容量是指用來存儲列表元素的數(shù)組的大小峦剔，它總是至少等于列表的大小并且最始默認(rèn)值為10；
- 隨著向 ArrayList 中不斷添加元素吝沫，其容量也自動增長惨险；自動增長會帶來數(shù)據(jù)向新數(shù)組的重新拷貝，因此栅受，如果可預(yù)知數(shù)據(jù)量的多少恭朗，可在構(gòu)造 ArrayList 時指定其容量；
- 在添加大量元素前而芥，應(yīng)用程序也可以使用ensureCapacity() 操作來增加 ArrayList 實(shí)例的容量膀值，這可以減少遞增式再分配的數(shù)量（就是先將其一次性擴(kuò)容，避免重復(fù)性擴(kuò)容操作）歌逢；
- 可以通過trimToSize()函數(shù)將數(shù)組大小調(diào)整到所存儲實(shí)際元素的個數(shù)大小翘狱，以減少對內(nèi)存的消耗盒蟆；
