乐趣区

关于java:从源码解读Java列表的遍历效率

Java 列表应该如何遍历效率更好?

Java 有三种遍历的形式:

  • 一般 for 循环遍历 (for)
  • 增强型 for 循环遍历 (foreach)
  • 迭代器循环遍历 (iterator)

这三种遍历形式是有差异的。

上面先用一个程序来比照不同的列表用不同的遍历形式所花的工夫差异:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangjianhua
 * @date 2021-05-09 16:08
 * @description 列表 for 循环
 */
@SuppressWarnings("ALL")
public class Main {public static void main(String[] args) {testForeachTransform();

        long arrayListForTime = arrayListForTime();

        System.out.println("测试 ArrayList 通过 for 遍历耗费工夫:" + arrayListForTime);

        long arrayListForeachTime = arrayListForeachTime();

        System.out.println("测试 ArrayList 通过 foreach 遍历耗费工夫:" + arrayListForeachTime);

        long arrayListIteratorTime = arrayListIteratorTime();

        System.out.println("测试 ArrayList 通过 iterator 遍历耗费工夫:" + arrayListIteratorTime);

        long linkedListForTime = linkedListForTime();

        System.out.println("测试 LinkedList 通过 for 遍历耗费工夫:" + linkedListForTime);

        long linkedListForeachTime = linkedListForeachTime();

        System.out.println("测试 LinkedList 通过 foreach 遍历耗费工夫:" + linkedListForeachTime);

        long linkedListIteratorTime = linkedListIteratorTime();

        System.out.println("测试 LinkedList 通过 iterator 遍历耗费工夫:" + linkedListIteratorTime);

        // 依据测试后果:// ArrayList 通过 for 遍历和通过 iterator 遍历差不多
        // LinkedList 通过 iterator 遍历比通过 for 遍历要快很多

        // 在咱们的利用中,要思考应用 List 接口的哪种实现类,能够更好更高效的满足理论场景需要
        // 通过实现 RandomAccess 接口来辨别 List 的哪种实现类

        // 实现 RandomAccess 接口的 List 通过 for 遍历数据,和通过 iterator 遍历数据差不多
        // 未实现 RandomAccess 接口的 List 通过 iterator 遍历数据,比通过 for 遍历数据高效很多
    }

    /**
     * 测试 foreach 转换成什么
     */
    private static void testForeachTransform() {System.out.println("测试 foreach 转换成什么");

        // 对于根本类型数组,foreach 遍历会转为 for 遍历,因为没有实现 iterator
        // 对于 List,foreach 遍历会转为 iterator 遍历,因为实现了 iterator

        // 运行后查看编译后的 class 文件即可看到 foreach 转换成什么

        int[] arrays = {1, 2, 3, 4, 5};

        for (int i = 0; i < arrays.length; ++i) { }

        for (int array : arrays) { }

        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        for (int i = 0; i < list.size(); ++i) { }

        for (int element : list) {}}

    /**
     * 测试 ArrayList 通过 for 遍历耗费工夫
     *
     * @return 耗费工夫
     */
    private static long arrayListForTime() {List<Integer> arrayList = new ArrayList<>();

        for (int i = 0; i < 100000; i++) {arrayList.add(i);
        }

        // 记录开始工夫
        long startTime = System.currentTimeMillis();

        // 通过 for 遍历
        for (int i = 0; i < arrayList.size(); i++) {arrayList.get(i);
        }

        // 记录完结工夫
        long endTime = System.currentTimeMillis();

        // 返回耗费工夫
        return endTime - startTime;
    }

    /**
     * 测试 ArrayList 通过 foreach 遍历耗费工夫
     *
     * @return 耗费工夫
     */
    private static long arrayListForeachTime() {List<Integer> arrayList = new ArrayList<>();

        for (int i = 0; i < 100000; i++) {arrayList.add(i);
        }

        // 记录开始工夫
        long startTime = System.currentTimeMillis();

        // 通过 foreach 遍历
        for (int array : arrayList) { }

        // 记录完结工夫
        long endTime = System.currentTimeMillis();

        // 返回耗费工夫
        return endTime - startTime;
    }

