遍歷LinkedList要用增強型for循環的原因是什么

本文小編為大家詳細介紹“遍歷LinkedList要用增強型for循環的原因是什么”，內容詳細，步驟清晰，細節處理妥當，希望這篇“遍歷LinkedList要用增強型for循環的原因是什么”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

for循環和鏈表介紹

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

我們還知道LinkedList是一個雙向鏈表，這個集合應該是唯一一個既實現了List接口又實現了Queue接口的集合類。 鏈表這種數據結構，跟數組相比，優勢在插入，劣勢在遍歷，那如果要遍歷一個鏈表，就要從頭開始遍歷，否則根本不知道下一個Node是什么。

增強for循環為什么遍歷LinkedList那么快

其實這個標題不合適，應該是為什么普通for循環遍歷LinkedList為什么那么慢。我們寫代碼驗證一下時間：

public void test() {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 100000; i++) {//插入100000條數據
            list.add(i);
        }
        int index = 0;//記錄最后一個元素
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {//普通for循環遍歷
            index = list.get(i);
        }
        long time2 = System.currentTimeMillis();
        LogUtil.Companion.d("1:" + (time2 - time1) + " index->" + index);
        for (int i : list) {//增強for循環遍歷
            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);
    }

運行結果：

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

其實增強型for循環底層就是用iterator實現的，可以分析兩者的字節碼得出這個結論，這里我們不分析，算作一致結論。來看上面的結果，發現普通for循環遍歷的時間跟增強for循環和iterator相比簡直令人發指。 為什么會這樣呢？我們看LinkedList的源碼一探究竟。

LinkedList是一個雙向鏈表，用Head跟Tail兩個Node記錄了頭尾節點。

LinkedList相關源碼分析

普通for循環

我們看到其實普通for循環只是調用了LinkedList的 get(index) 方法：

//LinkedList.java
    public E get(int index) {
        checkElementIndex(index); //只是檢測是否數組越界
        return node(index).item; //調用了node(index)方法
    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);
//判斷index離頭部近一點還是離尾部近一點
        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方法很簡單，只是調用了node方法，node方法也很簡單，只是判斷了index是否是小于size/2，小于說明離Head近一點，否則說明離tail近，離哪個近就從哪一頭開始暴力遍歷，所以如果LinkedList有100000個Node，那最遠的那個Node如果調用get方法就需要遍歷50000次。

所以普通for循環遍歷一次n個節點的LinkedList需要1+2+3+...+n/2+n/2+...+3+2+1次，時間復雜度可以寫作O(n^2^)。

增強for循環

可以看到最終是調用了LinkedList的內部類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循環涉及的方法，代碼其實也很簡單。如果 hasNext() 存在，就調用next() ，兩個Node：lastReturned和next。

每次獲取index的時候調用 ListItr(int index) 后next會指向當前index的Node。

調用next的時候lastReturned會指向next也就是當前index的Node，next指向next.next，所以每次遍歷的時候只要賦值一次就可以得到next的節點，所以遍歷一個n個節點的LinkedList就是需要n次。

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

這就是為什么兩個for循環的方式這么區別這么大了~我們也可以直觀的看出來當n到達十萬這個級別的時候O(n^2^)和O(n)差別有多大了。

不知道各位發現沒有，Iterator里面每個操作都先調用了 checkForComodification() 方法，判斷 (modCount != expectedModCount) 是否相等。

各位應該發現了ListItr有一個賦值，把modCount賦值給了expectedModCount，但每次調用遍歷或者addsetget的時候都會判斷這兩個值是否相等。

modCount是父類AbstractList的屬性，而每次調用add(),remove()方法的時候這個值都會變，也就是如果集合里面內容修改了modCount都會發生改變。

So，在使用Iterator的時候不能調用add()或者remove()這些會改變集合內容的方法。兩種情況：

• 在增強型for循環里面不能有add或者remove操作，使用Iterator迭代的時候不能做add或者remove操作。

• 如果有其他線程操作集合，需要加鎖避免改變集合，等待循環結束之后再修改。

否則都會報ConcurrentModificationException。

讀到這里，這篇“遍歷LinkedList要用增強型for循環的原因是什么”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。