Java--??面試官：LinkedList真的比ArrayList添加元素快？???本文通過Open JDK JMH帶你揭開真

歡迎進來學習的小伙伴，本文將會帶你揭開真相~

【學習背景】

不管你是學生，還是職場小白，還是入行Java幾年的小伙伴，相信很多小伙伴在面試Java工作崗位時，發現LinkedList和ArrayList這兩者相關的問題基本是必面的~

但是當面試官問到LinkedList和ArrayList的區別時，可能很多準備得不夠充分的小伙伴第一反應給出的回答僅僅是這樣的：

LinkedList底層數據結構是鏈表，添加和刪除元素效率比ArrayList高~

ArrayList底層數據結構是數組，查詢效率比LinkedList高~

有點毛病，而且僅僅是這樣回答，面試官可能不會懟你，但是肯定是不滿意的哇，也可能會繼續問：

面試官：哦，還有嗎？

應聘者：沒了~

面試官：大意了啊，你說的效率高是有通過JMH驗證尾插法添加元素的效率嗎？

應聘者：尾插法？？？

面試官：嗯，從數據結構的尾部添加數據，不過這里先不試了，回去再自己學習驗證下結論吧~

應聘者：哦…[臉紅emoj]…

回本正題，那么本文最主要目的就是通過JMH工具驗證==LinkedList添加元素真的比ArrayList快嗎？==

可能有些小伙伴會問JMH是啥？直接使用 for循環+時間戳System.currentTimeMillis() 盤它看看效率不行嗎？ 我想說的是你的==想法針不戳，但針滴不行啊，你可以百度看看為啥==，進入正文吧，JMH屬于Oracle官方Open JDK提供的一款性能測試工具，文中會進行介紹~

當然除了這個問題，本文也會將ArrayList和LinkedList進行分析和面試總結，加深對這兩者的認識，也希望能幫助到有需要的小伙伴~

@TOC

進入正文~

一、ArrayList和LinkedList

1.1 ArrayList

1.1.1 ArrayList特性

? 繼承AbstractList抽象類，==實現List接口==，還實現了RandomAccess==快速隨機訪問==以及Cloneable, java.io.Serializable克隆和序列化

? 底層數據結構是==數組==，連續內存空間，使用==for循環遍歷效率最高==，尾部添加和刪除元素時效率也很高，==非線程安全==

? 數組容量==動態自增==，當容量大于當前數組容量時進行擴容，==容量大小增加50%==，每次擴容都會開辟新空間，并且進行==新老數組的復制重排==

? 【JDK1.7之前版本】擴容后容量大小比【JDK1.7及之后版本】多1個容量

JDK1.7之前版本擴容關鍵源碼

int newCapacity = (oldCapacity * 3)/2 + 1 ）

JDK1.7及之后版本擴容關鍵源碼（PS：>>右移相當于除2的n次方，<<左移相當于乘2的n次方）

int newCapacity = oldCapacity + (oldCapacity >> 1)

1.1.2 ArrayList常用API

?增：效率add(E e) > add(int index,E element)

?刪：效率remove(int index) > remove(E e)

?改：set(int index,E element)

?查：get(int index)

1.1.3 ArrayList常見面試題（附參-）

（1）==ArrayList實現了RandomAccess接口，但是實際接口中什么都沒做，它有什么作用嗎？==

RandomAccess 是Java中的一個標志接口，只要實現該接口，就擁有快速隨機訪問的特性。

（2）==ArrayList幾個重要屬性各自的含義？==

ArrayList底層主要屬性有elementData對象數組、size集合大?。〝到M中已存儲的元素個數，非數組容量大?。?、DEFAULT_CAPACITY默認容量為10（new實例化時數組初始化容量大小為0，執行add添加元素時才指定初始化容量為DEFAULT_CAPACITY）~

（3）==ArrayList 屬性elementData數組使用了transient修飾，作用是什么？==

使用transient關鍵詞修飾屬性，表示不能被外部方法序列化

