ArrayList和LinkedList使用不當(dāng)，性能差距會如此之大！
前言
在面試的時候，經(jīng)常會被問到幾個問題：
ArrayList和LinkedList的區(qū)別，相信大部分朋友都能回答上：
- ArrayList是基于數(shù)組實現(xiàn)，LinkedList是基于鏈表實現(xiàn)
- 當(dāng)隨機訪問List時，ArrayList比LinkedList的效率更高，等等
當(dāng)被問到ArrayList和LinkedList的使用場景是什么時，大部分朋友的答案可能是：
- ArrayList和LinkedList在新增、刪除元素時，LinkedList的效率要高于 ArrayList，而在遍歷的時候，ArrayList的效率要高于LinkedList
那這個回答是否準(zhǔn)確呢?今天我們就來研究研究!
我們先來簡單介紹下ArrayList和LinkedList的原理實現(xiàn)!
源碼分析
ArrayList
實現(xiàn)類
- public class ArrayList<E> extends AbstractList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList實現(xiàn)了List接口，繼承了AbstractList抽象類，底層是數(shù)組實現(xiàn)的，并且實現(xiàn)了自增擴容數(shù)組大小。
ArrayList還實現(xiàn)了Cloneable接口和Serializable接口，所以他可以實現(xiàn)克隆和序列化。
ArrayList還實現(xiàn)了RandomAccess接口，這個接口是一個標(biāo)志接口，他標(biāo)志著“只要實現(xiàn)該接口的List類，都能實現(xiàn)快速隨機訪問”。
基本屬性
ArrayList屬性主要由數(shù)組長度size、對象數(shù)組elementData、初始化容量default_capacity等組成， 其中初始化容量默認(rèn)大小為10。
- //默認(rèn)初始化容量
- private static final int DEFAULT_CAPACITY = 10;
- //對象數(shù)組
- transient Object[] elementData;
- //數(shù)組長度
- private int size;
從ArrayList屬性來看，elementData被關(guān)鍵字transient修飾了，transient關(guān)鍵字修飾該字段則表示該屬性不會被序列化。
- 但ArrayList其實是實現(xiàn)了序列化接口，這是為什么呢?
由于ArrayList的數(shù)組是基于動態(tài)擴增的，所以并不是所有被分配的內(nèi)存空間都存儲了數(shù)據(jù)。
如果采用外部序列化法實現(xiàn)數(shù)組的序列化，會序列化整個數(shù)組，ArrayList為了避免這些沒有存儲數(shù)據(jù)的內(nèi)存空間被序列化，內(nèi)部提供了兩個私有方法writeObject以及readObject來自我完成序列化與反序列化，從而在序列化與反序列化數(shù)組時節(jié)省了空間和時間。
因此使用transient修飾數(shù)組，是防止對象數(shù)組被其他外部方法序列化。
ArrayList自定義序列化方法如下：
初始化
有三種初始化辦法：無參數(shù)直接初始化、指定大小初始化、指定初始數(shù)據(jù)初始化，源碼如下：
當(dāng)ArrayList新增元素時，如果所存儲的元素已經(jīng)超過其已有大小，它會計算元素大小后再進行動態(tài)擴容，數(shù)組的擴容會導(dǎo)致整個數(shù)組進行一次內(nèi)存復(fù)制。
因此，我們在初始化ArrayList時，可以通過第一個構(gòu)造函數(shù)合理指定數(shù)組初始大小，這樣有助于減少數(shù)組的擴容次數(shù)，從而提高系統(tǒng)性能。
注意點：
ArrayList 無參構(gòu)造器初始化時，默認(rèn)大小是空數(shù)組，并不是大家常說的 10，10 是在第一次 add 的時候擴容的數(shù)組值。
新增元素
ArrayList新增元素的方法有兩種，一種是直接將元素加到數(shù)組的末尾，另外一種是添加元素到任意位置。
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
- public void add(int index, E element) {
- rangeCheckForAdd(index);
- ensureCapacityInternal(size + 1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
兩個方法的相同之處是在添加元素之前，都會先確認(rèn)容量大小，如果容量夠大，就不用進行擴容;如果容量不夠大，就會按照原來數(shù)組的1.5倍大小進行擴容，在擴容之后需要將數(shù)組復(fù)制到新分配的內(nèi)存地址。
下面是具體的源碼：
這兩個方法也有不同之處，添加元素到任意位置，會導(dǎo)致在該位置后的所有元素都需要重新排列，而將元素添加到數(shù)組的末尾，在沒有發(fā)生擴容的前提下，是不會有元素復(fù)制排序過程的。
- 所以ArrayList在大量新增元素的場景下效率不一定就很慢的
如果我們在初始化時就比較清楚存儲數(shù)據(jù)的大小，就可以在ArrayList初始化時指定數(shù)組容量大小，并且在添加元素時，只在數(shù)組末尾添加元素，那么ArrayList在大量新增元素的場景下，性能并不會變差，反而比其他List集合的性能要好。
刪除元素
ArrayList 刪除元素有很多種方式，比如根據(jù)數(shù)組索引刪除、根據(jù)值刪除或批量刪除等等，原理和思路都差不多。
ArrayList在每一次有效的刪除元素操作之后，都要進行數(shù)組的重組，并且刪除的元素位置越靠前，數(shù)組重組的開銷就越大。
我們選取根據(jù)值刪除方式來進行源碼說明：
遍歷元素
由于ArrayList是基于數(shù)組實現(xiàn)的，所以在獲取元素的時候是非?？旖莸?。
- public E get(int index) {
- rangeCheck(index);
- return elementData(index);
- }
- E elementData(int index) {
- return (E) elementData[index];
- }
LinkedList
LinkedList是基于雙向鏈表數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的。
這個雙向鏈表結(jié)構(gòu)，鏈表中的每個節(jié)點都可以向前或者向后追溯，有幾個概念如下：
- 鏈表每個節(jié)點我們叫做 Node，Node 有 prev 屬性，代表前一個節(jié)點的位置，next 屬性，代表后一個節(jié)點的位置;
- first 是雙向鏈表的頭節(jié)點，它的前一個節(jié)點是 null。
- last 是雙向鏈表的尾節(jié)點，它的后一個節(jié)點是 null;
- 當(dāng)鏈表中沒有數(shù)據(jù)時，first 和 last 是同一個節(jié)點，前后指向都是 null;
- 因為是個雙向鏈表，只要機器內(nèi)存足夠強大，是沒有大小限制的。
Node結(jié)構(gòu)中包含了3個部分：元素內(nèi)容item、前指針prev以及后指針next，代碼如下。
- private static class Node<E> {
- E item;// 節(jié)點值
- Node<E> next; // 指向的下一個節(jié)點
- Node<E> prev; // 指向的前一個節(jié)點
- // 初始化參數(shù)順序分別是：前一個節(jié)點、本身節(jié)點值、后一個節(jié)點
- Node(Node<E> prev, E element, Node<E> next) {
- this.item = element;
- this.next = next;
- this.prev = prev;
- }
- }
LinkedList就是由Node結(jié)構(gòu)對象連接而成的一個雙向鏈表。
實現(xiàn)類
LinkedList類實現(xiàn)了List接口、Deque接口，同時繼承了AbstractSequentialList抽象類，LinkedList既實現(xiàn)了List類型又有Queue類型的特點;LinkedList也實現(xiàn)了Cloneable和Serializable接口，同ArrayList一樣，可以實現(xiàn)克隆和序列化。
由于LinkedList存儲數(shù)據(jù)的內(nèi)存地址是不連續(xù)的，而是通過指針來定位不連續(xù)地址，因此，LinkedList不支持隨機快速訪問，LinkedList也就不能實現(xiàn)RandomAccess接口。
- public class LinkedList
- extends AbstractSequentialList
- implements List, Deque, Cloneable, java.io.Serializable
基本屬性
- transient int size = 0;
- transient Node first;
- transient Node last;
我們可以看到這三個屬性都被transient修飾了，原因很簡單，我們在序列化的時候不會只對頭尾進行序列化，所以LinkedList也是自行實現(xiàn)readObject和writeObject進行序列化與反序列化。
下面是LinkedList自定義序列化的方法。
節(jié)點查詢
鏈表查詢某一個節(jié)點是比較慢的，需要挨個循環(huán)查找才行，我們看看 LinkedList 的源碼是如何尋找節(jié)點的：
LinkedList 并沒有采用從頭循環(huán)到尾的做法，而是采取了簡單二分法，首先看看 index 是在鏈表的前半部分，還是后半部分。
如果是前半部分，就從頭開始尋找，反之亦然。通過這種方式，使循環(huán)的次數(shù)至少降低了一半，提高了查找的性能。
新增元素
LinkedList添加元素的實現(xiàn)很簡潔，但添加的方式卻有很多種。
默認(rèn)的add (Ee)方法是將添加的元素加到隊尾，首先是將last元素置換到臨時變量中，生成一個新的Node節(jié)點對象，然后將last引用指向新節(jié)點對象，之前的last對象的前指針指向新節(jié)點對象。
LinkedList也有添加元素到任意位置的方法，如果我們是將元素添加到任意兩個元素的中間位置，添加元素操作只會改變前后元素的前后指針，指針將會指向添加的新元素，所以相比ArrayList的添加操作來說，LinkedList的性能優(yōu)勢明顯。
刪除元素
在LinkedList刪除元素的操作中，我們首先要通過循環(huán)找到要刪除的元素，如果要刪除的位置處于List的前半段，就從前往后找;若其位置處于后半段，就從后往前找。
這樣做的話，無論要刪除較為靠前或較為靠后的元素都是非常高效的，但如果List擁有大量元素，移除的元素又在List的中間段，那效率相對來說會很低。
遍歷元素
LinkedList的獲取元素操作實現(xiàn)跟LinkedList的刪除元素操作基本類似，通過分前后半段來循環(huán)查找到對應(yīng)的元素，但是通過這種方式來查詢元素是非常低效的，特別是在for循環(huán)遍歷的情況下，每一次循環(huán)都會去遍歷半個List。
所以在LinkedList循環(huán)遍歷時，我們可以使用iterator方式迭代循環(huán)，直接拿到我們的元素，而不需要通過循環(huán)查找List。
分析測試
新增元素操作性能測試
測試用例源代碼：
- ArrayList：https://paste.ubuntu.com/p/gktBvjgMGk/
- LinkedList：https://paste.ubuntu.com/p/3jQrY2XMPr/
測試結(jié)果：
通過這組測試，我們可以知道LinkedList添加元素的效率未必要高于ArrayList。
- 從集合頭部位置添加元素
由于ArrayList是數(shù)組實現(xiàn)的，在添加元素到數(shù)組頭部的時候，需要對頭部以后的數(shù)據(jù)進行復(fù)制重排，所以效率很低;
LinkedList是基于鏈表實現(xiàn)，在添加元素的時候，首先會通過循環(huán)查找到添加元素的位置，如果要添加的位置處于List的前半段，就從前往后找;若其位置處于后半段，就從后往前找，因此LinkedList添加元素到頭部是非常高效的。
- 從集合中間位置位置添加元素
ArrayList在添加元素到數(shù)組中間時，同樣有部分?jǐn)?shù)據(jù)需要復(fù)制重排，效率也不是很高;
LinkedList將元素添加到中間位置，是添加元素最低效率的，因為靠近中間位置，在添加元素之前的循環(huán)查找是遍歷元素最多的操作。
- 從集合尾部位置添加元素
而在添加元素到尾部的操作中，在沒有擴容的情況下，ArrayList的效率要高于LinkedList。
這是因為ArrayList在添加元素到尾部的時候，不需要復(fù)制重排數(shù)據(jù)，效率非常高。
LinkedList雖然也不用循環(huán)查找元素，但LinkedList中多了new對象以及變換指針指向?qū)ο蟮倪^程，所以效率要低于ArrayList。
- 注意：這是排除動態(tài)擴容數(shù)組容量的情況下進行的測試，如果有動態(tài)擴容的情況，ArrayList的效率也會降低。
刪除元素操作性能測試
ArrayList和LinkedList刪除元素操作測試的結(jié)果和添加元素操作測試的結(jié)果很接近!
結(jié)論：如果需要在List的頭部進行大量的插入、刪除操作，那么直接選擇LinkedList。否則，ArrayList即可。
遍歷元素操作性能測試
測試用例源代碼：
- ArrayList：https://paste.ubuntu.com/p/ZNWc9H2pYm/
- LinkedList：https://paste.ubuntu.com/p/xSk4nHDHvN/
測試結(jié)果：
我們可以看到，LinkedList的for循環(huán)性能是最差的，而ArrayList的for循環(huán)性能是最好的。
這是因為LinkedList基于鏈表實現(xiàn)的，在使用for循環(huán)的時候，每一次for循環(huán)都會去遍歷半個List，所以嚴(yán)重影響了遍歷的效率;ArrayList則是基于數(shù)組實現(xiàn)的，并且實現(xiàn)了RandomAccess接口標(biāo)志，意味著ArrayList可以實現(xiàn)快速隨機訪問，所以for循環(huán)效率非常高。
LinkedList的迭代循環(huán)遍歷和ArrayList的迭代循環(huán)遍歷性能相當(dāng)，也不會太差，所以在遍歷LinkedList時，我們要切忌使用for循環(huán)遍歷。
