快捷導(dǎo)航

一文講透為什么遍歷LinkedList要用增強(qiáng)型for循環(huán)

更新時(shí)間：2023年04月10日 10:22:55 作者：Yocn

這篇文章主要為大家介紹了為什么遍歷LinkedList要用增強(qiáng)型for循環(huán)的透徹詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

for循環(huán)和鏈表介紹

我們都知道java中有個(gè)增強(qiáng)型for循環(huán)，這個(gè)for循環(huán)很方便，如果不需要知道當(dāng)前遍歷到第幾個(gè)的話可以跟普通for循環(huán)替換使用，也有人知道這倆好像有那么一點(diǎn)點(diǎn)不一樣，但為什么不一樣就不知道了。

我們還知道LinkedList是一個(gè)雙向鏈表，這個(gè)集合應(yīng)該是唯一一個(gè)既實(shí)現(xiàn)了List接口又實(shí)現(xiàn)了Queue接口的集合類(lèi)。鏈表這種數(shù)據(jù)結(jié)構(gòu)，跟數(shù)組相比，優(yōu)勢(shì)在插入，劣勢(shì)在遍歷，那如果要遍歷一個(gè)鏈表，就要從頭開(kāi)始遍歷，否則根本不知道下一個(gè)Node是什么。

增強(qiáng)for循環(huán)為什么遍歷LinkedList那么快

其實(shí)這個(gè)標(biāo)題不合適，應(yīng)該是為什么普通for循環(huán)遍歷LinkedList為什么那么慢。我們寫(xiě)代碼驗(yàn)證一下時(shí)間：

public void test() {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 100000; i++) {//插入100000條數(shù)據(jù)
            list.add(i);
        }
        int index = 0;//記錄最后一個(gè)元素
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {//普通for循環(huán)遍歷
            index = list.get(i);
        }
        long time2 = System.currentTimeMillis();
        LogUtil.Companion.d("1:" + (time2 - time1) + " index->" + index);
        for (int i : list) {//增強(qiáng)for循環(huán)遍歷
            index = i;
        }
        long time3 = System.currentTimeMillis();
        LogUtil.Companion.d("2:" + (time3 - time2) + " index->" + index);
        Iterator<Integer> iterator = list.listIterator();
        while (iterator.hasNext()) {//iterator遍歷
            index = iterator.next();
        }
        long time4 = System.currentTimeMillis();
        LogUtil.Companion.d("3:" + (time4 - time3) + " index->" + index);
    }

運(yùn)行結(jié)果：

1:5056 index->99999
2:12 index->99999
3:1 index->99999

其實(shí)增強(qiáng)型for循環(huán)底層就是用iterator實(shí)現(xiàn)的，可以分析兩者的字節(jié)碼得出這個(gè)結(jié)論，這里我們不分析，算作一致結(jié)論。來(lái)看上面的結(jié)果，發(fā)現(xiàn)普通for循環(huán)遍歷的時(shí)間跟增強(qiáng)for循環(huán)和iterator相比簡(jiǎn)直令人發(fā)指。為什么會(huì)這樣呢？我們看LinkedList的源碼一探究竟。

LinkedList是一個(gè)雙向鏈表，用Head跟Tail兩個(gè)Node記錄了頭尾節(jié)點(diǎn)。

LinkedList相關(guān)源碼分析

普通for循環(huán)

我們看到其實(shí)普通for循環(huán)只是調(diào)用了LinkedList的 get(index) 方法：

//LinkedList.java
    public E get(int index) {
        checkElementIndex(index); //只是檢測(cè)是否數(shù)組越界
        return node(index).item; //調(diào)用了node(index)方法
    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);
//判斷index離頭部近一點(diǎn)還是離尾部近一點(diǎn)
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
     }
    }

get方法很簡(jiǎn)單，只是調(diào)用了node方法，node方法也很簡(jiǎn)單，只是判斷了index是否是小于size/2，小于說(shuō)明離Head近一點(diǎn)，否則說(shuō)明離tail近，離哪個(gè)近就從哪一頭開(kāi)始暴力遍歷，所以如果LinkedList有100000個(gè)Node，那最遠(yuǎn)的那個(gè)Node如果調(diào)用get方法就需要遍歷50000次。

所以普通for循環(huán)遍歷一次n個(gè)節(jié)點(diǎn)的LinkedList需要1+2+3+...+n/2+n/2+...+3+2+1次，時(shí)間復(fù)雜度可以寫(xiě)作O(n^2^)。

增強(qiáng)for循環(huán)

可以看到最終是調(diào)用了LinkedList的內(nèi)部類(lèi)ListItr

//LinkedList.java
public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;
        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
        public boolean hasNext() {
            return nextIndex < size;
        }
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
...
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

這里我們忽略一部分代碼先只看for循環(huán)涉及的方法，代碼其實(shí)也很簡(jiǎn)單。如果 hasNext() 存在，就調(diào)用next() ，兩個(gè)Node：lastReturned和next。

每次獲取index的時(shí)候調(diào)用 ListItr(int index) 后next會(huì)指向當(dāng)前index的Node。

調(diào)用next的時(shí)候lastReturned會(huì)指向next也就是當(dāng)前index的Node，next指向next.next，所以每次遍歷的時(shí)候只要賦值一次就可以得到next的節(jié)點(diǎn)，所以遍歷一個(gè)n個(gè)節(jié)點(diǎn)的LinkedList就是需要n次。

所以用iterator遍歷的話時(shí)間復(fù)雜度就是O(n)。

這就是為什么兩個(gè)for循環(huán)的方式這么區(qū)別這么大了~我們也可以直觀的看出來(lái)當(dāng)n到達(dá)十萬(wàn)這個(gè)級(jí)別的時(shí)候O(n^2^)和O(n)差別有多大了。

不知道各位發(fā)現(xiàn)沒(méi)有，Iterator里面每個(gè)操作都先調(diào)用了 checkForComodification() 方法，判斷 (modCount != expectedModCount) 是否相等。

各位應(yīng)該發(fā)現(xiàn)了ListItr有一個(gè)賦值，把modCount賦值給了expectedModCount，但每次調(diào)用遍歷或者addsetget的時(shí)候都會(huì)判斷這兩個(gè)值是否相等。

modCount是父類(lèi)AbstractList的屬性，而每次調(diào)用add(),remove()方法的時(shí)候這個(gè)值都會(huì)變，也就是如果集合里面內(nèi)容修改了modCount都會(huì)發(fā)生改變。

So，在使用Iterator的時(shí)候不能調(diào)用add()或者remove()這些會(huì)改變集合內(nèi)容的方法。兩種情況：