Java - ListIterator 实现细节
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20444586/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java - ListIterator Implementation Specifics
提问by Adam R.
I have a quick question about how ListIterators (and, I guess, Iterators in general) perform in Java. For, say, a Linked List (Java's standard one), if I get a ListIterator for it, does it loop through the entire list to build it? I'm using this to implement a fairly standard hash table, and I'm worried that using an iterator as opposed to writing a class of my own to do it would hamper my performance to O(n) always, as opposed to at worst.
我有一个关于 ListIterators（我猜是一般的 Iterators）在 Java 中如何执行的快速问题。比如说，一个链表（Java 的标准链表），如果我得到一个 ListIterator，它是否会遍历整个链表来构建它？我正在使用它来实现一个相当标准的哈希表，并且我担心使用迭代器而不是编写我自己的类来执行它会妨碍我的性能总是 O(n)，而不是最坏的.
采纳答案by zapl
Building a ListIteratordoes not iterate over the List. It's essentially just initializing the current position in the list.
构建 aListIterator不会迭代List. 它本质上只是初始化列表中的当前位置。
And that position is updated whenever you call .next().
只要您调用 ，该位置就会更新.next()。
Example implementation in LinkedList
示例实现 LinkedList
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
And ArrayList
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
It is no requirement that constructing an Iteratoris free. Imagine a Tree: Iterating over it could be implemented by building a linear representation first and then iterating that list. (I don't know of such an implementation though) That would be O(N) for construction, O(1) per .next()
没有要求构建一个Iterator是免费的。想象一棵树：迭代它可以通过首先构建一个线性表示然后迭代该列表来实现。（虽然我不知道这样的实现）对于构造来说，这将是 O(N)，每个 O(1).next()
Alternatively you could search the next element each time: that would be a O(log N) operation for each .next()but O(1) for creation. (Java's TreeMapdoes that)
或者，您可以每次都搜索下一个元素：这将是每个元素的 O(log N) 操作，.next()但创建的 O(1)操作。（Java 就是TreeMap这样做的）
Another option is to build a stack/heap of nodes to visit as you go. Guava's TreeTraverseruses this approach. Should be O(1) per .next()and O(1) for initialization.
另一种选择是构建一个堆栈/堆节点，以便随时访问。Guava 的TreeTraverser使用这种方法。应该是 O(1) per.next()和 O(1) 初始化。