    /**
     * 测试 ArrayList 通过 iterator 遍历耗费工夫
     *
     * @return 耗费工夫
     */
    private static long arrayListIteratorTime() {List<Integer> arrayList = new ArrayList<>();

        for (int i = 0; i < 100000; i++) {arrayList.add(i);
        }

        // 记录开始工夫
        long startTime = System.currentTimeMillis();

        // 通过 iterator 遍历
        Iterator<Integer> iterator = arrayList.iterator();
        while (iterator.hasNext()) {iterator.next();
        }

        // 记录完结工夫
        long endTime = System.currentTimeMillis();

        // 返回耗费工夫
        return endTime - startTime;
    }

    /**
     * 测试 LinkedList 通过 for 遍历所耗费工夫
     *
     * @return 耗费工夫
     */
    private static long linkedListForTime() {List<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 100000; i++) {linkedList.add(i);
        }

        // 记录开始工夫
        long startTime = System.currentTimeMillis();

        // 通过 for 遍历
        for (int i = 0; i < linkedList.size(); i++) {linkedList.get(i);
        }

        // 记录完结工夫
        long endTime = System.currentTimeMillis();

        // 返回耗费工夫
        return endTime - startTime;
    }

    /**
     * 测试 LinkedList 通过 for 遍历所耗费工夫
     *
     * @return 耗费工夫
     */
    private static long linkedListForeachTime() {List<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 100000; i++) {linkedList.add(i);
        }

        // 记录开始工夫
        long startTime = System.currentTimeMillis();

        // 通过 foreach 遍历
        for (int array : linkedList) { }

        // 记录完结工夫
        long endTime = System.currentTimeMillis();

        // 返回耗费工夫
        return endTime - startTime;
    }

    /**
     * 测试 LinkedList 通过 iterator 遍历所耗费工夫
     *
     * @return 耗费工夫
     */
    private static long linkedListIteratorTime() {List<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 100000; i++) {linkedList.add(i);
        }

        // 记录开始工夫
        long startTime = System.currentTimeMillis();

        // 通过 iterator 遍历
        Iterator<Integer> iterator = linkedList.iterator();
        while (iterator.hasNext()) {iterator.next();
        }

        // 记录完结工夫
        long endTime = System.currentTimeMillis();

        // 返回耗费工夫
        return endTime - startTime;
    }

}

来看运行后果:

咱们能够发现,对于程序式列表 ArrayList,一般 for 循环、增强型 for 循环、迭代器循环三者差异不大,遍历 10 万次都是破费 2ms。

然而对于链式列表 LinkedList,一般 for 循环和增强型 for 循环、迭代器循环的差异十分大,一般 for 循环遍历 10 万次破费 4390ms,而增强型 for 循环、迭代器循环遍历 10 万次仅破费 3ms、1ms。

为什么会这样?

因为程序式列表用三种遍历的任意一种,工夫复杂度都是 O(n)。而链式列表用一般 for 循环遍历,工夫复杂度是 O(n^2),然而如果链式列表用增强型 for 循环、迭代器循环的工夫复杂度是 O(n),相差了一个数量级的工夫,所以链式列表用一般 for 循环遍历会很慢。

首先,对于列表的增强型 for 循环,其实是等同于迭代器循环的。

如何看出的?

能够看编译后的 class 文件,通过反编译能够看到列表的增强型 for 循环转换为迭代器循环。不过这里要说一下,对于根本类型的数组应用增强型 for 循环,编译后是转换为一般 for 循环的,不是转换为迭代器循环,因为根本类型的数组没有定义迭代器循环的办法,所以就转换为了一般 for 循环。

下面运行程序的 testForeachTransform 办法,有做了列表的增强型 for 循环和根本类型数组的增强型 for 循环的转换比照测试,运行程序后查看编译后的 class 文件,能够看到转换成了什么代码,前面的剖析会具体开展说。

因为对于列表,增强型 for 循环转换为迭代器循环,而列表分为程序式和链式,所以从四个方面去剖析:

  • 程序式列表的一般 for 循环
  • 程序式列表的增强型 for 循环
  • 链式列表的一般 for 循环
  • 链式列表的增强型 for 循环

为什么链式列表用了迭代器循环会比一般 for 循环少一个指数数量级的工夫?咱们能够通过看源码找到答案。

上面手把手地教大家如何看源码,如何从源码中找到遍历效率的答案:

筹备

这里以 jdk1.8 作为测试,从 GitHub 找到测试源码,地址:https://github.com/zjhpure/so…

用 idea 关上,关上如图所示的中央。