ArrayList 的elementData數組是動態擴容的，并非所有被分配的內存空間都存儲了數據，如果采用外部序列化法實現序列化，那整個elementData都會被序列化

ArrayList為了避免這些沒有存儲數據的內存空間被序列化，內部提供了兩個私有方法 writeObject 以及 readObject 來自我完成序列化與反序列化，從而在序列化與反序列化數組時節省了空間和時間。

（4）==?ArrayList如何添加元素效率最高？==

ArrayList 新增元素的方法常用的有兩種，一種是==直接添加元素==，另外一種是==添加元素到指定位置==

使用ArrayList的add(E e)方法直接添加元素，默認將元素添加到數組尾部，在沒有發生擴容的情況下，不會有數組的復制重排過程，效率最高

使用add(int index,E element)添加元素到指定位置，index等于0，表示在頭部添加元素，會導致在該位置后的所有元素都需要進行復制排列，時間復雜度O(n)-線性復雜度，效率很低

因此ArrayList在初始化時指定合適的數組容量大小，直接添加元素到數組尾部，那么ArrayList 添加元素的效率反而比LinkedList高

（5）==?ArrayList使用哪種方式遍歷查找效率最高？==

ArrayList使用for循環遍歷查找效率最高，因為ArrayList底層數據結構為數組，數組是一塊連續內存的空間，并且ArrayList實現了 RandomAccess 接口標志，意味著 ArrayList 擁有快速隨機訪問特性，對于元素的查找，時間復雜度為O(1)-常數復雜度，效率最高。

（6）==?ArrayList在foreach循環或迭代器遍歷中，調用自身的remove(E e)方法刪除元素，會導致什么問題？==

會拋ConcurrentModificationException異常，原因是==集合修改次數==modCount和==迭代器期望修改次數==expectedModCount不一致

foreach循環相當于迭代器，在迭代器遍歷中，使用ArrayList自身的remove(E e)方法刪除元素，內部會進行modCount++，但并不會進行迭代器的expectedModCount++，因此導致進入下一趟遍歷調用迭代器的next()方法中，內部比對兩者不一致拋出ConcurrentModificationException異常

==目前開發規范都是禁止在迭代器中使用集合自身的remove/add方法==，如果要在循環中刪除元素，應該使用迭代器的remove刪除，也可以使用for循環進行remove刪除元素，不過需要角標減1（i--）

（7）==?ArrayList初始化容量大小足夠的情況下，相比于LinkedList在頭部、中間、尾部添加的效率如何？==

頭部：

ArrayList 底層結構是==數組==，數組是一塊連續的內存空間，添加元素到數組頭部時，需要對頭部以后的==所有數據進行復制重排，效率最低，時間復雜度為O(n)==

LinkedList 底層結構是==鏈表==，通過addFirst(E e)方法添加元素到頭部時，效率也最高，時間復雜度為O(1)-常數復雜度，不過多了新節點創建和指針變換的過程

LinkedList也可以通過add(index, E element)方法，指定index等于0時，也表示添加元素到頭部時，不過此過程會先通過==二分法查找==找到指定位置的節點元素，而頭部剛好處于前半部分的第一個，找到該節點就返回，再進行后續新節點創建和指針變換，不過這種方式添加元素的==綜合時間復雜度為O(logN)-對數復雜度==

中間：

ArrayList 添加元素到數組中間，==往后的所有數據需要都進行復制重排，時間復雜度為O(n)==；

LinkedList添加元素到中間，==二分法查找發揮的作用最低==，不論從前往后，還是從后往前，鏈表被循環遍歷的次數都是最多的，效率最低，綜合==時間復雜度為O(n)==

結尾：

ArrayList 添加元素尾部，不需要進行復制重排數組數據，==效率最高==，時間復雜度為O(1)

LinkedList添加元素到尾部，==不需要查找元素，效率也是最高的==，但是==多了==新節點對象創建以及==變換指針指向對象的過程==，==效率比ArrayList低一些==，時間復雜度為O(1)

