java - LinkedList - 使用 "get()"的迭代器来更快地迭代

Question

我正在读这本书:Mark Weiss 的《Java 中的数据结构和算法分析》。有人可以解释一下在调用 get(i) 时使用迭代器如何减少运行时间吗？

书中的文本片段:

Answer 1

    Integer[] elements = new Integer[] { 4, 2, 7, 8, 1, 0, 3, 5, 9, 6 };

    List<Integer> arrayList = new ArrayList<>(Arrays.asList(elements));
    List<Integer> linkedList = new LinkedList<>(Arrays.asList(elements));

    for (int i = 0; i < elements.length; i++) { // Runs for O(n)
        Integer l1 = arrayList.get(i); // returns in O(1) 
        Integer l2 = linkedList.get(i); // returns in O(n)
    }

ArrayList 的

get(index) 直接从内存位置获取 index 处的元素。
因此，get(index)的时间为O(1)

LinkedList 的

get(index) 通过从 LinkedList 的头位置遍历列表来获取 index 处的元素。对于 LinkedList 的给定索引元素，没有可以预测的指定内存位置。
因此，get(index)的时间为O(n)

ArrayList 的总运行时间 = O(1) * O(n) = O(n)
LinkedList 的总运行时间 = O(n) * O(n) = O(n^2)

<小时/>

使用java.util.Iterator类

    Iterator iterator = arrayList.iterator();

    // total execution time: O(N)
    while (iterator.hasNext()) { // runs for each element iteratively
        System.out.print(iterator.next());
    }
    System.out.println();

    iterator = linkedList.iterator();

    // total execution time: O(N)
    while (iterator.hasNext()) { // runs for each element iteratively
        System.out.print(iterator.next());
    }
    System.out.println();

iterator.next() 只是迭代到 List 中的下一个元素。这样做的好处是我们不需要从链表的头部开始查找List Node。 迭代器类帮助您保留List当前节点位置的地址。

同样可以使用for-each as iterator来实现，它具有更简单的代码实现。

    for (Integer I : arrayList) { // runs for each element: total execution time: O(N)
        System.out.print(I); // gets in O(1)
    }

    System.out.println();

    for (Integer I : linkedList) { // runs for each element: total execution time: O(N)
        System.out.print(I); // gets in O(1)
    }

因此使用迭代器，
ArrayList 的总运行时间 = O(n)
LinkedList 的总运行时间 = O(n)