本文提到的實現(xiàn)均是基于jdk 1.8壕鹉，其他版本可能不同剃幌。 如果文章有錯的地方歡迎指正，大家互相交流 , 歡迎評論大家一起討論技術(shù)晾浴。
一负乡、數(shù)組和鏈表介紹
數(shù)組和鏈表是兩種基本的數(shù)據(jù)結(jié)構(gòu)，雖然均是作為線性的數(shù)據(jù)結(jié)構(gòu)脊凰，但是在內(nèi)存存儲上的表現(xiàn)不一樣抖棘，所以也有各自的特點。
1.1狸涌、數(shù)組的特點
在內(nèi)存中切省，數(shù)組是一塊連續(xù)的區(qū)域。對內(nèi)存要求較高帕胆，因為只能分配連續(xù)的內(nèi)存空間朝捆，零碎的內(nèi)存空間小于數(shù)組申請的空間時利用不上。
數(shù)組需要預(yù)留空間懒豹，在使用前要先申請占內(nèi)存的大小芙盘，可能會浪費內(nèi)存空間驯用。
插入數(shù)據(jù)和刪除數(shù)據(jù)效率低，插入數(shù)據(jù)時儒老，這個位置后面的數(shù)據(jù)在內(nèi)存中都要向后移蝴乔。刪除數(shù)據(jù)時，這個數(shù)據(jù)后面的數(shù)據(jù)都要往前移動驮樊。
隨機讀取效率很高淘这。因為數(shù)組是連續(xù)的，知道每一個數(shù)據(jù)的內(nèi)存地址巩剖，可以直接找到給定地址的數(shù)據(jù)铝穷。
不利于擴展，數(shù)組定義的空間不夠時要重新定義數(shù)組
1.2佳魔、鏈表的特點
在內(nèi)存中可以存在任何地方曙聂，不要求連續(xù)。
每一個數(shù)據(jù)都保存了下一個數(shù)據(jù)的內(nèi)存地址鞠鲜，通過這個地址找到下一個數(shù)據(jù)宁脊。
增加數(shù)據(jù)和刪除數(shù)據(jù)很容易。 因為只需要將下一個數(shù)據(jù)的地址修改一下就好贤姆，不用像數(shù)組要移動數(shù)據(jù)榆苞。
查找數(shù)據(jù)時效率低，因為不具有隨機訪問性霞捡，所以訪問某個位置的數(shù)據(jù)都要從第一個數(shù)據(jù)開始訪問坐漏，然后根據(jù)第一個數(shù)據(jù)保存的下一個數(shù)據(jù)的地址找到第二個數(shù)據(jù)，以此類推碧信。要找到第三個人赊琳，必須從第一個人開始問起。
不指定大小砰碴，擴展方便躏筏。鏈表大小不用定義，數(shù)據(jù)隨意增刪呈枉。
1.3趁尼、數(shù)組和鏈表總結(jié)
數(shù)組的優(yōu)點
- 隨機訪問性強、查找速度快（要說明的是這指的是通過下標訪問猖辫，而如果要通過數(shù)據(jù)值來范圍酥泞，也是跟鏈表一樣需要遍歷數(shù)組的）
數(shù)組的缺點
插入和刪除效率低
可能浪費內(nèi)存
內(nèi)存空間要求高，必須有足夠的連續(xù)內(nèi)存空間
數(shù)組大小固定住册，不能動態(tài)拓展
鏈表的優(yōu)點
插入刪除速度快
內(nèi)存利用率高婶博，不會浪費內(nèi)存
大小沒有固定，拓展很靈活
鏈表的缺點
- 不能隨機查找，必須從第一個開始遍歷凡人，查找效率低
建議
對性能不敏感時名党，隨便用哪個都可以，但是對性能有要求時挠轴，隨機訪問多新增刪除少時建議用數(shù)組传睹，相反，建議用鏈表
二岸晦、Collection集合體系的繼承樹
三欧啤、ArrayList源碼賞析
3.1、插入元素启上，賞析擴容
ArrayList的底層實現(xiàn)是數(shù)組，而數(shù)組長度是固定的冈在，ArrayList長度卻是可變長的倒慧，其實ArrayList底層用的是擴容的手段，簡單來說就是當容量不夠時包券，將元素拷貝到一個長度更長的新數(shù)組纫谅。
所以ArrayList在插入元素時，先做的是數(shù)組擴容溅固，因為新增一個元素付秕，所以minCapacity = size+1，如果是第一次插入侍郭，則minCapacity默認為10询吴，意思是ArrayList不可能一個一個的擴容，因為容量擴展的開銷太大呀励幼，若minCapacity > 當前的容量時才會進行擴容汰寓，否則不需要擴容直接插入元素即可。到這里苹粟，我們可以得知minCapacity 可以理解成客戶端本次插入元素需要的最小容量的意思。minCapacity 其實也不是最終要擴容的數(shù)量跃闹，因為這只是客戶端要求存放元素的最少容量嵌削，可是ArrayList也有自己的原則，它默認擴容0.5倍望艺，若minCapacity 較大將按minCapacity 來擴容苛秕，否則就是擴容0.5倍。
3.2找默、移除元素艇劫，賞析對象回收細節(jié)
第505行：elementData[--size] = null; // clear to let GC do its work惩激，主動斷開了棧與堆的連接店煞，之后該對象就失去了引用蟹演，GC才能進行回收，不然沒用的對象一直占用內(nèi)存可能會導(dǎo)致內(nèi)存溢出與內(nèi)存泄露顷蟀。
3.3酒请、總結(jié)及建議
ArrayList的底層實現(xiàn)原理相對不難，難點主要是擴容鸣个。雖然每次擴容默認增大0.5倍羞反，但是擴容涉及到元素復(fù)制到新數(shù)組，開銷是比較大的囤萤。所以建議：
當預(yù)計到插入元素較多時昼窗，在實例化時利用public ArrayList(int initialCapacity)構(gòu)造函數(shù)指定初始容量，若是在插入元素的過程中才知道接下來插入元素操作頻繁涛舍，可以用public void ensureCapacity(int minCapacity)方法擴容膏秫。
四、Vector與ArrayList的區(qū)別
Vector是jdk1.2的類了做盅，比較老舊的一個集合類缤削。
Vector底層也是數(shù)組，實現(xiàn)原理跟ArrayList幾乎一樣吹榴，與ArrayList最大的區(qū)別就是：同步(線程安全)
還有個區(qū)別ArrayList在底層數(shù)組不夠用時在原來的基礎(chǔ)上擴展0.5倍亭敢，Vector是擴展1倍。
Vector是同步的图筹，我們可以從方法上就可以看得出來~
五帅刀、LinkedList實現(xiàn)原理
該LinkedList內(nèi)部類，就是ArrayList的節(jié)點類远剩。根據(jù)屬性扣溺，可以猜到LinkedList的底層實現(xiàn)應(yīng)該是個雙向鏈表，沒錯瓜晤，就是雙向鏈表锥余。
知道了節(jié)點對象后，只要懂得鏈表的知識痢掠，加上邏輯思維能力驱犹，自己實現(xiàn)一個簡單的LinkedList應(yīng)該不是難事，所以LinkedList就不多說了足画。
最后雄驹，要補充一下的就是：從上面的Collection繼承樹中可以看到，LinkedList除了實現(xiàn)List接口外淹辞，還實現(xiàn)了Deque接口医舆，Deque接口是個雙向隊列。因此，LinkedList除了能夠存放元素外蔬将，還可以實現(xiàn)隊列和棧的功能爷速，可謂是一個功能強大的類。
六娃胆、總結(jié)
其實集合的源碼看起來并不是很困難遍希，遇到問題可以翻一翻，應(yīng)該是能夠看懂的里烦。
ArrayList凿蒜、LinkedList、Vector算是在面試題中比較常見的的知識點了胁黑。下面我就來做一個簡單的總結(jié)：
ArrayList
底層實現(xiàn)是數(shù)組
ArrayList的默認初始化容量是10废封，每次擴容時候增加原先容量的一半，也就是變?yōu)樵瓉淼?.5倍
在增刪時候丧蘸，需要數(shù)組的拷貝復(fù)制(navite 方法由C/C++實現(xiàn))
LinkedList
底層實現(xiàn)是雙向鏈表[雙向鏈表方便實現(xiàn)往前遍歷]
Vector
底層是數(shù)組漂洋，現(xiàn)在已少用，被ArrayList替代力喷，原因有兩個：
Vector所有方法都是同步刽漂，有性能損失。
Vector初始length是10 超過length時 以100%比率增長弟孟，相比于ArrayList更多消耗內(nèi)存**贝咙。**
總的來說：查詢多用ArrayList，增刪多用LinkedList拂募。
