java LinkedList对“get（）”使用迭代器以加快迭代速度

Question

我正在读这本书：Data Structures and Algorithm Analysis in Java by Mark Weiss。有人能解释一下在调用get(i)时使用迭代器是如何减少运行时间的吗

书中的文本片段：

Answer 1

这是因为get(i)将从链表的头节点开始，然后依次移动到下一个节点，直到它返回对第i个节点的引用，也就是O(n)，因为它必须经过n，或者说i个不同的节点才能将引用返回给调用者。另一方面，迭代器将存储当前节点，每次对next()的连续调用都将简单地将引用向前推进，直接指向当前节点之后的下一个节点，这是一个O(1)操作

get(i)是泛型的，并且不假设您正在遍历列表，这意味着它不知道您之前在查看哪个节点（如果有的话）。因此，它必须通过再次遍历列表的头部来重新访问第i个节点。使用迭代器假设迭代，这意味着您之前查看的节点，或者说另一种方式，您接下来查看的节点，被假设为下一个节点，因此迭代器可以通过存储对当前节点的引用来优化。这样，它就不必通过链表的头部来查找下一个节点

Answer 2

    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)forArrayList直接从内存位置获取index处的元素
因此，get(index)在O(1)

get(index)forLinkedList通过从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 = 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 NodeIterator class帮助您保留List当前node位置的地址

同样可以使用for each as迭代器来实现，该迭代器具有更简单的代码实现

    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)