Java - ListIterator实现规范

Question

我有一个关于ListIterators (我猜是一般的迭代器)在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 )操作，而对于创建，则是O(1)。(Java的TreeMap做到了这一点)

另一种选择是构建一个节点堆栈/堆，以便在执行过程中进行访问。Guava的TreeTraverser使用这种方法。每个.next()应为O(1)，初始化时应为O(1)。