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