Спецификации реализации 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) для построения, O (1) per .next()

В качестве альтернативы вы могли бы искать следующий элемент каждый раз: это был бы O (log N) для каждого .next(), но O (1) для создания. (Java TreeMap делает это)

Другой вариант - построить стек/кучу узлов, которые нужно посетить, когда вы идете. Этот подход используется в TreeTraverser Гуавы. Должно быть O (1) на .next() и O (1) для инициализации.