一、ArrayList的數據結構
ArrayList底層的數據結構就是數組，數組元素類型為Object類型，即可以存放所有類型數據。我們對ArrayList類的實例的所有的操作(增刪改查等)，其底層都是基于數組的。
定義底層數據結構：Object[] 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 == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access
===The capacity of the ArrayList is the length of this array buffer. ===
注釋中這句話的意思是ArrayList的capacity即容量是數組elementData的長度。capacity = elementData.length，而不是arrayList.size()。
===Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added.===
注釋中這句話的意思是當通過如：List<String> dataList = new ArrayList<>();創建ArrayList的一個對象時，此時該dataList是沒有被定義容量的，當add第一個元素的時候，此時才將dataList的容量設置為?DEFAULT_CAPACITY即10.
舉例說明：
因為ArrayList中數組elementData的屬性是default，所以我們通過反射來獲取數組的長度即capacity。
public class Test {public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {List<String> dataList = new ArrayList<>();//初始化時獲取ArrayList的capacityint arrayListCapacity = getArrayListCapacity(dataList);System.out.println("初始化時ArrayList的capacity：" + arrayListCapacity);dataList.add("zhangsan");//添加第一個元素初始化時獲取ArrayList的capacityint arrayListCapacity1 = getArrayListCapacity(dataList);System.out.println("add第一個元素后ArrayList的capacity：" + arrayListCapacity1);}/*** 反射獲取ArrayList的容量capacity* @param arrayList* @return* @throws NoSuchFieldException* @throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {Class<ArrayList> arrayListClass = ArrayList.class;Field elementData = arrayListClass.getDeclaredField("elementData");elementData.setAccessible(true);Object[] objects = (Object[]) elementData.get(arrayList);return objects.length;} }
結果：
初始化時ArrayList的capacity：0
add第一個元素后ArrayList的capacity：10 ?二、ArrayList的屬性
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{// 版本號private static final long serialVersionUID = 8683452581122892189L;// 缺省容量private static final int DEFAULT_CAPACITY = 10;// 空對象數組private static final Object[] EMPTY_ELEMENTDATA = {};// 缺省空對象數組private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 元素數組transient Object[] elementData;// 實際元素大小，默認為0private int size;// 最大數組容量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; }
ArrayList類的屬性中核心的屬性為elementData，類型為Object[]，用于存放實際元素，并且被標記為transient，也就意味著在序列化的時候，此字段是不會被序列化的。
三、ArrayList的構造函數
public ArrayList()型構造函數
/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
構造一個空的arrayList對象，初始容量為10。（該初始容量也是add第一個元素的時候設置的）。
public ArrayList(int initialCapacity)型構造函數
/*** 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) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
構造一個空的arrayList對象，并指定初始容量，不允許初始容量小于0，否則拋出異常。
public ArrayList(Collection<? extends E> c)型構造函數
/*** 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();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;}}
舉例說明：
public class Test {private static int size;public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {List<String> dataList = new ArrayList<>();dataList.add("zhangsan");dataList.add("lisi");dataList.add("wangwu");System.out.println("傳入的參數dataList的大小: " + dataList.size());List<String> dataList2 = new ArrayList<>(dataList);System.out.println("new ArrayList<>(dataList)的元素: " + dataList2);int arrayListCapacity = getArrayListCapacity(dataList2);System.out.println("new ArrayList<>(dataList)的capacity: " + arrayListCapacity);}/*** 反射獲取ArrayList的容量capacity* @param arrayList* @return* @throws NoSuchFieldException* @throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {Class<ArrayList> arrayListClass = ArrayList.class;Field elementData = arrayListClass.getDeclaredField("elementData");elementData.setAccessible(true);Object[] objects = (Object[]) elementData.get(arrayList);return objects.length;} }
結果：
傳入的參數dataList的大小: 3 new ArrayList<>(dataList)的元素: [zhangsan, lisi, wangwu] new ArrayList<>(dataList)的capacity: 3
此種構造方法得到的arrayList的capacity為傳入collection的size。
四、ArrayList的增刪改查
1、增：add
public class TestArrayList {public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {List<String> dataList = new ArrayList<>();int arrayListCapacity = getArrayListCapacity(dataList);System.out.println("未添加元素在時capacity：" + arrayListCapacity);dataList.add("zhangsan1");int arrayListCapacity1 = getArrayListCapacity(dataList);System.out.println("add第一個元素在時capacity：" + arrayListCapacity1);dataList.add("zhangsan2");dataList.add("zhangsan3");dataList.add("zhangsan4");dataList.add("zhangsan5");dataList.add("zhangsan6");dataList.add("zhangsan7");dataList.add("zhangsan8");dataList.add("zhangsan9");dataList.add("zhangsan10");int arrayListCapacity2 = getArrayListCapacity(dataList);System.out.println("add第十個元素在時capacity：" + arrayListCapacity2);dataList.add("zhangsan11");int arrayListCapacity3 = getArrayListCapacity(dataList);System.out.println("add第十一個元素在時capacity：" + arrayListCapacity3);}/*** 反射獲取ArrayList的容量capacity* @param arrayList* @return* @throws NoSuchFieldException* @throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {Class<ArrayList> arrayListClass = ArrayList.class;Field elementData = arrayListClass.getDeclaredField("elementData");elementData.setAccessible(true);Object[] objects = (Object[]) elementData.get(arrayList);return objects.length;} }
結果：
未添加元素在時capacity：0 add第一個元素在時capacity：10 add第十個元素在時capacity：10 add第十一個元素在時capacity：15
結合以上，在添加第一個元素時進行了擴容，capacity為10。當添加第十一個元素時，此時容量為10，已不夠用，又進行了擴容，capacity為15。
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;}
ensureCapacityInternal函數確保elemenData數組有合適的大小。指定minCapacity大小
private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}
ensureExplicitCapacity函數判斷是否需要擴容。當arrayList所需的最小容量minCapacity大于當前數組elementData的長度時，就需要擴容了。
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}
真正的擴容方法grow。
拷貝擴容：Arrays.copyOf(elementData, newCapacity)；根據newCapacity構建一個新的數組，并將原數組elementData的數組復制到新數組中。最后將新的數組賦值給原數組。
/*** 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 codeint 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);}
========int newCapacity = oldCapacity + (oldCapacity >> 1);=========
正常情況下會擴容1.5倍，特殊情況下（新擴展數組大小已經達到了最大值）則只取最大值。
增（插入）：add(int index,E element)
舉例：
?
public class Test {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("zhangsan1");list.add("zhangsan2");list.add("zhangsan3");list.add("zhangsan4");System.out.println("list before add===" + list);list.add(1,"zhaoliu");System.out.println("list after add====" + list);} }
?
結果：
list before add===[zhangsan1, zhangsan2, zhangsan3, zhangsan4]
list after add====[zhangsan1, zhaoliu, zhangsan2, zhangsan3, zhangsan4] 源碼分析：類似于下面的remove，都涉及到元素的移動。
/*** Inserts the specified element at the specified position in this* list. Shifts the element currently at that position (if any) and* any subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/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++;}
?
2、刪：remove
舉例：
public class TestArrayList {public static void main(String[] args) {List<String> dataList = new ArrayList<>();dataList.add("zhangsan");dataList.add("lisi");dataList.add("wangwu");dataList.add("zhaoliu");System.out.println(dataList);dataList.remove(1);System.out.println(dataList);} }
結果：
[zhangsan, lisi, wangwu, zhaoliu]
[zhangsan, wangwu, zhaoliu] remove源碼：
/*** 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 workreturn oldValue;}
解釋說明：
對索引進行校驗后，判斷刪除后需要移動的個數，本例中刪除索引1的元素，需要移動索引2，3即兩個元素
移動元素，使用的是System.arraycopy(Object src, int srcPos,Object dest, int destPos,int length)方法。
原數組
[zhangsan, lisi, wangwu, zhaoliu]
變成
[zhangsan, wangwu, zhaoliu, zhaoliu]
最后?elementData[--size] = null 將最后一個元素置為null。此時的size為3，即將element[3]置為null，顯示如下：
[zhangsan, wangwu, zhaoliu]
=========注意這句注釋：clear to let GC do its work==========
說明：置空原尾部數據 不再強引用, 可以GC掉（引用為null）
3、改：set
舉例：
public class TestArrayList {public static void main(String[] args) {List<String> dataList = new ArrayList<>();dataList.add("zhangsan");dataList.add("lisi");dataList.add("wangwu");dataList.add("zhaoliu");System.out.println(dataList);dataList.set(3,"zl");System.out.println(dataList);} }
結果：
[zhangsan, lisi, wangwu, zhaoliu]
[zhangsan, lisi, wangwu, zl] set源碼：
/*** Replaces the element at the specified position in this list with* the specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}
判讀所給索引是否在arrayList的size之內，否則拋出?IndexOutOfBoundsException異常。
/*** Checks if the given index is in range. If not, throws an appropriate* runtime exception. This method does *not* check if the index is* negative: It is always used immediately prior to an array access,* which throws an ArrayIndexOutOfBoundsException if index is negative.*/private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
? 4、查：get
舉例說明：
public class TestArrayList {public static void main(String[] args){List<String> dataList = new ArrayList<>();dataList.add("zhangsan");dataList.add("lisi");dataList.add("wangwu");dataList.add("zhaoliu");System.out.println(dataList.get(3));} }
結果：
zhaoliu
get源碼：
/*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {rangeCheck(index);return elementData(index);}
? 可以看到，ArrayList的增、刪都涉及到元素的移動，當元素數量比較多的時候，效率相對就會降低。但是改、查不涉及到元素的移動，根據索引值直接定位，效率比較高。
五、總結
1、ArrayList的優缺點：
從上面的幾個過程總結一下ArrayList的優缺點。ArrayList的優點如下：
1、ArrayList底層以數組實現，是一種隨機訪問模式，再加上它實現了RandomAccess接口，因此查找也就是get的時候非常快
2、ArrayList在順序添加一個元素的時候非常方便，只是往數組里面添加了一個元素而已
不過ArrayList的缺點也十分明顯：
1、刪除元素的時候，涉及到一次元素復制，如果要復制的元素很多，那么就會比較耗費性能
2、插入元素的時候，涉及到一次元素復制，如果要復制的元素很多，那么就會比較耗費性能
因此，ArrayList比較適合順序添加、隨機訪問的場景。
2、ArrayList和Vector的區別
Vector，它是ArrayList的線程安全版本，其實現90%和ArrayList都完全一樣，區別在于：
1、Vector是線程安全的，ArrayList是線程非安全的
2、Vector可以指定增長因子，如果該增長因子指定了，那么擴容的時候會每次新的數組大小會在原數組的大小基礎上加上增長因子；如果不指定增長因子，那么就給原數組大小*2，源碼如下：
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);
參考資料：
https://blog.csdn.net/hrbeuwhw/article/details/79435934? ??集合間關系圖
https://www.cnblogs.com/leesf456/p/5308358.html
https://www.cnblogs.com/xrq730/p/4989451.html
)
)
的處理方式)
