Java - ListIterator 实现细节

Question

我有一个简短的问题，关于 ListIterators(我想，通常是 Iterators)在 Java 中的表现。例如，对于一个链表(Java 的标准链表)，如果我为其获取一个 ListIterator，它是否会遍历整个列表来构建它？我正在使用它来实现一个相当标准的哈希表，我担心使用迭代器而不是编写我自己的类来做它会妨碍我的性能 O(n) 总是，而不是最坏的情况.

Answer 1

构建 ListIterator 不会迭代 List。它本质上只是初始化列表中的当前位置。

每当您调用 .next() 时，该位置就会更新。

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;
    }

和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];
    }

不要求构造一个Iterator是免费的。想象一棵树:迭代它可以通过首先构建一个线性表示然后迭代该列表来实现。 (虽然我不知道这样的实现)构造 O(N)，每个 .next()

O(1)

或者，您可以每次都搜索下一个元素:这对于每个 .next() 都是 O(log N) 操作，但创建 O(1)。 (Java 的 TreeMap 就是这样做的)

另一种选择是构建一个堆栈/堆节点，以便您随时访问。 Guava 的TreeTraverser使用这种方法。应该是每个 .next() 的 O(1) 和 O(1) 的初始化。