1、程序式列表的一般 for 循环

找到 arrayListForTime 办法,如下图:

从代码能够看出,记录开始工夫和记录完结工夫之间的代码就是 for 循环耗费的工夫,遍历的每一次都是调用 get 办法,所以只有晓得 get 办法耗费的工夫是多少,就能晓得 for 循环一共耗费多少工夫。咱们先通过 idea 的跳转性能,看看 get 办法的源码,然而跳转后显示的是一个接口,如下图:

怎么办?应该怎样才能找到 get 办法的源码?

这时候须要通过打断点来调试,能力找到 get 办法的源码。在 get 办法处打一个断点,点击调试按钮,程序运行后会跳到 get 办法处停着,调试时执行 Force Step Into,跳入到 get 办法的源码中,就能够看到 get 办法的源码,如下图:

咱们能够看到 get 办法源码是长这样的,如下图:

如果在调试看 get 办法的源码时又遇到接口,继续执行 Force Step Into,跳进办法外部,就能够看到办法的源码。前面还会有很多看源码的操作,就不会再细写怎么找到源码的办法了,同样依照下面的操作就能找到。

回到源码,这里由两局部组成,首先执行 rangeCheck 办法,再执行 elementData 办法。第一步的 rangeCheck 办法,其实就是查看输出的下标是否超过了数组的长度 size,源码如下:

    /**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void rangeCheck(int index) {if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

第二步的 elementData 办法,源码如下:

    // Positional Access Operations

    @SuppressWarnings("unchecked")
    E elementData(int index) {return (E) elementData[index];
    }

这里间接就是从 elementData 数组中取元素,因为是程序式列表,底层是用数组保留元素的,通过 idea 点击跳转 elementData 能够看到 elementData 是一个数组,如下图:

所以综上所述能够看到,对于程序式列表的一般 for 循环,每次 get 办法的工夫复杂度是 O(1),遍历 n 个元素的工夫复杂度是 O(n)。

2、程序式列表的增强型 for 循环

对于列表,增强型 for 循环会转换为迭代器循环,能够从 Java 运行后编译的 class 文件找到答案,咱们先找到 testForeachTransform 办法,如下图:

点击运行程序,查看编译生成的 class 文件,咱们能够看到,对于根本类型数组,增强型 for 循环转换为一般 for 循环,而对于列表,增强型 for 循环转换为迭代器循环,如下图:

所以剖析列表的增强型 for 循环,其实就是剖析列表的迭代器循环,上面剖析程序式列表的迭代器循环

咱们找到 arrayListIteratorTime 办法,如下图:

遍历的每一次都是调用 next 办法,所以只有晓得 next 办法耗费的工夫是多少,就能晓得迭代器循环一共耗费多少工夫。列表 arrayList 先调用 iterator 办法获取迭代器 iterator,而后每次遍历调用迭代器 iterator 的 next 办法,咱们先看 iterator 办法的源码,如下:

    /**
     * Returns an iterator over the elements in this list in proper sequence.
     *
     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator<E> iterator() {return new Itr();
    }

在 iterator 办法里,创立一个 Itr 对象,Itr 类是一个外部类,咱们再看 Itr 类的源码,如下:

    /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {return cursor != size;}

        @SuppressWarnings("unchecked")
        public E next() {checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {return;}
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();}

        final void checkForComodification() {if (modCount != expectedModCount)
                throw new ConcurrentModificationException();}
    }

正好能够看到 Itr 类有一个 next 办法和 hasNext 办法,在 while 循环的条件里调用的就是 hasNext 办法,从源码能够看到,hasNext 办法就是判断游标 cursor 是否等于列表的长度 size,一旦等于,while 循环完结。

咱们来剖析 next 办法,next 办法的源码只有三句是要害,如下图:

ArrayList.this.elementData 就是获取列表的数组,而后 cursor=i + 1,就是游标加 1,最初从数组 elementData 中取元素,返回元素。

所以综上所述能够看到,对于程序式列表的增强型 for 循环 (迭代器循环),每次 next 办法的工夫复杂度是 O(1),遍历 n 个元素的工夫复杂度是 O(n)。

3、链式列表的一般 for 循环

找到 linkedListForTime 办法,如下图:

用同样的办法去浏览源码,咱们能够发现遍历的每一次都是调用 get 办法,所以只有晓得 get 办法耗费的工夫是多少,就能晓得 for 循环一共耗费多少工夫。找到 get 办法的源码,如下:

    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {checkElementIndex(index);
        return node(index).item;
    }

先调用 checkElementIndex 办法,再返回 node(index).item。咱们来看 checkElementIndex 办法的源码,如下:

    private void checkElementIndex(int index) {if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

这里调用了 isElementIndex 办法,再看 isElementIndex 办法的源码,如下:

    /**
     * Tells if the argument is the index of an existing element.
     */
    private boolean isElementIndex(int index) {return index >= 0 && index < size;}

