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

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

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

LinkedList不只是记住了head（和tail列表）元素。其他所有元素都需要遍历整个列表来找到。

这是一个双向链接列表的图示（Java LinkedList也是双向链接）：

因此，如果您Iterator在i-th元素处创建起始位置，则它将在head（或tail）处起始并跟随指针直至i-th元素。就像调用：

list.get(i);

这显然要付出代价O(n)。

备选：ArrayList

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

提供这种快速随机访问的数据结构通常将接口RandomAccess（文档和实现类）实现为指示符。

如何迭代

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

这是使用的通常方法Iterator：

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

或者，您也可以使用增强的for循环，该循环内部执行相同的操作，但看起来更紧凑：

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

由于Java LinkedList是双向链接的列表，因此您也可以从尾部开始，然后反向迭代该列表。因此，只需使用LinkedList#descendingIterator方法（文档）代替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());
}

您也可以ListIterator使用hasPrevious()和previous()方法来前后遍历列表。这是它的文档。