ArrayList 概述
自己的理解，數(shù)據結構的出現(xiàn)必定是伴隨的原有的數(shù)據結構進行升級而出現(xiàn)的。為什么會有arraylist呢？然后arraylist是一種以數(shù)組為底層的數(shù)據結構。那么數(shù)組的大小是不可變的，但是實際運用中我們經常要求可以改變，所以就衍生出arraylist這種集合。
ArrayList的基本特點
1.ArrayList 底層是一個動態(tài)擴容的數(shù)組結構
2.允許存放（不止一個） null 元素（hashmap只允許有一個null元素，hashtable不允許null元素）
3.允許存放重復數(shù)據，存儲順序按照元素的添加順序
4.ArrayList 并不是一個線程安全的集合。如果集合的增刪操作需要保證線程的安全性，可以考慮使用CopyOnWriteArrayList或者使用collections.synchronizedList(List l)函數(shù)返回一個線程安全的ArrayList類.
擴容機制&add方法
由于arrayList是長度可變的，也就是說如果存放的元素大于數(shù)組長度就會進行擴容，那么擴容機制必定是伴隨的add增加元素的方法進行的，我們來讀一讀arraylist中的add方法。
1.首先調用 ensureCapacityInternal方法，參數(shù)樹size+1，也就是判斷如果要添加這個元素，那么數(shù)組的元素就變成了size+1，是否可以存放的下呢？
2.判斷數(shù)組是否為空，由于構造函數(shù)中如果是無參構造函數(shù)那么就會創(chuàng)建一個空的數(shù)組，如果是空的數(shù)組的話，就會將默認數(shù)組大小為10。然后進行調用擴容判斷。
這里要注意的是為什么會有modcount這個變量呢？ 可以查閱資料，會發(fā)現(xiàn)原來他是迭代器中的一個變量，為什么arraylist是線程不安全的呢?其實可以這么認為含有modcount 的集合都是線程不安全的，因為如果我們在遍歷的時候去修改數(shù)組就會導致線程不安全。如果這個集合進行了修改變動的話，modcount都必須要改變，所以modcount含義就是集合變動次數(shù)。是迭代器中的一種fail-fast機制。
3.如果數(shù)組的元素個數(shù)大于數(shù)組的長度就要進行擴容。
由此看來 ArrayList 的擴容機制的知識點一共又兩個
1.每次擴容的大小為原來大小的 1.5倍 （當然這里沒有包含 1.5倍后大于 MAX_ARRAY_SIZE 的情況）
2.擴容的過程其實是一個將原來元素拷貝到一個擴容后數(shù)組大小的長度新數(shù)組中。所以 ArrayList 的擴容其實是相對來說比較消耗性能的。
迭代器
迭代器?Iterator?模式是用于遍歷各種集合類的標準訪問方法。它可以把訪問邏輯從不同類型的集合類中抽象出來，從而避免向客戶端暴露集合的內部結構。
ArrayList底層是使用數(shù)組進行實現(xiàn)的，在使用下標進行訪問時可以做到o(1)的時間復雜度，但是在進行插入刪除時需要移動元素，同時當ArrayList底層數(shù)組空間不足時，需要擴充容量，（默認擴大為原來的1.5倍），這會進行元素的重新拷貝，所以不適合于頻繁進行插入刪除操作的情況。其擴容是用到System.arraycopy(a, 0, elementData, size, numNew);這么一個方法，也就是會新建一個數(shù)組然后進行復制。
總結：
1.ArrayList 底層是一個動態(tài)擴容的數(shù)組結構,每次擴容需要增加1.5倍的容量
2.ArrayList 擴容底層是通過Arrays.CopyOf和System.arraycopy來實現(xiàn)的。每次都會產生新的數(shù)組，和數(shù)組中內容的拷貝，所以會耗費性能，所以在多增刪的操作的情況可優(yōu)先考慮 LinkList 而不是 ArrayList。
3.ArrayList 的 toArray 方法重載方法的使用。
4.允許存放（不止一個） null 元素，
5.允許存放重復數(shù)據，存儲順序按照元素的添加順序
6.ArrayList 并不是一個線程安全的集合。如果集合的增刪操作需要保證線程的安全性，可以考慮使用CopyOnWriteArrayList或者使collections.synchronizedList(List l)函數(shù)返回一個線程安全的ArrayList類.
ArrayList集合知識點總結
ArrayList是一個動態(tài)數(shù)組，查詢快、增刪慢。ArrayList是線程不安全的，運行效率快，允許元素為null。
1.?ArrayList與LinkedList的區(qū)別有哪些？
答：ArrayList的底層數(shù)據結構為數(shù)組，增刪慢、查詢快，線程不安全，效率高。
LinkedList的底層數(shù)據結構為鏈表，增刪快、查詢慢，線程不安全，效率高。
2.?ArrayList與Vector的區(qū)別？
答：Vector底層數(shù)據結構為數(shù)組，增刪慢、查詢快，線程安全，效率低，每次擴容為原來數(shù)組的2倍。
ArrayList底層數(shù)據結構為數(shù)組，增刪慢、查詢快，線程不安全，效率高，每次擴容為原來數(shù)組的1.5倍。
3.?ArrayList的底層是數(shù)組，數(shù)組的名稱是什么？類型是什么？
答：名稱是elementData，類型是Object[]，所以ArrayList里面可以存放任意類型的元素。
4.?ArrayList底層數(shù)組的默認初始化容量是多少？當超出這個大小時，每次擴容是多少？
答：默認初始化容量是10。當超出這個大小時，每次擴容1.5倍。
5.?LinkedList的底層是什么？
答：雙向鏈表。（hashmap是使用單向鏈表）
6.?ArrayList里面可以存null嗎？
答：可以。
7.?ArrayList的底層是數(shù)組，它和數(shù)組有什么區(qū)別嗎？
答：ArrayList區(qū)別于數(shù)組的地方在于能夠自動擴展大小，每次擴容1.5倍。
8.?當向ArrayList集合中添加元素時需要調用add()方法，add()方法的執(zhí)行流程是怎樣的？
答：調用add()方法時，add()方法首先調用ensureCapacityInternal()來判斷elementData數(shù)組容量是否足夠，ensureCapacityInternal()之所以能夠判斷，是因為它內部調用了ensureExplicitCapacity()方法，這個方法才是真正判斷elementData數(shù)組容量是否夠用的關鍵方法。如果容量足夠，則直接將元素添加到ArrayList中；如果容量不夠，則ensureExplicityCapacity()方法內部會調用grow()方法來對數(shù)組進行擴容。擴容成功之后，再將元素添加到ArrayList擴容之后的新數(shù)組中。
注意：如何擴容呢？會先創(chuàng)建一個原來數(shù)組1.5倍大小的新數(shù)組，然后將數(shù)據拷貝到新數(shù)組中。
9.?在調用ArrayList的remove(int index)方法時，執(zhí)行流程是怎樣的？
答：首先判斷index是否合理，如果合理的話，會調用System.arraycopy()方法把指定下標到數(shù)組末尾的元素向前移動一個單位，并且會把數(shù)組最后一個元素設為null。這樣是為了方便GC回收。
10.?ArrayList在調用get(int index)方法查詢的時候，執(zhí)行流程是怎樣的？
答：首先判斷index是否合理，然后調用elementData()方法，elementData()方法返回根據index查到的具體的元素。注意：這里的返回值都經過了向下轉型（Object -> E）。
11.?ArrayList的大小是如何自動增加的？你能分享一下你的代碼嗎？
答：當向ArrayList中增加一個對象的時候，Java首先會判斷ArrayList的底層數(shù)組elementData是否還有足夠的空間來存儲這個對象，如果有，就直接存，如果沒有，就會基于原有的數(shù)組擴容出一個1.5倍的新數(shù)組，并將數(shù)據全部復制到新數(shù)組中。
請注意這樣一個情況，新建了一個數(shù)組，舊數(shù)組的對象被復制到了新的數(shù)組中，并且現(xiàn)有的數(shù)組引用指向新的數(shù)組。
12.?什么情況下你會使用ArrayList？什么情況下你會選擇LinkedList？
答：當對數(shù)據的主要操作為索引或只在集合的末端增加、刪除數(shù)據時，使用ArrayList效率比較高；當對數(shù)據的操作主要為指定位置的插入或刪除操作時，使用LinkedList效率比較高。
13.?在ArrayList的增、刪、改、查中，什么地方會修改modCount？
答：增如果導致擴容，則會修改modCount；刪一定會修改modCount；改和查一定不會修改modCount。
14.?為什么ArrayList在增、刪的時候效率低？
答：因為在增、刪的過程中會涉及到數(shù)組的復制，效率低。
15.?ArrayList的時間復雜度是多少？
答：當修改、查詢或者只在數(shù)組末尾增、刪時，時間復雜度為O(1)；對指定位置的元素進行增、刪時，時間復雜度為O(n)。
