LinkedList - 使用迭代器“get()”来更快地迭代

Question

我正在读这本书：Data Structures and Algorithm Analysis in Java by Mark Weiss。有人可以解释一下使用迭代器如何在调用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)
    }

get(index)for ArrayListindex直接从内存位置获取元素。
因此，get(index)在O(1)

get(index)for LinkedListindex通过从 LinkedList 的头部位置遍历列表来获取元素 at 。对于 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从列表的头部搜索。Iterator class帮助您保留当前node位置的地址 os List。

同样可以使用for-each 作为迭代器来实现，它具有更简单的代码实现。

    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)