前言

在面試的時(shí)候，經(jīng)常會被問到幾個問題：

ArrayList和LinkedList的區(qū)別，相信大部分朋友都能回答上：

ArrayList是基于數(shù)組實(shí)現(xiàn)，LinkedList是基于鏈表實(shí)現(xiàn)

當(dāng)隨機(jī)訪問List時(shí)，ArrayList比LinkedList的效率更高，等等

當(dāng)被問到ArrayList和LinkedList的使用場景是什么時(shí)，大部分朋友的答案可能是：

ArrayList和LinkedList在新增、刪除元素時(shí)，LinkedList的效率要高于 ArrayList，而在遍歷的時(shí)候，ArrayList的效率要高于LinkedList

那這個回答是否準(zhǔn)確呢？今天我們就來研究研究！

配合這篇文章食用會更香，從源碼角度解析ArrayList.subList的幾個坑

文章首發(fā)在公眾號（月伴飛魚），之后同步到掘金和個人網(wǎng)站：xiaoflyfish.cn/

喜歡的話，之后會分享更多系列文章！

覺得有收獲，希望幫忙點(diǎn)贊，轉(zhuǎn)發(fā)下哈，謝謝，謝謝

微信搜索：月伴飛魚，交個朋友，進(jìn)面試交流群

公眾號后臺回復(fù)666，可以獲得免費(fèi)電子書籍

我們先來簡單介紹下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接口，這個接口是一個標(biāo)志接口，他標(biāo)志著“只要實(shí)現(xiàn)該接口的List類，都能實(shí)現(xiàn)快速隨機(jī)訪問”。

基本屬性

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其實(shí)是實(shí)現(xiàn)了序列化接口，這是為什么呢？

由于ArrayList的數(shù)組是基于動態(tài)擴(kuò)增的，所以并不是所有被分配的內(nèi)存空間都存儲了數(shù)據(jù)。

如果采用外部序列化法實(shí)現(xiàn)數(shù)組的序列化，會序列化整個數(shù)組，ArrayList為了避免這些沒有存儲數(shù)據(jù)的內(nèi)存空間被序列化，內(nèi)部提供了兩個私有方法writeObject以及readObject來自我完成序列化與反序列化，從而在序列化與反序列化數(shù)組時(shí)節(jié)省了空間和時(shí)間。

因此使用transient修飾數(shù)組，是防止對象數(shù)組被其他外部方法序列化。

ArrayList自定義序列化方法如下：

初始化

有三種初始化辦法：無參數(shù)直接初始化、指定大小初始化、指定初始數(shù)據(jù)初始化，源碼如下：

當(dāng)ArrayList新增元素時(shí)，如果所存儲的元素已經(jīng)超過其已有大小，它會計(jì)算元素大小后再進(jìn)行動態(tài)擴(kuò)容，數(shù)組的擴(kuò)容會導(dǎo)致整個數(shù)組進(jìn)行一次內(nèi)存復(fù)制。

因此，我們在初始化ArrayList時(shí)，可以通過第一個構(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++;
    }

兩個方法的相同之處是在添加元素之前，都會先確認(rèn)容量大小，如果容量夠大，就不用進(jìn)行擴(kuò)容；如果容量不夠大，就會按照原來數(shù)組的1.5倍大小進(jìn)行擴(kuò)容，在擴(kuò)容之后需要將數(shù)組復(fù)制到新分配的內(nèi)存地址。

下面是具體的源碼：

這兩個方法也有不同之處，添加元素到任意位置，會導(dǎo)致在該位置后的所有元素都需要重新排列，而將元素添加到數(shù)組的末尾，在沒有發(fā)生擴(kuò)容的前提下，是不會有元素復(fù)制排序過程的。

所以ArrayList在大量新增元素的場景下效率不一定就很慢的

如果我們在初始化時(shí)就比較清楚存儲數(shù)據(jù)的大小，就可以在ArrayList初始化時(shí)指定數(shù)組容量大小，并且在添加元素時(shí)，只在數(shù)組末尾添加元素，那么ArrayList在大量新增元素的場景下，性能并不會變差，反而比其他List集合的性能要好。

刪除元素

ArrayList 刪除元素有很多種方式，比如根據(jù)數(shù)組索引刪除、根據(jù)值刪除或批量刪除等等，原理和思路都差不多。

ArrayList在每一次有效的刪除元素操作之后，都要進(jìn)行數(shù)組的重組，并且刪除的元素位置越靠前，數(shù)組重組的開銷就越大。

我們選取根據(jù)值刪除方式來進(jìn)行源碼說明：

遍歷元素

由于ArrayList是基于數(shù)組實(shí)現(xiàn)的，所以在獲取元素的時(shí)候是非常快捷的。

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)的。

這個雙向鏈表結(jié)構(gòu)，鏈表中的每個節(jié)點(diǎn)都可以向前或者向后追溯，有幾個概念如下：

