久久青春热热视频,人妻少妇蜜桃Av

大家好，我是二哥呀。

這是《Java 程序員進(jìn)階之路》專(zhuān)欄的第 60 篇，我們來(lái)聊聊 ArrayList 和 LinkedList 之間的區(qū)別。大家可以到 GitHub 上給二哥一個(gè) star，馬上破 400 星標(biāo)了。

https://github.com/itwanger/toBeBetterJavaer

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

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

害，我一開(kāi)始學(xué) Java 的時(shí)候，也問(wèn)過(guò)一個(gè)大佬，“ArrayList 和 LinkedList 有什么區(qū)別？”他就把“ArrayList 底層是數(shù)組，查詢快、增刪慢；LinkedList 底層是鏈表，查詢慢、增刪快”甩給我了，當(dāng)時(shí)覺(jué)得，大佬好牛逼?。?/p>

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

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

先來(lái)給大家普及一個(gè)概念——時(shí)間復(fù)雜度。

在計(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ù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無(wú)窮時(shí)的情況。例如，如果一個(gè)算法對(duì)于任何大小為 n （必須比 $n_0$ 大）的輸入，它至多需要 $5n^3 + 3n$ 的時(shí)間運(yùn)行完畢，那么它的漸近時(shí)間復(fù)雜度是 $O(n3^)$ 。

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

對(duì)于 ArrayList 來(lái)說(shuō)：

1）get(int index) 方法的時(shí)間復(fù)雜度為 $O(1)$ ，因?yàn)槭侵苯訌牡讓訑?shù)組根據(jù)下標(biāo)獲取的，和數(shù)組長(zhǎng)度無(wú)關(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ù)雜度為 $O(1)$ 。

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ù)雜度為 $O(n)$ 。

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

來(lái)執(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 的元素為沉默王四，這一點(diǎn)需要注意。也就是說(shuō)，在數(shù)組中插入元素的時(shí)候，會(huì)把插入位置以后的元素依次往后復(fù)制，所以下標(biāo)為 2 和下標(biāo)為 3 的元素都為沉默王四。

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

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

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 來(lái)說(shuō)：

1）get(int index) 方法的時(shí)間復(fù)雜度為 $O(n)$ ，因?yàn)樾枰h(huán)遍歷整個(gè)鏈表。

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)小于鏈表長(zhǎng)度的一半時(shí)，從前往后遍歷；否則從后往前遍歷，這樣從理論上說(shuō)，就節(jié)省了一半的時(shí)間。

如果下標(biāo)為 0 或者 list.size() - 1 的話，時(shí)間復(fù)雜度為 $O(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 在鏈表中是直接存儲(chǔ)的，所以時(shí)間復(fù)雜度為 $O(1)$ 。

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

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) 方法將新的元素插入到指定的位置，需要先通過(guò)遍歷查找這個(gè)元素，然后再進(jìn)行插入，所以時(shí)間復(fù)雜度為 $O(n)$ 。

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 的話，時(shí)間復(fù)雜度為 $O(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++;
}

linkFirst() 只需要對(duì) first 進(jìn)行更新即可。

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

linkLast() 只需要對(duì) last 進(jìn)行更新即可。

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

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) 方法查找元素，所以時(shí)間復(fù)雜度為 $O(n)$ 。

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

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

需要注意的是，如果列表很大很大，ArrayList 和 LinkedList 在內(nèi)存的使用上也有所不同。LinkedList 的每個(gè)元素都有更多開(kāi)銷(xiāo)，因?yàn)橐鎯?chǔ)上一個(gè)和下一個(gè)元素的地址。ArrayList 沒(méi)有這樣的開(kāi)銷(xiāo)。

查詢的時(shí)候，ArrayList 比 LinkedList 快，這是毋庸置疑的；插入和刪除的時(shí)候，LinkedList 因?yàn)橐闅v列表，所以并不比 ArrayList 更快。反而 ArrayList 更輕量級(jí)，不需要在每個(gè)元素上維護(hù)上一個(gè)和下一個(gè)元素的地址。

但是，請(qǐng)注意，如果 ArrayList 在增刪改的時(shí)候涉及到大量的數(shù)組復(fù)制，效率就另當(dāng)別論了，因?yàn)檫@個(gè)過(guò)程相當(dāng)?shù)暮臅r(shí)。

對(duì)于初學(xué)者來(lái)說(shuō)，一般不會(huì)涉及到百萬(wàn)級(jí)別的數(shù)據(jù)操作，如果真的不知道該用 ArrayList 還是 LinkedList，就無(wú)腦選擇 ArrayList 吧！

這是《Java 程序員進(jìn)階之路》專(zhuān)欄的第 60 篇。Java 程序員進(jìn)階之路，風(fēng)趣幽默、通俗易懂，對(duì) Java 初學(xué)者極度友好和舒適??，內(nèi)容包括但不限于 Java 語(yǔ)法、Java 集合框架、Java IO、Java 并發(fā)編程、Java 虛擬機(jī)等核心知識(shí)點(diǎn)。

https://github.com/itwanger/toBeBetterJavaer

這么好的東西，還不 star 下？

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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