## 07 List 源碼會問哪些面試題 > 勤學如春起之苗，不見其增，日有所長。 > ——陶潛 ## 引導語 List 作為工作中最常見的集合類型，在面試過程中，也是經常會被問到各種各樣的面試題，一般來說，只要你看過源碼，心中對 List 的總體結構和細節有所了解的話，基本問題都不大。 ## 1 面試題 ### 1.1 說說你自己對 ArrayList 的理解？ 很多面試官喜歡這樣子開頭，考察面試同學對 ArrayList 有沒有總結經驗，介于 ArrayList 內容很多，建議先回答總體架構，再從某個細節出發作為突破口，比如這樣： ArrayList 底層數據結構是個數組，其 API 都做了一層對數組底層訪問的封裝，比如說 add 方法的過程是……（這里可以引用我們在 ArrayList 源碼解析中 add 的過程）。 一般面試官看你回答得井井有條，并且沒啥漏洞的話，基本就不會深究了，這樣面試的主動權就掌握在自己手里面了，如果你回答得支支吾吾，那么面試官可能就會開啟自己面試的套路了。 說說你自己對 LinkedList 的理解也是同樣套路。 ### 1.2 擴容類問題 #### 1.2.1 ArrayList 無參數構造器構造，現在 add 一個值進去，此時數組的大小是多少，下一次擴容前最大可用大小是多少？ 答：此處數組的大小是 1，下一次擴容前最大可用大小是 10，因為 ArrayList 第一次擴容時，是有默認值的，默認值是 10，在第一次 add 一個值進去時，數組的可用大小被擴容到 10 了。 #### 1.2.2 如果我連續往 list 里面新增值，增加到第 11 個的時候，數組的大小是多少？ 答：這里的考查點就是擴容的公式，當增加到 11 的時候，此時我們希望數組的大小為 11，但實際上數組的最大容量只有 10，不夠了就需要擴容，擴容的公式是：oldCapacity + (oldCapacity>> 1)，oldCapacity 表示數組現有大小，目前場景計算公式是：10 + 10 ／2 = 15，然后我們發現 15 已經夠用了，所以數組的大小會被擴容到 15。 #### 1.2.3 數組初始化，被加入一個值后，如果我使用 addAll 方法，一下子加入 15 個值，那么最終數組的大小是多少？ 答：第一題中我們已經計算出來數組在加入一個值后，實際大小是 1，最大可用大小是 10 ，現在需要一下子加入 15 個值，那我們期望數組的大小值就是 16，此時數組最大可用大小只有 10，明顯不夠，需要擴容，擴容后的大小是：10 + 10 ／2 = 15，這時候發現擴容后的大小仍然不到我們期望的值 16，這時候源碼中有一種策略如下： ~~~java // newCapacity 本次擴容的大小，minCapacity 我們期望的數組最小大小 // 如果擴容后的值 < 我們的期望值，我們的期望值就等于本次擴容的大小 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; ~~~ 所以最終數組擴容后的大小為 16。 #### 1.2.4 現在我有一個很大的數組需要拷貝，原數組大小是 5k，請問如何快速拷貝？ 答：因為原數組比較大，如果新建新數組的時候，不指定數組大小的話，就會頻繁擴容，頻繁擴容就會有大量拷貝的工作，造成拷貝的性能低下，所以回答說新建數組時，指定新數組的大小為 5k 即可。 #### 1.2.5 為什么說擴容會消耗性能？ 答：擴容底層使用的是 System.arraycopy 方法，會把原數組的數據全部拷貝到新數組上，所以性能消耗比較嚴重。 #### 1.2.6 源碼擴容過程有什么值得借鑒的地方？ 答：有兩點： * 是擴容的思想值得學習，通過自動擴容的方式，讓使用者不用關心底層數據結構的變化，封裝得很好，1.5 倍的擴容速度，可以讓擴容速度在前期緩慢上升，在后期增速較快，大部分工作中要求數組的值并不是很大，所以前期增長緩慢有利于節省資源，在后期增速較快時，也可快速擴容。 * 擴容過程中，有數組大小溢出的意識，比如要求擴容后的數組大小，不能小于 0，不能大于 Integer 的最大值。 這兩點在我們平時設計和寫代碼時都可以借鑒。 ### 2 刪除類問題 #### 2.1 有一個 ArrayList，數據是 2、3、3、3、4，中間有三個 3，現在我通過 for (int i=0;i<list.size ();i++) 的方式，想把值是 3 的元素刪除，請問可以刪除干凈么？最終刪除的結果是什么，為什么？刪除代碼如下： ~~~java List<String> list = new ArrayList<String>() {{ add("2"); add("3"); add("3"); add("3"); add("4"); }}; for (int i = 0; i < list.size(); i++) { if (list.get(i).equals("3")) { list.remove(i); } } ~~~ 答：不能刪除干凈，最終刪除的結果是 2、3、4，有一個 3 刪除不掉，原因我們看下圖： 從圖中我們可以看到，每次刪除一個元素后，該元素后面的元素就會往前移動，而此時循環的 i 在不斷地增長，最終會使每次刪除 3 的后一個 3 被遺漏，導致刪除不掉。 #### 2.2 還是上面的 ArrayList 數組，我們通過增強 for 循環進行刪除，可以么？ 答：不可以，會報錯。因為增強 for 循環過程其實調用的就是迭代器的 next () 方法，當你調用 list#remove () 方法進行刪除時，modCount 的值會 +1，而這時候迭代器中的 expectedModCount 的值卻沒有變，導致在迭代器下次執行 next () 方法時，expectedModCount != modCount 就會報 ConcurrentModificationException 的錯誤。 #### 2.3 還是上面的數組，如果刪除時使用 Iterator.remove () 方法可以刪除么，為什么？ 答：可以的，因為 Iterator.remove () 方法在執行的過程中，會把最新的 modCount 賦值給 expectedModCount，這樣在下次循環過程中，modCount 和 expectedModCount 兩者就會相等。 #### 2.4 以上三個問題對于 LinkedList 也是同樣的結果么？ 答：是的，雖然 LinkedList 底層結構是雙向鏈表，但對于上述三個問題，結果和 ArrayList 是一致的。 ### 3 對比類問題 #### 3.1 ArrayList 和 LinkedList 有何不同？ 答：可以先從底層數據結構開始說起，然后以某一個方法為突破口深入，比如：最大的不同是兩者底層的數據結構不同，ArrayList 底層是數組，LinkedList 底層是雙向鏈表，兩者的數據結構不同也導致了操作的 API 實現有所差異，拿新增實現來說，ArrayList 會先計算并決定是否擴容，然后把新增的數據直接賦值到數組上，而 LinkedList 僅僅只需要改變插入節點和其前后節點的指向位置關系即可。 #### 3.2 ArrayList 和 LinkedList 應用場景有何不同 答：ArrayList 更適合于快速的查找匹配，不適合頻繁新增刪除，像工作中經常會對元素進行匹配查詢的場景比較合適，LinkedList 更適合于經常新增和刪除，對查詢反而很少的場景。 #### 3.3 ArrayList 和 LinkedList 兩者有沒有最大容量 答：ArrayList 有最大容量的，為 Integer 的最大值，大于這個值 JVM 是不會為數組分配內存空間的，LinkedList 底層是雙向鏈表，理論上可以無限大。但源碼中，LinkedList 實際大小用的是 int 類型，這也說明了 LinkedList 不能超過 Integer 的最大值，不然會溢出。 #### 3.4 ArrayList 和 LinkedList 是如何對 null 值進行處理的 答：ArrayList 允許 null 值新增，也允許 null 值刪除。刪除 null 值時，是從頭開始，找到第一值是 null 的元素刪除；LinkedList 新增刪除時對 null 值沒有特殊校驗，是允許新增和刪除的。 #### 3.5 ArrayList 和 LinedList 是線程安全的么，為什么？ 答：當兩者作為非共享變量時，比如說僅僅是在方法里面的局部變量時，是沒有線程安全問題的，只有當兩者是共享變量時，才會有線程安全問題。主要的問題點在于多線程環境下，所有線程任何時刻都可對數組和鏈表進行操作，這會導致值被覆蓋，甚至混亂的情況。 如果有線程安全問題，在迭代的過程中，會頻繁報 ConcurrentModificationException 的錯誤，意思是在我當前循環的過程中，數組或鏈表的結構被其它線程修改了。 #### 3.6 如何解決線程安全問題？ Java 源碼中推薦使用 Collections#synchronizedList 進行解決，Collections#synchronizedList 的返回值是 List 的每個方法都加了 synchronized 鎖，保證了在同一時刻，數組和鏈表只會被一個線程所修改，或者采用 CopyOnWriteArrayList 并發 List 來解決，這個類我們后面會說。 ### 4 其它類型題目 #### 4.1 你能描述下雙向鏈表么？ 答：如果和面試官面對面溝通的話，你可以去畫一下，可以把 《LinkedList 源碼解析》中的 LinkedList 的結構畫出來，如果是電話面試，可以這么描述：雙向鏈表中雙向的意思是說前后節點之間互相有引用，鏈表的節點我們稱為 Node。Node 有三個屬性組成：其前一個節點，本身節點的值，其下一個節點，假設 A、B 節點相鄰，A 節點的下一個節點就是 B，B 節點的上一個節點就是 A，兩者互相引用，在鏈表的頭部節點，我們稱為頭節點。頭節點的前一個節點是 null，尾部稱為尾節點，尾節點的后一個節點是 null，如果鏈表數據為空的話，頭尾節點是同一個節點，本身是 null，指向前后節點的值也是 null。 #### 4.2 描述下雙向鏈表的新增和刪除 答：如果是面對面溝通，最好可以直接畫圖，如果是電話面試，可以這么描述： 新增：我們可以選擇從鏈表頭新增，也可以選擇從鏈表尾新增，如果是從鏈表尾新增的話，直接把當前節點追加到尾節點之后，本身節點自動變為尾節點。 刪除：把刪除節點的后一個節點的 prev 指向其前一個節點，把刪除節點的前一個節點的 next 指向其后一個節點，最后把刪除的節點置為 null 即可。 ## 總結 List 在工作中經常遇到，熟讀源碼不僅僅是為了應對面試，也為了在工作中使用起來得心應手，如果想更深入了解 List，可以看一遍 ArrayList 源碼之后，自己重新實現一個 List。這樣的話，就會對 List 底層的數據結構和操作細節理解更深。