从源码能够看到,这个办法的意思就是判断是否是元素的下标,其实和程序式列表的 rangeCheck 办法差不多,都是判断下标的合法性。那么再看后面 get 办法的 node(index).item,源码如下:

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {// assert isElementIndex(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;
        }
    }

因为是链式列表,底层用链表保留元素。从 node 办法的源码能够看出整个过程,先判断下标地位是在两头靠右还是两头靠左,如果两头靠左,那就从开始节点往后面一个一个地寻找,如果是两头靠右,那就从完结节点往前面一个一个地寻找,所以链式列表寻找一个元素的工夫复杂度是 O(n)。

从这里就能够看出,链式列表寻找一个元素的效率就比程序式列表寻找一个元素的效率要低很多了,因为程序式列表寻找一个元素的工夫复杂度是 O(1),链式列表寻找一个元素的工夫复杂度是 O(n)。

因为要有 n 个元素须要遍历,所以链式列表遍历 n 个元素的工夫复杂度是 O(n^2),链式列表的一般 for 循环很慢,比程序式列表的一般 for 循环慢了一个数量级。

然而链式列表寻找一个元素并不是每一个都要 n 次能力找到的,依据这里的源码能够发现,会依据下标在两头靠右还是靠左来判断是从开始节点往后还是从完结节点往前,综合起来,寻找的工夫是 1,2,3,4…n/2,n/2…4,3,2,1。

总次数:(1+n/2)n/2=3/4n^2,四分之三 n 的平方,同样也是 n 的平方的数量级。

所以综上所述能够看到,对于链式列表的一般 for 循环,每次 get 办法的工夫复杂度是 O(n),遍历 n 个元素的工夫复杂度是 O(n^2)。

4、链式列表的增强型 for 循环

对于链式列表,增强型 for 循环同样也会转换为迭代器循环。

所以剖析列表的增强型 for 循环,其实就是剖析列表的迭代器循环,上面剖析链式列表的迭代器循环

咱们找到 linkedListIteratorTime 办法,如下图:

遍历的每一次都是调用 next 办法,所以只有晓得 next 办法耗费的工夫是多少,就能晓得迭代器循环一共耗费多少工夫。列表 linkedList 先调用 iterator 办法获取迭代器 iterator,而后每次遍历调用迭代器 iterator 的 next 办法,咱们先看 iterator 办法的源码,如下:

    /**
     * Returns an iterator over the elements in this list (in proper
     * sequence).<p>
     *
     * This implementation merely returns a list iterator over the list.
     *
     * @return an iterator over the elements in this list (in proper sequence)
     */
    public Iterator<E> iterator() {return listIterator();
    }

在 iterator 办法里,调用 listIterator 办法,源码如下:

    /**
     * {@inheritDoc}
     *
     * <p>This implementation returns {@code listIterator(0)}.
     *
     * @see #listIterator(int)
     */
    public ListIterator<E> listIterator() {return listIterator(0);
    }

在 listIterator 办法里,调动办法 listIterator(0),这里的意思是从链表的第一个元素开始,源码如下:

    /**
     * Returns a list-iterator of the elements in this list (in proper
     * sequence), starting at the specified position in the list.
     * Obeys the general contract of {@code List.listIterator(int)}.<p>
     *
     * The list-iterator is <i>fail-fast</i>: if the list is structurally
     * modified at any time after the Iterator is created, in any way except
     * through the list-iterator's own {@code remove} or {@code add}
     * methods, the list-iterator will throw a
     * {@code ConcurrentModificationException}.  Thus, in the face of
     * concurrent modification, the iterator fails quickly and cleanly, rather
     * than risking arbitrary, non-deterministic behavior at an undetermined
     * time in the future.
     *
     * @param index index of the first element to be returned from the
     *              list-iterator (by a call to {@code next})
     * @return a ListIterator of the elements in this list (in proper
     *         sequence), starting at the specified position in the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @see List#listIterator(int)
     */
    public ListIterator<E> listIterator(int index) {checkPositionIndex(index);
        return new ListItr(index);
    }

