ArrayList 重拳出擊，把 LinkedList 干翻在地

作者：沉默王二 2021-10-09 20:13:03

在計算機科學中，算法的時間復雜度(Time complexity)是一個函數，它定性描述該算法的運行時間。這是一個代表算法輸入值的字符串的長度的函數。時間復雜度常用大 O 符號表述，不包括這個函數的低階項和首項系數。

https://github.com/itwanger/toBeBetterJavaer

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

這是一個極其不負責任的總結，關鍵是你會在很多地方看到這樣的結論。

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

后來我研究了 ArrayList 和 LinkedList 的源碼，發現還真的是，前者是數組，后者是 LinkedList，于是我對大佬更加佩服了!

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

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

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

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

對于 ArrayList 來說：

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

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

這也是 ArrayList 的最大優點。

2)add(E e) 方法會默認將元素添加到數組末尾，但需要考慮到數組擴容的情況，如果不需要擴容，時間復雜度為。

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)擴容的時候，內部執行的 Arrays.copyOf() 方法是耗時的關鍵，需要把原有數組中的元素復制到擴容后的新數組當中。

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) 方法將新的元素插入到指定的位置，考慮到需要復制底層數組(根據之前的判斷，擴容的話，數組可能要復制一次)，根據最壞的打算(不管需要不需要擴容，System.arraycopy() 肯定要執行)，所以時間復雜度為。

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; 
}

來執行以下代碼，把沉默王八插入到下標為 2 的位置上。

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

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

之后再通過 elementData[index] = element 將下標為 2 的元素賦值為沉默王八;隨后執行 size = s + 1，數組的長度變為 7。

4)remove(int index) 方法將指定位置上的元素刪除，考慮到需要復制底層數組，所以時間復雜度為。

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) 方法的時間復雜度為，因為需要循環遍歷整個鏈表。

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; 
    } 
}

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

如果下標為 0 或者 list.size() - 1 的話，時間復雜度為。這種情況下，可以使用 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 在鏈表中是直接存儲的，所以時間復雜度為。

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

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) 方法將新的元素插入到指定的位置，需要先通過遍歷查找這個元素，然后再進行插入，所以時間復雜度為。

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

如果下標為 0 或者 list.size() - 1 的話，時間復雜度為。這種情況下，可以使用 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 插入元素的時間復雜度近似，其實是有問題的，因為 add(int index, E element) 方法在插入元素的時候會調用 node(index) 查找元素，該方法之前我們之間已經確認過了，時間復雜度為，即便隨后調用 linkBefore() 方法進行插入的時間復雜度為，總體上的時間復雜度仍然為才對。

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) 方法將指定位置上的元素刪除，考慮到需要調用 node(index) 方法查找元素，所以時間復雜度為。

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; 
}

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

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

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

但是，請注意，如果 ArrayList 在增刪改的時候涉及到大量的數組復制，效率就另當別論了，因為這個過程相當的耗時。

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

本文轉載自微信公眾號「沉默王二」，可以通過以下二維碼關注。轉載本文請聯系沉默王二公眾號。

責任編輯：武曉燕來源：沉默王二