ArrayList源碼分析主要由五部分組成，一是繼承和實(shí)現(xiàn)類，二是基本屬性，三是構(gòu)造方法，四是主要方法，五是分析與總結(jié)。
一、 ArrayList概述：
ArrayList特點(diǎn)：是基于數(shù)組實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組，其容量能自動(dòng)增長，元素有順序、可重復(fù) 、查詢快、增刪慢、線程不安全，內(nèi)部的元素可以直接通過get與set方法進(jìn)行訪問。
ArrayList繼承了AbstractList，實(shí)現(xiàn)了RandomAccess、Cloneable和Serializable接口！
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
（1）繼承AbstractList,把模板類定義成抽象類，抽象類本身不能實(shí)例化，繼承接口的實(shí)現(xiàn)類必須要實(shí)現(xiàn)接口的所有方法，而模板類僅僅是為了實(shí)現(xiàn)一些通用方法不需要實(shí)現(xiàn)所有接口方法，不會(huì)產(chǎn)生沒有實(shí)現(xiàn)的接口濫用。實(shí)現(xiàn)了代碼的最大化復(fù)用和代碼的最大化精簡(jiǎn)。
AbstractList又繼承了AbstractCollection實(shí)現(xiàn)了List接口，List提供了相關(guān)的添加、刪除、修改、遍歷等功能！
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
protected AbstractList() {
}
（2）實(shí)現(xiàn)了List接口，表明ArrayList是一個(gè)有序、可重復(fù)的數(shù)組，提供了相關(guān)的添加、刪除、修改、遍歷等功能！
（3）實(shí)現(xiàn)RandomAccess接口，提供了隨機(jī)訪問功能，是一個(gè)標(biāo)記接口，實(shí)際上就是通過下標(biāo)序號(hào)進(jìn)行快速訪問，主要目的是使算法能夠在隨機(jī)和順序訪問的list中表現(xiàn)的更加高效。
Collections下的binarySearch方法的源碼：
public static <T>int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
indexedBinarySearch是直接通過get訪問數(shù)據(jù)
iteratorBinarySearch是通過ListIterator查找響應(yīng)的元素
實(shí)現(xiàn)RandomAccess接口的的List可以通過簡(jiǎn)單的for循環(huán)來訪問數(shù)據(jù)比使用iterator訪問來的高效快速。
（4）實(shí)現(xiàn)了Cloneable接口，表明ArrayList支持克隆，即可以重寫Object.clone方法，否則在重寫clone方法時(shí)，報(bào)CloneNotSupportedException
（5）實(shí)現(xiàn)了Serializable接口可以被序列化與反序列化。
二、ArrayList的繼承關(guān)系
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.ArrayList<E>
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess
Direct Known Subclasses:
AttributeList, RoleList, RoleUnresolvedList
類中屬性
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 版本號(hào)
private static final long serialVersionUID = 8683452581122892189L;
// 缺省容量
private static final int DEFAULT_CAPACITY = 10;
// 空對(duì)象數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 缺省空對(duì)象數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素?cái)?shù)組
transient Object[] elementData;
// 實(shí)際元素大小，默認(rèn)為0
private int size;
// 最大數(shù)組容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
三、ArrayList方法（API）
// Collection中定義的API
boolean add(E object)
boolean addAll(Collection<? extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection<?> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
boolean removeAll(Collection<?> collection)
boolean retainAll(Collection<?> collection)
int size()
<T> T[] toArray(T[] array)
Object[] toArray()
// AbstractCollection中定義的API
void add(int location, E object)
boolean addAll(int location, Collection<? extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
ListIterator<E> listIterator()
E remove(int location)
E set(int location, E object)
List<E> subList(int start, int end)
// ArrayList新增的API
Object clone()
void ensureCapacity(int minimumCapacity)
void trimToSize()
void removeRange(int fromIndex, int toIndex)
四、構(gòu)造方法（有3個(gè)）
（1）無參構(gòu)造，初始化長度為0的數(shù)組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
（2）傳入int類型的值，初始化長度為自定義的數(shù)組
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);
}
}
（3）對(duì)傳入的集合元素進(jìn)行復(fù)制，構(gòu)造一個(gè)包含指定元素的列表
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
五、 主要方法解析
1. add(E e)，在元素列表的末尾插入指定的元素，返回true或者拋出異常，無其他返回值
每次添加元素之前都會(huì)判斷添加后的容量是否需要擴(kuò)容
//添加單個(gè)元素
public boolean add(E e) {
//判斷添加后的長度是否需要擴(kuò)容
ensureCapacityInternal(size + 1);
//在數(shù)組末尾添加上當(dāng)前元素，并且修改size大小
elementData[size++] = e;
return true;
}
看到它首先調(diào)用了ensureCapacityInternal()方法.注意參數(shù)是size+1,這是個(gè)面試考點(diǎn)
//集合的初始容量為10
private static final int DEFAULT_CAPACITY = 10;
//判斷是否是第一次初始化數(shù)組
private void ensureCapacityInternal(int minCapacity) {
/**
EMPTY_ELEMENTDATA是elementData 的初始化{}一個(gè)空數(shù)組，elementData是數(shù)組緩沖器，
ArrayList的元素都放在這個(gè)數(shù)組緩沖器中。
DEFAULT_CAPACITY是數(shù)組列表初始容量大小為10，ArrayList會(huì)在第一次添加元素的時(shí)候設(shè)置數(shù)組緩沖
器的初始大小為10.
**/
//判斷當(dāng)前數(shù)組是否 == EMPTY_ELEMENTDATA，因?yàn)槟J(rèn)構(gòu)造函數(shù)創(chuàng)建時(shí)是將空數(shù)組EMPTY_ELEMENTDATA賦值給elementData
if (elementData == EMPTY_ELEMENTDATA) {
//判斷默認(rèn)容量10和當(dāng)前數(shù)據(jù)長度的大小，取其中大的值作為判斷本次是否需要擴(kuò)容的依據(jù)，由于第一次數(shù)組是空的，所以默認(rèn)要使數(shù)組擴(kuò)容到10的長度
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//判斷是否需要擴(kuò)容
ensureExplicitCapacity(minCapacity);
}
這個(gè)方法里又嵌套調(diào)用了兩個(gè)方法:計(jì)算容量+確保容量
計(jì)算容量：如果elementData是空，則返回默認(rèn)容量10和size+1的最大值，否則返回size+1
計(jì)算完容量后，進(jìn)行確保容量可用：(modCount不用理它，它用來計(jì)算修改次數(shù))
如果size+1 > elementData.length證明數(shù)組已經(jīng)放滿，則增加容量，調(diào)用grow()。
//判斷擴(kuò)容的方法
private void ensureExplicitCapacity(int minCapacity) {
//如果需要擴(kuò)容modCount++，此參數(shù)是指當(dāng)前列表結(jié)構(gòu)被修改的次數(shù)
modCount++;
// 判斷當(dāng)前數(shù)據(jù)量是否大于數(shù)組的長度
if (minCapacity - elementData.length > 0)
//如果大于則進(jìn)行擴(kuò)容操作
grow(minCapacity);
}
增加容量：默認(rèn)1.5倍擴(kuò)容。
獲取當(dāng)前數(shù)組長度=>oldCapacity
oldCapacity>>1 表示將oldCapacity右移一位(位運(yùn)算)，相當(dāng)于除2。再加上1，相當(dāng)于新容量擴(kuò)容1.5倍。
如果newCapacity>1=1,1<2所以如果不處理該情況，擴(kuò)容將不能正確完成。
如果新容量比最大值還要大，則將新容量賦值為VM要求最大值。
將elementData拷貝到一個(gè)新的容量中。
// 內(nèi)部數(shù)組的容量可以擴(kuò)展到的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//擴(kuò)容方法
private void grow(int minCapacity) {
// 記錄擴(kuò)容前數(shù)組的長度
int oldCapacity = elementData.length;
//將原數(shù)組的長度擴(kuò)大0.5倍作為擴(kuò)容后新數(shù)組的長度（如果擴(kuò)容前數(shù)組長度為10，那么經(jīng)過擴(kuò)容后的數(shù)組長度應(yīng)該為15）
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果擴(kuò)容后的長度小于當(dāng)前數(shù)據(jù)量，那么就將當(dāng)前數(shù)據(jù)量的長度作為本次擴(kuò)容的長度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判斷新數(shù)組長度是否大于可分配數(shù)組的最大大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
//將擴(kuò)容長度設(shè)置為最大可用長度
newCapacity = hugeCapacity(minCapacity);
// 拷貝，擴(kuò)容，構(gòu)建一個(gè)新的數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
//判斷如果新數(shù)組長度超過當(dāng)前數(shù)組定義的最大長度時(shí)，就將擴(kuò)容長度設(shè)置為Interger.MAX_VALUE,也就是int的最大長度
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
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;
}
size+1的問題
好了，那到這里可以說一下為什么要size+1。
size+1代表的含義是：
如果集合添加元素成功后，集合中的實(shí)際元素個(gè)數(shù)。
為了確保擴(kuò)容不會(huì)出現(xiàn)錯(cuò)誤。
假如不加一處理，如果默認(rèn)size是0，則0+0>>1還是0。
如果size是1，則1+1>>1還是1。有人問:不是默認(rèn)容量大小是10嗎?事實(shí)上，jdk1.8版本以后，ArrayList的擴(kuò)容放在add()方法中。之前放在構(gòu)造方法中。我用的是1.8版本，所以默認(rèn)ArrayList arrayList = new ArrayList();后，size應(yīng)該是0.所以,size+1對(duì)擴(kuò)容來講很必要.
2. add(int index，E element)，在指定位置添加元素
// 在指定位置添加元素
public void add(int index, E element) {
// 檢測(cè)指定位置下標(biāo)是否合法，是否在列表的長度范圍內(nèi)
rangeCheckForAdd(index);
// 擴(kuò)展內(nèi)部數(shù)組的容量
ensureCapacityInternal(size + 1); // Increments modCount!!
// 分片段拷貝數(shù)組到新的列表
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 指定下標(biāo)的數(shù)組值為當(dāng)前添加的元素
elementData[index] = element;
// 長度自增長
size++;
}
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
代碼解釋:
Object src : 原數(shù)組
int srcPos : 從元數(shù)據(jù)的起始位置開始
Object dest : 目標(biāo)數(shù)組
int destPos : 目標(biāo)數(shù)組的開始起始位置
int length : 要copy的數(shù)組的長度
示例：size為6，我們調(diào)用add(2,element)方法，則會(huì)從index=2+1=3的位置開始，將數(shù)組元素替換為從index起始位置為index=2，長度為6-2=4的數(shù)據(jù)。
3. addAll(Collection<? extends E> c)，將指定集合追加到列表的末尾，返回值為true或者false，還可能拋出異常
// 在列表的結(jié)尾追加一個(gè)集合
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
// 擴(kuò)容
ensureCapacityInternal(size + numNew); // Increments modCount
// 將原數(shù)組與指定數(shù)組拼接到一起
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
4. addAll(int index, Collection<? extends E> c)，在指定位置追加指定元素列表，返回值為true或者false，還可能拋出異常
public boolean addAll(int index, Collection<? extends E> c) {
// 檢測(cè)指定位置是否合法，是否超出邊界
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
// 擴(kuò)展容量
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
// 如果指定位置在原列表之間，則分兩部分復(fù)制數(shù)組
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 如果指定位置正好在列表的位置，直接在列表尾部添加指定集合即可
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
5. remove(int index)，移除指定下標(biāo)對(duì)應(yīng)的列表元素，返回值為指定下標(biāo)對(duì)應(yīng)的列表元素
/**
*按下標(biāo)移除元素
*/
public E remove(int index) {
//先判斷index是否大于等于size，如果大于等于將報(bào)異常
rangeCheck(index);
modCount++;
//防止數(shù)組index下標(biāo)位置所指向的內(nèi)存在移動(dòng)元素的時(shí)候被占用
E oldValue = elementData(index);
//需要在elementData數(shù)組中移動(dòng)元素的長度
int numMoved = size - index - 1;
if (numMoved > 0)
//將elementData從下標(biāo)index+1開始的元素到，長度為numMoved，移除到elementData的下標(biāo)為index開始的地方
//這樣就能將elementData中下標(biāo)為index的元素覆蓋掉
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
6. remove(Object o)，移除列表中的指定元素，返回值為true或者false，也可拋出異常
public boolean remove(Object o) {
if (o == null) {
// 如果移除的指定元素為null，先找到列表中值為null的元素的下標(biāo)，然后移除元素
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 如果移除的元素不為null，先找到下標(biāo)，然后移除元素
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 用指定下標(biāo)將列表分割為兩個(gè)區(qū)域，然后撮合兩個(gè)列表成為一個(gè)新的列表，達(dá)到移除指定元素作用
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;
}
7. removeAll(Collection<?> c)，移除指定的集合元素
public boolean removeAll(Collection<?> c) {
// 采用Objects工具類，如果指定集合為null，則拋出空指針異常
Objects.requireNonNull(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) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
8. removeIf(Predicate<? super E> filter)，根據(jù)指定的篩選條件刪除指定的列表元素，這是Jdk1.8新增的方法
@Override
public boolean removeIf(Predicate<? super E> filter) {
// Objects工具類判定null操作
Objects.requireNonNull(filter);
int removeCount = 0;
// 裝載int類型的小型數(shù)組，可以理解為裝載int的列表
final BitSet removeSet = new BitSet(size);
// 因?yàn)楹竺娴谋闅v列表元素，可能有多線程同時(shí)訪問的情況，固做此標(biāo)記
final int expectedModCount = modCount;
final int size = this.size;
// 遍歷列表元素找到符合篩選條件的下標(biāo)，然后存儲(chǔ)到BitSet中
for (int i = 0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked") final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
// 上面如果有多線程同時(shí)訪問，則此處可能會(huì)報(bào)異常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
// 如果符合篩選提交的元素個(gè)數(shù)不為0，則進(jìn)行刪除操作
if (anyToRemove) {
// 移除符合篩選條件的元素后，列表的長度
final int newSize = size - removeCount;
for (int i = 0, j = 0; (i < size) && (j < newSize); i++, j++) {
// 可以參加下面的testBitSet測(cè)試分析，它表示返回的是正序排列BitSet中沒有的int類型值
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k = newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
測(cè)試BitSet類型的存儲(chǔ)，主要測(cè)試nextClearBit方法
public void testBitSet() {
// 長度為6，對(duì)應(yīng)存儲(chǔ)元素為{0,1,2,3,4,5}
BitSet removeSet = new BitSet(6);
// 如下為裝載的數(shù)據(jù)，淺綠色標(biāo)記
removeSet.set(1);
removeSet.set(0);
removeSet.set(3);
removeSet.set(5);
// 可采用如下方式，找到為裝載的數(shù)據(jù)，即為{2,4}
for (int i = 0; i < 6; i++) {
System.out.println("清除前i=" + i);
i = removeSet.nextClearBit(i);
System.out.println("清除后i=" + i);
System.out.println("-----------------");
}
}
清除前i=0
清除后i=2
-----------------
清除前i=3
清除后i=4
-----------------
清除前i=5
清除后i=6
-----------------
測(cè)試removeIf(Predicate<? super E> filter)方法
public void testRemoveIf() {
ArrayList<String> mArrayList = new ArrayList<>();
mArrayList.add("a");
mArrayList.add("b");
mArrayList.add("ab");
mArrayList.add("c");
mArrayList.add("aa");
mArrayList.add("d");
System.out.println("初始時(shí)：" + mArrayList.toString());
mArrayList.removeIf(s -> s.contains("a"));
System.out.println("過濾完：" + mArrayList.toString());
// 初始時(shí)：[a, b, ab, c, aa, d]
// 過濾完：[b, c, d]
}
9. clone()，克隆列表，是一種淺拷貝，拷貝的裝載對(duì)象的內(nèi)存地址
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
10. set(int index, E element)，用指定元素替換指定下標(biāo)的值并返回
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
11.get(int index)方法：返回指定下標(biāo)處的元素的值。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
rangeCheck(index)會(huì)檢測(cè)index值是否合法，如果合法則返回索引對(duì)應(yīng)的值。
5、總結(jié)
1：ArrayList 本質(zhì)實(shí)現(xiàn)方法是用數(shù)組！是非同步的！
2:初始化容量 = 10 ，最大容量不會(huì)超過 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8！
3：indexOf和lastIndexOf 查找元素，若元素不存在，則返回-1！
4：當(dāng)ArrayList容量不足以容納全部元素時(shí)，ArrayList會(huì)重新設(shè)置容量：新的容量=“(原始容量x3)/2 + 1”。
5：ArrayList的克隆函數(shù)，即是將全部元素克隆到一個(gè)數(shù)組中。
6：ArrayList實(shí)現(xiàn)java.io.Serializable的方式。當(dāng)寫入到輸出流時(shí)，先寫入“容量”，再依次寫入“每一個(gè)元素”；當(dāng)讀出輸入流時(shí)，先讀取“容量”，再依次讀取“每一個(gè)元素”。
7：造成ArrayList添加（add）慢的原因是什么？
當(dāng)容量不夠時(shí)，每次增加元素，使用System.arraycopy()方法將原來的元素拷貝到一個(gè)新的數(shù)組中，造成了資源的浪費(fèi)，也因此建議在事先能確定元素?cái)?shù)量的情況下，在使用ArrayList。
8：ArrayList的實(shí)現(xiàn)中大量地調(diào)用了Arrays.copyof()和System.arraycopy()方法。
9：造成ArrayList移除（remove）慢的原因是什么？
ArrayList基于數(shù)組實(shí)現(xiàn)，可以通過下標(biāo)索引直接查找到指定位置的元素，因此查找效率高，但每次根據(jù)下標(biāo)插入或刪除元素時(shí)，就需要調(diào)用System.arraycopy（）方法將下標(biāo)前數(shù)據(jù)和下標(biāo)后的數(shù)據(jù)進(jìn)行拼接并復(fù)制到新的數(shù)組里，因此插入、刪除元素的效率低。
10：在查找給定元素索引值等的方法中，源碼都將該元素的值分為null和不為null兩種情況處理，ArrayList中允許元素為null。
11：ArrayList為什么能自動(dòng)擴(kuò)展大小，不需要手動(dòng)設(shè)置大??？
ArrayList內(nèi)部采用的是Array對(duì)象存儲(chǔ)，本身該對(duì)象是需要定義長度的，所以每次添加數(shù)據(jù)的時(shí)候，都是判斷是否先擴(kuò)展容量，且容量有最大值限制，容量的大小是在原來基礎(chǔ)上擴(kuò)大1.5倍：公式（oldCapacity + oldCapacity >> 1）。
12：ArrayLIst查詢效率高：ArrayLIst是連續(xù)存放元素的，找到第一個(gè)元素的首地址，再加上每個(gè)元素的占據(jù)的字節(jié)大小就能定位到對(duì)應(yīng)的元素。
13：LinkedList插入刪除效率高。因?yàn)閳?zhí)行插入刪除操作時(shí)，只需要操作引用即可，元素不需要移動(dòng)元素，他們分布在內(nèi)存的不同地方，通過引用來互相關(guān)聯(lián)起來。而ArrayLIst需要移動(dòng)元素，故效率低。
