為了有針對性的準備面試，鎖屏面試題百日百刷開始每日從各處收集的面經(jīng)中選擇幾道經(jīng)典面試題分享并給出答案供參考，答案中會做與題目相關(guān)的擴展，并且可能會拋出一定問題供思考。這些題目我會標注具體的公司、招聘類型(校招、社招、實習)以及面試階段。這些面試題會收錄到鎖屏面試題app和小程序中并整理歸類好。其他面試題也同樣在持續(xù)更新中，多謝使用和支持。下面是今日面試題:

====ArrayList 和 LinkedList 實現(xiàn)原理和前者的擴容機制？[阿里云][校招][一面]

以下內(nèi)容均是以jdk1.8來講:

ArrayList實現(xiàn)原理:

Arraylist底層是用一個Object數(shù)組elementData來保存數(shù)據(jù)的:

transient Object[] elementData; // non-private to simplify nested class access

從創(chuàng)建一個ArrayList開始看，一般都是通過new即通過構(gòu)造函數(shù)來創(chuàng)建一個ArrayList看源碼:

很簡單，無非就是無參構(gòu)造只會創(chuàng)建一個空的數(shù)組，帶初始化數(shù)組大小的構(gòu)造器會創(chuàng)建一個知道容量的ArrayList,以及用另一個ArrayList初始化新的ArrayList的構(gòu)造函數(shù)。

再看ArrayList的操作:

1)添加:

這里，modCount是我們每次對ArrayList做改變大小的時候會做一次自增操作的變量，記錄下修改次數(shù)。核心的常問的一個方法就是這個grow()方法，這是當ArrayList中元素的數(shù)組(上面講到的存儲數(shù)據(jù)的)elementData容量不夠時做的擴容操作。這里我們以用空參構(gòu)造器創(chuàng)建ArrayList時，第一次向ArrayList添加元素時會做一次擴容操作來講:

判斷容量是否足夠的就是這么一句:if (minCapacity - elementData.length > 0)

在grow中，核心的一段就是int newCapacity = oldCapacity + (oldCapacity >> 1);新的容量是舊的容量的1.5倍(oldCapacity >> 1實際上是一次oldCapacity除2操作)

注意這里擴容觸發(fā)條件是在使用無參構(gòu)造器第一次添加元素，以及添加元素時，判斷發(fā)現(xiàn)數(shù)組長度不夠時。

2)?刪除：

看代碼很簡單，就是做一次數(shù)組復(fù)制，移動要刪除的某一位置元素的后面的元素，并且將舊數(shù)組置為null做垃圾回收。指定remove(Object O)這個方法也是先找對應(yīng)元素的下標，然后做與上面代碼差不多的操作。有興趣的可以看下源碼。

查詢就沒啥好講的了，底層是數(shù)組存儲，查詢很容易做到?？勺孕锌丛创a。

LinkedList實現(xiàn)原理:

LinkedList存儲是通過雙向鏈表實現(xiàn)的:

它的空參構(gòu)造不做任何操作，帶參構(gòu)造LinkedList(Collection<? extends E> c)也是著重體現(xiàn)在添加元素的操作，所以直接講它的一些操作，這里需要大家能夠懂鏈表的增刪改查的操作，因為LinkedList的這些操作就是根據(jù)這些來的。希望大家能夠找一下資料了解下，這里篇幅有限，不作講解。

1)?添加：

頭部添加:

看下上面關(guān)于LinkedList一開始講的，可以看到LinkedList成員變量就有保存first和last，這里從頭部插入和從尾部插入基本上操作一致，只是保存位置不同，看代碼很容易看懂，就是對鏈表的操作，至于add()方法是在尾部插入新的元素。

2)?刪除

removeFirst()和removeLast()以及remove()(remove和removeFirst()操作一致)，都是簡單去鏈表表頭或表尾的操作，可以自己看源碼，熟悉鏈表操作的同學很容易就能看懂，不作贅述。說一說remove(int index)：

這里是先根據(jù)index找到LinkedList中存儲的節(jié)點，見上圖node()方法，然后開始刪除元素操作，見unlink()方法，熟悉鏈表的刪除操作，很容易能看懂，判斷刪除的元素是否是表頭后表尾，是的話簡單的賦值一下即可，不是的話做相應(yīng)的刪除操作。Remove(Object o)這個方法也是先找到這個list中是否有這個元素，先通過查找，再調(diào)用unlink()方法刪除。

3）查找

LinkedList查找操作在上面的刪除操作中，先查找在做刪除的步驟中已經(jīng)講過(上面的node方法)，請自行對照源碼查看查找操作。

更多面試題或?qū)W習資源可查看我主頁或評論獲取