[[427856]]

 https://github.com/itwanger/toBeBetterJavaer

如果再有人給你說 “ArrayList 底層是數(shù)組，查詢快、增刪慢;LinkedList 底層是鏈表，查詢慢、增刪快”，你可以讓他滾了!

這是一個極其不負(fù)責(zé)任的總結(jié)，關(guān)鍵是你會在很多地方看到這樣的結(jié)論。

害，我一開始學(xué) Java 的時候，也問過一個大佬，“ArrayList 和 LinkedList 有什么區(qū)別?”他就把“ArrayList 底層是數(shù)組，查詢快、增刪慢;LinkedList 底層是鏈表，查詢慢、增刪快”甩給我了，當(dāng)時覺得，大佬好牛逼啊!

后來我研究了 ArrayList 和 LinkedList 的源碼，發(fā)現(xiàn)還真的是，前者是數(shù)組，后者是 LinkedList，于是我對大佬更加佩服了!

直到后來，我親自跑程序驗證了一遍，才發(fā)現(xiàn)大佬的結(jié)論太草率了!根本就不是這么回事!

先來給大家普及一個概念——時間復(fù)雜度。

在計算機科學(xué)中，算法的時間復(fù)雜度(Time complexity)是一個函數(shù)，它定性描述該算法的運行時間。這是一個代表算法輸入值的字符串的長度的函數(shù)。時間復(fù)雜度常用大 O 符號表述，不包括這個函數(shù)的低階項和首項系數(shù)。使用這種方式時，時間復(fù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。例如，如果一個算法對于任何大小為 n (必須比 大)的輸入，它至多需要 的時間運行完畢，那么它的漸近時間復(fù)雜度是 。

增刪改查，對應(yīng)到 ArrayList 和 LinkedList，就是 add(E e)、remove(int index)、add(int index, E element)、get(int index)，我來給大家一一分析下，它們對應(yīng)的時間復(fù)雜度，也就明白了“ArrayList 底層是數(shù)組，查詢快、增刪慢;LinkedList 底層是鏈表，查詢慢、增刪快”這個結(jié)論很荒唐的原因

對于 ArrayList 來說：

1)get(int index) 方法的時間復(fù)雜度為 ，因為是直接從底層數(shù)組根據(jù)下標(biāo)獲取的，和數(shù)組長度無關(guān)。

public E get(int index) { 
    Objects.checkIndex(index, size); 
    return elementData(index); 
} 

這也是 ArrayList 的最大優(yōu)點。

2)add(E e) 方法會默認(rèn)將元素添加到數(shù)組末尾，但需要考慮到數(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; 
} 

如果需要擴容的話，并且不是第一次(oldCapacity > 0)擴容的時候，內(nèi)部執(zhí)行的 Arrays.copyOf() 方法是耗時的關(guān)鍵，需要把原有數(shù)組中的元素復(fù)制到擴容后的新數(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ù)之前的判斷，擴容的話，數(shù)組可能要復(fù)制一次)，根據(jù)最壞的打算(不管需要不需要擴容，System.arraycopy() 肯定要執(zhí)行)，所以時間復(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 的位置上。

ArrayList<String> list = new ArrayList<>(); 
list.add("沉默王二"); 
list.add("沉默王三"); 
list.add("沉默王四"); 
list.add("沉默王五"); 
list.add("沉默王六"); 
list.add("沉默王七"); 
list.add(2, "沉默王八"); 

System.arraycopy() 執(zhí)行完成后，下標(biāo)為 2 的元素為沉默王四，這一點需要注意。也就是說，在數(shù)組中插入元素的時候，會把插入位置以后的元素依次往后復(fù)制，所以下標(biāo)為 2 和下標(biāo)為 3 的元素都為沉默王四。

之后再通過 elementData[index] = element 將下標(biāo)為 2 的元素賦值為沉默王八;隨后執(zhí)行 size = s + 1，數(shù)組的長度變?yōu)?7。

4)remove(int index) 方法將指定位置上的元素刪除，考慮到需要復(fù)制底層數(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; 
} 

對于 LinkedList 來說：

1)get(int index) 方法的時間復(fù)雜度為 ，因為需要循環(huán)遍歷整個鏈表。

public E get(int index) { 
    checkElementIndex(index); 
    return node(index).item; 
} 
 
LinkedList.Node<E> node(int index) { 
    // assert isElementIndex(index); 
 
    if (index < (size >> 1)) { 
        LinkedList.Node<E> x = first; 
        for (int i = 0; i < index; i++) 
            x = x.next; 
        return x; 
    } else { 
        LinkedList.Node<E> x = last; 
        for (int i = size - 1; i > index; i--) 
            x = x.prev; 
        return x; 
    } 
} 

