毫不留情地揭開 ArrayList 和 LinkedList 之間的神秘面紗
ArrayList 和 LinkedList 是 List 接口的兩種不同實(shí)現(xiàn)，并且兩者都不是線程安全的。但初學(xué)者往往搞不清楚它們兩者之間的區(qū)別，不知道什么時(shí)候該用 ArrayList，什么時(shí)候該用 LinkedList，那這篇文章就來傳道受業(yè)解惑一下。
ArrayList 內(nèi)部使用的動(dòng)態(tài)數(shù)組來存儲(chǔ)元素，LinkedList 內(nèi)部使用的雙向鏈表來存儲(chǔ)元素，這也是 ArrayList 和 LinkedList 最本質(zhì)的區(qū)別。
注：本文使用的 JDK 源碼版本為 14，小伙伴如果發(fā)現(xiàn)文章中的源碼和自己本地的不同時(shí)，不要擔(dān)心，不是我源碼貼錯(cuò)了，也不是你本地的源碼錯(cuò)了，只是版本不同而已。
由于 ArrayList 和 LinkedList 內(nèi)部使用的存儲(chǔ)方式不同，導(dǎo)致它們的各種方法具有不同的時(shí)間復(fù)雜度。先來通過維基百科理解一下時(shí)間復(fù)雜度這個(gè)概念。
在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度（Time complexity）是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間。這是一個(gè)代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大 O 符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時(shí)的情況。例如，如果一個(gè)算法對(duì)于任何大小為 n （必須比??大）的輸入，它至多需要??的時(shí)間運(yùn)行完畢，那么它的漸近時(shí)間復(fù)雜度是 。
對(duì)于 ArrayList 來說：
1）get(int index) 方法的時(shí)間復(fù)雜度為 ，因?yàn)槭侵苯訌牡讓訑?shù)組根據(jù)下標(biāo)獲取的，和數(shù)組長(zhǎng)度無關(guān)。
public E get(int index) {Objects.checkIndex(index, size);return elementData(index);}
這也是 ArrayList 的最大優(yōu)點(diǎn)。
2）add(E e) 方法會(huì)默認(rèn)將元素添加到數(shù)組末尾，但需要考慮到數(shù)組擴(kuò)容的情況，如果不需要擴(kuò)容，時(shí)間復(fù)雜度為 。
public boolean add(E e) {modCount++;add(e, elementData, size);return true;}private void add(E e, Object[] elementData, int s) {if (s == elementData.length)elementData = grow();elementData[s] = e;size = s + 1;}
如果需要擴(kuò)容的話，并且不是第一次（oldCapacity > 0）擴(kuò)容的時(shí)候，內(nèi)部執(zhí)行的 Arrays.copyOf() 方法是耗時(shí)的關(guān)鍵，需要把原有數(shù)組中的元素復(fù)制到擴(kuò)容后的新數(shù)組當(dāng)中。
private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity >> 1 /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}
3）add(int index, E element) 方法將新的元素插入到指定的位置，考慮到需要復(fù)制底層數(shù)組（根據(jù)之前的判斷，擴(kuò)容的話，數(shù)組可能要復(fù)制一次），根據(jù)最壞的打算（不管需要不需要擴(kuò)容，System.arraycopy() 肯定要執(zhí)行），所以時(shí)間復(fù)雜度為 。
public void add(int index, E element) {rangeCheckForAdd(index);modCount++;final int s;Object[] elementData;if ((s = size) == (elementData = this.elementData).length)elementData = grow();System.arraycopy(elementData, index,elementData, index + 1,s - index);elementData[index] = element;size = s + 1;}
來執(zhí)行以下代碼，把沉默王八插入到下標(biāo)為 2 的位置上。
ArrayListlist = new ArrayList<>(); list.add("沉默王二");list.add("沉默王三");list.add("沉默王四");list.add("沉默王五");list.add("沉默王六");list.add("沉默王七");list.add(2, "沉默王八");
System.arraycopy() 執(zhí)行完成后，下標(biāo)為 2 的元素為沉默王四，這一點(diǎn)需要注意。也就是說，在數(shù)組中插入元素的時(shí)候，會(huì)把插入位置以后的元素依次往后復(fù)制，所以下標(biāo)為 2 和下標(biāo)為 3 的元素都為沉默王四。
之后再通過 elementData[index] = element 將下標(biāo)為 2 的元素賦值為沉默王八；隨后執(zhí)行 size = s + 1，數(shù)組的長(zhǎng)度變?yōu)?7。
4）remove(int index) 方法將指定位置上的元素刪除，考慮到需要復(fù)制底層數(shù)組，所以時(shí)間復(fù)雜度為 。
public E remove(int index) {Objects.checkIndex(index, size);final Object[] es = elementData;@SuppressWarnings("unchecked") E oldValue = (E) es[index];fastRemove(es, index);return oldValue;}private void fastRemove(Object[] es, int i) {modCount++;final int newSize;if ((newSize = size - 1) > i)System.arraycopy(es, i + 1, es, i, newSize - i);es[size = newSize] = null;}
對(duì)于 LinkedList 來說：
1）get(int index) 方法的時(shí)間復(fù)雜度為 ，因?yàn)樾枰h(huán)遍歷整個(gè)鏈表。
public E get(int index) {checkElementIndex(index);return node(index).item;}LinkedList.Nodenode(int index) { // assert isElementIndex(index);if (index < (size >> 1)) {LinkedList.Nodex = first; for (int i = 0; i < index; i++)x = x.next;return x;} else {LinkedList.Nodex = last; for (int i = size - 1; i > index; i--)x = x.prev;return x;}}
下標(biāo)小于鏈表長(zhǎng)度的一半時(shí)，從前往后遍歷；否則從后往前遍歷，這樣從理論上說，就節(jié)省了一半的時(shí)間。
如果下標(biāo)為 0 或者 list.size() - 1 的話，時(shí)間復(fù)雜度為 。這種情況下，可以使用 getFirst() 和 getLast() 方法。
public E getFirst() {final LinkedList.Nodef = first; if (f == null)throw new NoSuchElementException();return f.item;}public E getLast() {final LinkedList.Nodel = last; if (l == null)throw new NoSuchElementException();return l.item;}
first 和 last 在鏈表中是直接存儲(chǔ)的，所以時(shí)間復(fù)雜度為 。
2）add(E e) 方法默認(rèn)將元素添加到鏈表末尾，所以時(shí)間復(fù)雜度為 。
public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {final LinkedList.Nodel = last; final LinkedList.NodenewNode = new LinkedList.Node<>(l, e, null); last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}
3）add(int index, E element) 方法將新的元素插入到指定的位置，需要先通過遍歷查找這個(gè)元素，然后再進(jìn)行插入，所以時(shí)間復(fù)雜度為 。
public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}
如果下標(biāo)為 0 或者 list.size() - 1 的話，時(shí)間復(fù)雜度為 。這種情況下，可以使用 addFirst() 和 addLast() 方法。
public void addFirst(E e) {linkFirst(e);}private void linkFirst(E e) {final LinkedList.Nodef = first; final LinkedList.NodenewNode = new LinkedList.Node<>(null, e, f); first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;}
linkFirst() 只需要對(duì) first 進(jìn)行更新即可。
public void addLast(E e) {linkLast(e);}void linkLast(E e) {final LinkedList.Nodel = last; final LinkedList.NodenewNode = new LinkedList.Node<>(l, e, null); last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}
linkLast() 只需要對(duì) last 進(jìn)行更新即可。
需要注意的是，有些文章里面說，LinkedList 插入元素的時(shí)間復(fù)雜度近似 ，其實(shí)是有問題的，因?yàn)?add(int index, E element) 方法在插入元素的時(shí)候會(huì)調(diào)用 node(index) 查找元素，該方法之前我們之間已經(jīng)確認(rèn)過了，時(shí)間復(fù)雜度為 ，即便隨后調(diào)用 linkBefore() 方法進(jìn)行插入的時(shí)間復(fù)雜度為 ，總體上的時(shí)間復(fù)雜度仍然為 才對(duì)。
void linkBefore(E e, LinkedList.Nodesucc) { // assert succ != null;final LinkedList.Nodepred = succ.prev; final LinkedList.NodenewNode = new LinkedList.Node<>(pred, e, succ); succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}
4）remove(int index) 方法將指定位置上的元素刪除，考慮到需要調(diào)用 node(index) 方法查找元素，所以時(shí)間復(fù)雜度為 。
public E remove(int index) {checkElementIndex(index);return unlink(node(index));}E unlink(LinkedList.Nodex) { // assert x != null;final E element = x.item;final LinkedList.Nodenext = x.next; final LinkedList.Nodeprev = x.prev; if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}
通過時(shí)間復(fù)雜度的比較，以及源碼的分析，我相信小伙伴們?cè)谶x擇的時(shí)候就有了主意，對(duì)吧？
需要注意的是，如果列表很大很大，ArrayList 和 LinkedList 在內(nèi)存的使用上也有所不同。LinkedList 的每個(gè)元素都有更多開銷，因?yàn)橐鎯?chǔ)上一個(gè)和下一個(gè)元素的地址。ArrayList 沒有這樣的開銷。
但是，ArrayList 占用的內(nèi)存在聲明的時(shí)候就已經(jīng)確定了（默認(rèn)大小為 10），不管實(shí)際上是否添加了元素，因?yàn)閺?fù)雜對(duì)象的數(shù)組會(huì)通過 null 來填充。LinkedList 在聲明的時(shí)候不需要指定大小，元素增加或者刪除時(shí)大小隨之改變。
另外，ArrayList 只能用作列表；LinkedList 可以用作列表或者隊(duì)列，因?yàn)樗€實(shí)現(xiàn)了 Deque 接口。
我在寫這篇文章的時(shí)候，遇到了一些問題，所以請(qǐng)教了一些大廠的技術(shù)大佬，結(jié)果有個(gè)朋友說，“如果真的不知道該用 ArrayList 還是 LinkedList，就選擇 ArrayList 吧！”
我當(dāng)時(shí)以為他在和我開玩笑呢，結(jié)果通過時(shí)間復(fù)雜度的分析，好像他說得有道理啊。查詢的時(shí)候，ArrayList 比 LinkedList 快，這是毋庸置疑的；插入和刪除的時(shí)候，之前有很多資料說 LinkedList 更快，時(shí)間復(fù)雜度為 ，但其實(shí)不是的，因?yàn)橐闅v列表，對(duì)吧？
反而 ArrayList 更輕量級(jí)，不需要在每個(gè)元素上維護(hù)上一個(gè)和下一個(gè)元素的地址。
我這樣的結(jié)論可能和大多數(shù)文章得出的結(jié)論不符，那么我想，選擇權(quán)交給小伙伴們，你們?cè)谑褂玫倪^程中認(rèn)真地思考一下，并且我希望你們把自己的思考在留言區(qū)放出來。
公眾號(hào)：沉默王二（ID：cmower）
CSDN：沉默王二
這是一個(gè)有顏值卻靠才華吃飯的程序員，你知道，他的文章風(fēng)趣幽默，讀起來就好像花錢一樣爽快。
長(zhǎng)按下圖二維碼關(guān)注，你將感受到一個(gè)有趣的靈魂，且每篇文章都有干貨。
------------------
原創(chuàng)不易，莫要白票，如果覺得有點(diǎn)用的話，請(qǐng)毫不留情地素質(zhì)三連吧，分享、點(diǎn)贊、在看，我不挑，因?yàn)檫@將是我寫作更多優(yōu)質(zhì)文章的最強(qiáng)動(dòng)力。