（8）==?ArrayList為什么是非線程安全的？==

因為ArrayList添加元素時，主要會進行這兩步操作，一是==判斷數組容量是否滿足大小==，二是==在數組對應位置賦值==，這2步操作在多線程訪問時都存在安全隱患~

第1個隱患是，判斷數組容量是否滿足大小的ensureCapacityInternal(size+1)方法中，可能多個線程會讀取到相同的size值，如果第1個線程傳入size+1進行判斷容量時，剛好滿足容量大小，就不會進行擴容，同理，其他線程也不會進行擴容，這樣就會導致進行下一步其他線程在數組對應位置賦值時，拋出數組下標越界ArrayIndexOutOfBoundsException異常

第2個隱患是，在數組對應位置賦值elementData [size++] = e; 實際上會被分解成兩步進行，先賦值 elementData [size] = e;再進行size=size+1; 可能第1個線程剛賦值完，還沒進行size+1，其他線程又對同一位置進行賦值，導致前面線程添加的元素值被覆蓋。

1.2 LinkedList

1.2.1 LinkedList特性

?繼承AbstractSequentialList抽象類，實現了List接口，還實現了Deque雙向隊列以及克隆Cloneable和序列化java.io.Serializable

?底層數據結構是雙向鏈表，在頭部和尾部添加、刪除元素效率比較高，非線程安全

?JDK1.7后Entry header屬性被替換為Node first和Node last首尾節點屬性

替換3點優勢：

first/last 屬性能更清晰地表達鏈表的鏈頭和鏈尾概念

first/last 方式可以在初始化 LinkedList 的時候節省 new 一個 Entry

first/last 方式最重要的性能優化是鏈頭和鏈尾的插入刪除操作更加快捷了。

1.2.2 LinkedList常用API

?增：效率add(E e) = addLast(E e) = addFirst(E e) > add(int index,E element)

?刪：效率removeFirst() = removeLast() > remove(int index) >remove(Object o)

?改：set(int index,E element)

?查：get(int index)

1.2.3 LinkedList常見面試題（附參-）

（1）==LinkedList為什么不能實現RandomAccess接口？==

因為LinkedList底層數據結構是鏈表，內存地址不連續，只能通過指針來定位，不支持隨機快速訪問，所以不能實現 RandomAccess 接口

（2）==LinkedList幾個重要屬性各自的含義？==

LinkedList底層主要屬性有size集合大?。ㄦ湵黹L度）、first鏈表頭部節點、last鏈表尾部節點，并且也都使用transient修飾，表示不能外部序列化與反序列化，內部自己實現了序列化與反序列化。

（3）==LinkedList默認添加元素是怎么實現的？==

LinkedList添加元素的方法主要有==直接添加==和==指定位置添加==

直接添加元素有add(E e)方法和addAll(Collection c)方法，指定位置添加元素有addFirst(E e)、addLast(E e)、add(int index,E element)、addAll(int index,Collection c)方法

==直接添加==元素默認添加到鏈表的尾部，不需要先查找節點，直接通過尾部節點，創建新節點和變換指針指向新節點

==指定位置==添加元素，如果是添加元素到鏈表頭部或尾部，都不需要先查找節點，直接通過頭部或尾部節點，創建新節點和變換指針指向新節點，但是如果是add(int index,E element)添加元素到非首尾位置，會先使用二分查找到該位置對應的節點，再通過該節點，創建新節點和變換指針指向新節點

（4）==LinkedList使用哪種方式遍歷效率最高？==

LinkedList底層數據結構是雙向鏈表的，使用foreach循環或iterator迭代器遍歷效率最高，通過迭代器的hasNext()、next()快速遍歷元素

需要注意的是盡量避免使用for循環遍歷LinkedList，因為每一次循環，都會使用二分查找先找到指定位置的節點，再通過該節點新建節點以及變換指針，效率極其低下。