• 鏈表每個節(jié)點(diǎn)我們叫做 Node，Node 有 prev 屬性，代表前一個節(jié)點(diǎn)的位置，next 屬性，代表后一個節(jié)點(diǎn)的位置；
• first 是雙向鏈表的頭節(jié)點(diǎn)，它的前一個節(jié)點(diǎn)是 null。
• last 是雙向鏈表的尾節(jié)點(diǎn)，它的后一個節(jié)點(diǎn)是 null；
• 當(dāng)鏈表中沒有數(shù)據(jù)時(shí)，first 和 last 是同一個節(jié)點(diǎn)，前后指向都是 null；
• 因?yàn)槭莻€雙向鏈表，只要機(jī)器內(nèi)存足夠強(qiáng)大，是沒有大小限制的。

Node結(jié)構(gòu)中包含了3個部分：元素內(nèi)容item、前指針prev以及后指針next，代碼如下。

private static class Node<E> {
    E item;// 節(jié)點(diǎn)值
    Node<E> next; // 指向的下一個節(jié)點(diǎn)
    Node<E> prev; // 指向的前一個節(jié)點(diǎn)

    // 初始化參數(shù)順序分別是：前一個節(jié)點(diǎn)、本身節(jié)點(diǎn)值、后一個節(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)對象連接而成的一個雙向鏈表。

實(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存儲數(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;

我們可以看到這三個屬性都被transient修飾了，原因很簡單，我們在序列化的時(shí)候不會只對頭尾進(jìn)行序列化，所以LinkedList也是自行實(shí)現(xiàn)readObject和writeObject進(jìn)行序列化與反序列化。

下面是LinkedList自定義序列化的方法。

節(jié)點(diǎn)查詢

鏈表查詢某一個節(jié)點(diǎn)是比較慢的，需要挨個循環(huán)查找才行，我們看看 LinkedList 的源碼是如何尋找節(jié)點(diǎn)的：

LinkedList 并沒有采用從頭循環(huán)到尾的做法，而是采取了簡單二分法，首先看看 index 是在鏈表的前半部分，還是后半部分。

如果是前半部分，就從頭開始尋找，反之亦然。通過這種方式，使循環(huán)的次數(shù)至少降低了一半，提高了查找的性能。

新增元素

LinkedList添加元素的實(shí)現(xiàn)很簡潔，但添加的方式卻有很多種。

默認(rèn)的add (Ee)方法是將添加的元素加到隊(duì)尾，首先是將last元素置換到臨時(shí)變量中，生成一個新的Node節(jié)點(diǎn)對象，然后將last引用指向新節(jié)點(diǎn)對象，之前的last對象的前指針指向新節(jié)點(diǎn)對象。

LinkedList也有添加元素到任意位置的方法，如果我們是將元素添加到任意兩個元素的中間位置，添加元素操作只會改變前后元素的前后指針，指針將會指向添加的新元素，所以相比ArrayList的添加操作來說，LinkedList的性能優(yōu)勢明顯。

刪除元素

在LinkedList刪除元素的操作中，我們首先要通過循環(huán)找到要刪除的元素，如果要刪除的位置處于List的前半段，就從前往后找；若其位置處于后半段，就從后往前找。

這樣做的話，無論要刪除較為靠前或較為靠后的元素都是非常高效的，但如果List擁有大量元素，移除的元素又在List的中間段，那效率相對來說會很低。

遍歷元素

LinkedList的獲取元素操作實(shí)現(xiàn)跟LinkedList的刪除元素操作基本類似，通過分前后半段來循環(huán)查找到對應(yīng)的元素，但是通過這種方式來查詢元素是非常低效的，特別是在for循環(huán)遍歷的情況下，每一次循環(huán)都會去遍歷半個List。

所以在LinkedList循環(huán)遍歷時(shí)，我們可以使用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ù)組實(shí)現(xiàn)的，在添加元素到數(shù)組頭部的時(shí)候，需要對頭部以后的數(shù)據(jù)進(jìn)行復(fù)制重排，所以效率很低；

LinkedList是基于鏈表實(shí)現(xiàn)，在添加元素的時(shí)候，首先會通過循環(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對象以及變換指針指向?qū)ο蟮倪^程，所以效率要低于ArrayList。

注意：這是排除動態(tài)擴(kuò)容數(shù)組容量的情況下進(jìn)行的測試，如果有動態(tài)擴(kuò)容的情況，ArrayList的效率也會降低。

刪除元素操作性能測試

ArrayList和LinkedList刪除元素操作測試的結(jié)果和添加元素操作測試的結(jié)果很接近！

結(jié)論：如果需要在List的頭部進(jìn)行大量的插入、刪除操作，那么直接選擇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)性能是最好的。

這是因?yàn)長inkedList基于鏈表實(shí)現(xiàn)的，在使用for循環(huán)的時(shí)候，每一次for循環(huán)都會去遍歷半個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)，也不會太差，所以在遍歷LinkedList時(shí)，我們要切忌使用for循環(huán)遍歷。

最后

覺得有收獲，希望幫忙點(diǎn)贊，轉(zhuǎn)發(fā)下哈，謝謝，謝謝

微信搜索：月伴飛魚，交個朋友，進(jìn)面試交流群

公眾號后臺回復(fù)666，可以獲得免費(fèi)電子書籍