下標(biāo)小于鏈表長度的一半時，從前往后遍歷;否則從后往前遍歷，這樣從理論上說，就節(jié)省了一半的時間。

如果下標(biāo)為 0 或者 list.size() - 1 的話，時間復(fù)雜度為 。這種情況下，可以使用 getFirst() 和 getLast() 方法。

public E getFirst() { 
    final LinkedList.Node<E> f = first; 
    if (f == null) 
        throw new NoSuchElementException(); 
    return f.item; 
} 
 
public E getLast() { 
    final LinkedList.Node<E> l = last; 
    if (l == null) 
        throw new NoSuchElementException(); 
    return l.item; 
} 

first 和 last 在鏈表中是直接存儲的，所以時間復(fù)雜度為 。

2)add(E e) 方法默認(rèn)將元素添加到鏈表末尾，所以時間復(fù)雜度為 。

public boolean add(E e) { 
    linkLast(e); 
    return true; 
} 
void linkLast(E e) { 
    final LinkedList.Node<E> l = last; 
    final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null); 
    last = newNode; 
    if (l == null) 
        first = newNode; 
    else 
        l.next = newNode; 
    size++; 
    modCount++; 
} 

3)add(int index, E element) 方法將新的元素插入到指定的位置，需要先通過遍歷查找這個元素，然后再進行插入，所以時間復(fù)雜度為。

public void add(int index, E element) { 
    checkPositionIndex(index); 
 
    if (index == size) 
        linkLast(element); 
    else 
        linkBefore(element, node(index)); 
} 

如果下標(biāo)為 0 或者 list.size() - 1 的話，時間復(fù)雜度為 。這種情況下，可以使用 addFirst() 和 addLast() 方法。

public void addFirst(E e) { 
    linkFirst(e); 
} 
private void linkFirst(E e) { 
    final LinkedList.Node<E> f = first; 
    final LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f); 
    first = newNode; 
    if (f == null) 
        last = newNode; 
    else 
        f.prev = newNode; 
    size++; 
    modCount++; 
} 

linkLast() 只需要對 last 進行更新即可。

public void addLast(E e) { 
    linkLast(e); 
} 
 
void linkLast(E e) { 
    final LinkedList.Node<E> l = last; 
    final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null); 
    last = newNode; 
    if (l == null) 
        first = newNode; 
    else 
        l.next = newNode; 
    size++; 
    modCount++; 
} 

需要注意的是，有些文章里面說，LinkedList 插入元素的時間復(fù)雜度近似 ，其實是有問題的，因為 add(int index, E element) 方法在插入元素的時候會調(diào)用 node(index) 查找元素，該方法之前我們之間已經(jīng)確認(rèn)過了，時間復(fù)雜度為 ，即便隨后調(diào)用 linkBefore() 方法進行插入的時間復(fù)雜度為 ，總體上的時間復(fù)雜度仍然為 才對。

void linkBefore(E e, LinkedList.Node<E> succ) { 
    // assert succ != null; 
    final LinkedList.Node<E> pred = succ.prev; 
    final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ); 
    succ.prev = newNode; 
    if (pred == null) 
        first = newNode; 
    else 
        pred.next = newNode; 
    size++; 
    modCount++; 
} 

4)remove(int index) 方法將指定位置上的元素刪除，考慮到需要調(diào)用 node(index) 方法查找元素，所以時間復(fù)雜度為 。

public E remove(int index) { 
    checkElementIndex(index); 
    return unlink(node(index)); 
} 
 
E unlink(LinkedList.Node<E> x) { 
    // assert x != null; 
    final E element = x.item; 
    final LinkedList.Node<E> next = x.next; 
    final LinkedList.Node<E> prev = 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; 
} 

通過時間復(fù)雜度的比較，以及源碼的分析，我相信大家在選擇的時候就有了主意，對吧?

需要注意的是，如果列表很大很大，ArrayList 和 LinkedList 在內(nèi)存的使用上也有所不同。LinkedList 的每個元素都有更多開銷，因為要存儲上一個和下一個元素的地址。ArrayList 沒有這樣的開銷。

查詢的時候，ArrayList 比 LinkedList 快，這是毋庸置疑的;插入和刪除的時候，LinkedList 因為要遍歷列表，所以并不比 ArrayList 更快。反而 ArrayList 更輕量級，不需要在每個元素上維護上一個和下一個元素的地址。

但是，請注意，如果 ArrayList 在增刪改的時候涉及到大量的數(shù)組復(fù)制，效率就另當(dāng)別論了，因為這個過程相當(dāng)?shù)暮臅r。

對于初學(xué)者來說，一般不會涉及到百萬級別的數(shù)據(jù)操作，如果真的不知道該用 ArrayList 還是 LinkedList，就無腦選擇 ArrayList 吧!

本文轉(zhuǎn)載自微信公眾號「沉默王二」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系沉默王二公眾號。