（5）==LinkedList使用Iterator迭代器遍歷時，進行remove(E e)操作，迭代器的指針會發生什么變化？==

LinkedList使用迭代器遍歷，內部自己實現的是ListIterator接口，主要有lastReturned最后返回節點、next下一節點、nextIndex下一指針以及expectedModCount期望修改次數4個重要屬性，其中nextIndex下一指針從0開始

LinkedList迭代器遍歷時，每進行一趟遍歷，都會經過hasNext()、next()操作，并且在next()方法中，進行了nextIndex++操作

當進行到某一趟遍歷，調用remove()進行操作元素，會通過lastReturned進行解鏈，并且將next = lastReturned和nextIndex--操作，也就是迭代器的下一指針會減一

（6）==LinkedList默認位置添加元素和指定位置添加元素分別怎么實現，哪種性能更高？==

LinkedList默認位置添加元素通過add(E e)方法實現，默認位置是添加元素到尾部，時間復雜度是O(1)-常數復雜度，效率最高。

LinkedList指定位置添加元素通過addLast(E e)、addFirst(E e)方法添加元素到尾部和頭部，add(E e)方法默認位置是添加元素到尾部，時間復雜度是O(1)-常數復雜度，效率最高。

LinkedList還有一種指定位置添加元素通過add(int index, E element)方法實現，這種方式添加元素前，需要先通過二分查找找到指定位置的元素，再通過該元素進行==新節點創建以及指針變換==，綜合時間復雜度是O(logN)，如果添加元素的位置剛好在中間，二分查找發揮的作用最小，效率比較低~

（7）==List集合迭代器遍歷使用Iterator和ListIterator有什么不同？==

都是迭代器，都可以用來遍歷對應的實現類

Iterator允許遍歷所有實現Iterator接口的實現類，而ListIterator只能遍歷List集合

兩者都有hasNext()、next()、remove()方法正向操作列表，ListIterator還可以進行逆向操作列表和往集合中添加元素

二、JMH測試ArrayList和LinkedList性能

2.1 JMH是什么？

官方介紹

簡單介紹

JMH全稱Java Microbenchmark Harness（Java微基準套件），是Oracle 官方Open JDK提供的一款==Java微基準性能測試工具==，主要是基于==方法層面的基準測試==，納秒級精確度~

2.2 JMH應用場景？

【典型應用】

精確驗證某個方法執行時間

測試接口不同實現的吞吐量

等等…

日常開發及優化Java代碼時，當定位到熱點方法，想進一步==優化熱點方法的性能時==，可以通過JHM==精確驗證某個方法執行時間==，根據測試結果不斷進行優化~

2.3 JMH測試ArrayList和LinkedList（揭開真相）

應用場景不在于有多少，在于你用不用得到，這里我們就利用JMH==精確驗證某個方法執行時間==，來驗證本文的主題==LinkedList添加元素真的比ArrayList快？==

大致思路：

分別實現LinkedList和ArrayList默認添加元素==即尾部添加元素==的方法~

利用JMH分別對兩個方法進行基準測試，根據測試結果進行分析性能~

2.3.1 代碼實現

（1）添加依賴

需要依賴==jmh-core==和==jmh-generator-annprocess==兩個架包，可以去Maven官網下載~

Maven工程直接在pom.xml中添加依賴如下：

org.openjdk.jmh jmh-core 1.26 provided org.openjdk.jmh jmh-generator-annprocess 1.26 provided

（2）添加元素方法

package com.justin.java; import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.Throughput) //基準測試類型：吞吐量(單位時間內調用了多少次) @OutputTimeUnit(TimeUnit.MILLISECONDS) //基準測試結果的時間類型：毫秒 @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) //預熱：2 輪,每次1秒 @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS) //度量：測試5輪,每輪1秒 @Fork(1) //Fork出1個線程來測試 @State(Scope.Thread) // 每個測試線程分配1個實例 public class ArrayAndLinkedJmhTest { private List