java - Java 中 LinkedList 的迭代器时间复杂度？

Question

下面的代码将调用迭代器并将整数发送回调用它的方法。我只是想知道通过使用 Iterator 我的时间复杂度是否会变得恒定？ (即 O(1))。因为如果我将 get 与 LinkedList 一起使用，它将给我线性时间(即 O(n))。

protected int least(int i) {
    if(i >= digits.size()) {
        return 0;           
    }

    // temp++;
    // System.out.println("Time taken=" + temp);
    // long start = System.nanoTime();

    ListIterator<Integer> itr1 = digits.listIterator(digits.size() - i);

    // System.out.println("Time elapsed:" + (System.nanoTime() - start));

    return itr1.previous();
}

Answer 1

从第 i 个元素开始的迭代器

如果您创建一个直接从 LinkedList 的第 i 索引开始的 Iterator，您需要知道这也需要O(n)。在 LinkedList 中查找元素总是慢。

LinkedList 只记住列表的head(和tail)元素。需要通过遍历整个列表来找到所有其他元素。

这是一个双向链表的例子(Javas LinkedList 也是双向链表):

因此，如果您创建一个从第 i 元素开始的 Iterator，它将从 head(或 tail) 并跟随指针到达第 i 元素。这就像调用:

list.get(i);

这显然花费了 O(n)。

---

替代方案:ArrayList

如果您需要快速基于索引的访问，也称为随机访问，您可以考虑使用ArrayList。它的结构允许在O(1)中访问(它可以通过start + i * sizeof(type)直接计算元素在内存中的位置)。

提供如此快速随机访问的数据结构通常实现接口(interface) RandomAccess ( documentation and implementing classes ) 作为指示器。

---

如何迭代

如上所述，迭代 LinkedList 不应通过 list.get(i) 基于索引的访问来完成。因此，您应该使用 Iterator(或 ListIterator，如果您需要在迭代时修改列表)。

这是使用 Iterator 的常用方法:

Iterator<E> iter = list.iterator();
while (iter.hasNext()) {
    E element = iter.next();
    ...
}

或者您也可以使用增强的 for 循环，它在内部做同样的事情，但看起来更紧凑:

for (E element : list) {
    ...
}

由于 Javas LinkedList 是一个双向链表，您也可以从尾部开始反向迭代列表强>.因此，只需使用 LinkedList#descendingIterator 方法 ( documentation ) 而不是 LinkedList#iterator。

最后一个示例展示了如何在迭代时使用 ListIterator 修改列表:

ListIterator<E> listIter = list.listIterator(0);
while (listIter.hasNext()) {
    E element = listIter.next();
    ...
    // Remove the element last polled
    listIter.remove();
    // Inserts an element right before the last polled element
    listIter.add(new Element());
}

您还可以通过 hasPrevious() 和 previous() 方法使用 ListIterator 向前和向后遍历列表。这是它的 documentation .