为什么遍历LinkedList要用增强型for循环

超、凢脫俗 2023-09-25 22:58 64阅读 0赞

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()这些会改变集合内容的方法。两种情况：

1.  在增强型for循环里面不能有add或者remove操作，使用Iterator迭代的时候不能做add或者remove操作。
2.  如果有其他线程操作集合，需要加锁避免改变集合，等待循环结束之后再修改。

否则都会报**ConcurrentModificationException**。

作者：Yocn  
链接：https://juejin.cn/post/7219738264851955770