Java - ListIterator实现细节

Question

我有一个关于ListIterators(以及我猜,通常是Iterators)如何在Java中执行的快速问题.比方说,如果我得到一个ListIterator链接列表(Java标准版),它是否循环遍历整个列表来构建它？我正在使用它来实现一个相当标准的哈希表,我担心使用迭代器而不是编写我自己的类来执行它会妨碍我的性能总是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),O(1)per.next()

或者,您可以每次搜索下一个元素:这将是每个.next()O(1)的操作,但O(1)用于创建.(Java TreeMap的确如此)

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