在另一个 listIterator 办法里,调用 checkPositionIndex 办法,而后创立一个 ListItr 对象,ListItr 类是一个外部类,咱们先看 checkPositionIndex 办法,源码如下:

    private void checkPositionIndex(int index) {if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

在 checkPositionIndex 办法里,调用 isPositionIndex 办法,源码如下:

    /**
     * Tells if the argument is the index of a valid position for an
     * iterator or an add operation.
     */
    private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}

从源码能够看到,isPositionIndex 办法的意思就是判断是否是元素的下标,和程序式列表的 rangeCheck 办法差不多,都是判断下标的合法性。咱们再看 ListItr 类的源码,如下:

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

        public boolean hasPrevious() {return nextIndex > 0;}

        public E previous() {checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {return nextIndex;}

        public int previousIndex() {return nextIndex - 1;}

        public void remove() {checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        public void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();}

        final void checkForComodification() {if (modCount != expectedModCount)
                throw new ConcurrentModificationException();}
    }

正好能够看到 ListItr 类有一个 next 办法和 hasNext 办法,在 while 循环的条件里调用的就是 hasNext 办法,从源码能够看到,hasNext 办法就是判断游标 nextIndex 是否等于列表的长度 size,一旦等于,while 循环完结。

咱们来剖析 next 办法,从 next 办法的源码能够发现,它在沿着链表一直往后遍历,如下图:

所以迭代器循环遍历 n 个元素的工夫复杂度是 O(n),比一般 for 循环遍历 n 个元素的 O(n^2) 快了一个数量级。

为什么忽然就升高一个数量级了?

咱们认真比照下面的源码就能够看出,其实迭代器循环的遍历只是扭转了一下思路,对于链式列表的一般 for 循环,每次查找一个元素都要从链表的开始节点或完结节点往两头一个一个地找,这样找一个元素,那就要 O(n) 的工夫复杂度了。然而咱们想一下,原本就是要遍历全副元素的,能不能不要每次都从新寻找一次元素?当然能够,因为每一个元素都保留有下一个节点的地址,所以就能够换一个思路了,从开始节点开始遍历,通过节点找到下一个节点,再通过下一个节点找到下下一个节点,直到完结节点,就不须要每次寻找一个元素都要从新寻找一次了。

迭代器循环的遍历就是下面的思路。一个思路的简略扭转,就能把工夫升高一个数量级。

对于链式列表,应用一般 for 循环遍历,每次 get 办法的工夫复杂度是 O(n),然而应用迭代器循环遍历,每次 next 办法的工夫复杂度是 O(1),所以可能大幅减低工夫。而链式列表之所以每次 next 办法的工夫复杂度是 O(1),是因为每次 next 办法都是将指针向后挪动一位,而不是像一般 for 循环的 get 办法那样从头到尾寻找一次。

所以综上所述能够看到,对于链式列表的增强型 for 循环 (迭代器循环),每次 next 办法的工夫复杂度是 O(1),遍历 n 个元素的工夫复杂度是 O(n)。

总结

依据测试后果:

  • ArrayList 通过一般 for 循环遍历 10 万条数据,破费 2ms,工夫复杂度 O(n)。
  • ArrayList 通过增强型 for 循环遍历 10 万条数据,破费 2ms,工夫复杂度 O(n)。
  • ArrayList 通过迭代器循环遍历 10 万条数据,破费 2ms,工夫复杂度 O(n)。
  • LinkedList 通过一般 for 循环遍历 10 万条数据,破费 4390ms,工夫复杂度 O(n^2),显著慢很多。
  • LinkedList 通过增强型 for 循环遍历 10 万条数据,破费 3ms,工夫复杂度 O(n)。
  • LinkedList 通过迭代器循环遍历 10 万条数据,破费 1ms,工夫复杂度 O(n)。

论断:

  • 对于程序式列表,应用一般 for 循环遍历数据
  • 对于链式列表,应用增强型 for 循环遍历数据

公众号:纯净编程说 (chunjie_tech)

原文链接:https://mp.weixin.qq.com/s/A8…

退出移动版