在java中寻求对迭代器的进一步理解

Question

如果我使用for循环(循环标准,而不是增强的for语句),我无法看到迭代器在搜索集合时如何提高效率.如果我有一个如下声明:

(假设aList是通用对象的List,键入E,nextElement引用列表中的下一个元素)

for (int index = 0; index < aList.size(); index++){
E nextElement = aList.get(index);
// do something with nextElement...
}

我有一个看起来像这样的get方法:

Node<E> nodeRef = head;
for (int i = 0; i < index; i++){
    nodeRef = nodeRef.next;
    // possible other code
}

这基本上是在列表中搜索,一次一个元素.但是,如果我使用迭代器,它不会执行相同的操作吗？我知道迭代器应该是O(1)速度,但如果必须搜索整个列表,它不会是O(n)吗？

Answer 1

它主要不是效率,IMO.这是关于抽象的.使用索引将您绑定到可以有效检索给定索引的项目的集合(因此,对于链接列表,它将无法正常工作)...并且它不表达您正在尝试执行的操作,迭代列表.

使用迭代器,您可以表达迭代一系列项目的想法,无论该序列是否可以轻松地被索引,是否提前知道大小,甚至在它实际上是无限的情况下.

你的第二种情况仍然使用一个for循环来编写,这个循环会增加一个索引,这不是考虑它的惯用方式 - 它应该只是测试它是否到达终点.例如,它可能是:

for (Node<E> nodeRef = head; nodeRef != null; nodeRef = nodeRef.next)
{
}

现在我们有了正确的抽象:循环表示我们开始的地方(头部),当我们停止时(当没有更多元素时)以及我们如何从一个元素转到下一个元素(使用该next字段).这表达了比"我有一个从0开始的计数器更有效地迭代的想法,并且我将在每次迭代时询问特定计数器的值,直到计数器的值大于发生的某个值.成为清单的长度."

我们已经习惯于后一种表达事物的方式,但它并没有像迭代器方法那样真正地说出我们的意思.

Answer 2

我认为您问的问题是指迭代器与get在集合对象上使用显式的 for 循环的效率。

如果您使用的简单版本编写代码get，并使用它迭代列表，那么它会带您

操作总数n(n-1)/2为 O(n^2)。

但是，如果您使用内部跟踪下一个元素的迭代器（即前进一步），则迭代整个列表的时间复杂度为 O(n)，这是一个很大的改进。