Как ListIterator может участвовать во вставке элементов?

289

12 июня 2017, 20:39

Задание (part11.task14) из книги "Talking in Java" B. Eckel:

Создайте пустой контейнер LinkedList<Integer>. Используя итератор ListIterator, добавьте в List значения Integer; все операции вставки должны осуществляться в середине списка.

Я написал что-то в духе:

package part11.task14;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<Integer>();
        for (int i=0;i<20;i++){
            list.add(list.size()/2, i+1);
            System.out.println(list);
        }
    }
}
Output:
[1]
[2, 1]
[2, 3, 1]
[2, 4, 3, 1]
[2, 4, 5, 3, 1]
[2, 4, 6, 5, 3, 1]
[2, 4, 6, 7, 5, 3, 1]
[2, 4, 6, 8, 7, 5, 3, 1]
[2, 4, 6, 8, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 13, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 14, 13, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 14, 15, 13, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 14, 16, 15, 13, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 14, 16, 17, 15, 13, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 17, 15, 13, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1]

Собственно по порядку:

Правильно ли я понял, что автор книги ждёт именно такого объявления:

List<Integer> list = ?
Почему нельзя просто вставлять в середину элементы, как я это сделал в своём коде? Iterator замечательная вещь, когда мы пишем метод, принимающий что-то, что выражает Collection<Type> и хотим обработать каждый элемент. Но зачем нам в данном задании такой подход? Мы знаем конкретный тип LinkedList<Integer>...
Как в вашем представлении выглядит правильное решение данного упражнения? Ходить внутри ListIterator<Integer>, а как дошли до середины вызывать

it.set((int)(Math.random*1000)) ?

И вообще, .set меняет ссылку, а не добавляет... Каша в голове, помогите ;с Как ListIterator может участвовать во вставке в список?

Можно конечно над вопросом 3 подумать в следующую сторону, но это уже какая-то хиромантия:

package part11.task14;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        int i = 1, k = 10;
        List<Integer> list = new LinkedList<Integer>(Arrays.asList(new Integer[10]));
        ListIterator<Integer> it;
        while (k-- > 0) {
            it = list.listIterator();
            while (it.hasNext()) {
                it.next();
                if (it.nextIndex() == list.size() / 2){
                    it.set(i++);
                    break;
                }
            }
            System.out.println(list);
        }
    }
}
Output: 
[null, null, null, null, 1, null, null, null, null, null]
[null, null, null, null, 2, null, null, null, null, null]
[null, null, null, null, 3, null, null, null, null, null]
[null, null, null, null, 4, null, null, null, null, null]
[null, null, null, null, 5, null, null, null, null, null]
[null, null, null, null, 6, null, null, null, null, null]
[null, null, null, null, 7, null, null, null, null, null]
[null, null, null, null, 8, null, null, null, null, null]
[null, null, null, null, 9, null, null, null, null, null]
[null, null, null, null, 10, null, null, null, null, null]

Answer 1

Мне кажется, что автор упражнения хочет, чтобы вы использовали итератор, потому что так будет быстрее работать. Давайте разберёмся, почему.

Как известно, LinkedList является реализацией двусвязного списка. В двусвязном списке, в отличии от списка на основе массива, нельзя быстро получить итератор на произвольный элемент. Поэтому добавление элемента в середину списка с помощью метода add(индекс, значение) будет работать долго (пропорционально числу элементов в списке). Вставка n элементов таким алгоритмом будет работать Θ(n^2) времени, что, конечно, долго. Использование итератора позволяет написать алгоритм, работающий Θ(n) времени.

Ваш вариант с итератором также будет долго работать — фактически вы написали свою реализацию метода add(индекс, значение). Правильное решение может быть примерно таким:

Заводим один итератор. Объявить его надо снаружи цикла. Поддерживаем инвариант, что в начале каждой итерации наш итератор указывает на середину списка.
В каждой итерации:
- Добавляем элемент, вызвав метод add итератора (итератор указывает на середину списка по инварианту).
- Если итератор перестал указывать на середину списка, сдвинем итератор в нужную сторону (понятно, что придётся сдвинуть максимум на один элемент).

Возможная реализация:

List<Integer> list = new LinkedList<>();
ListIterator<Integer> iterator = list.listIterator();
for (int i = 0; i < 20; i++) {
    iterator.add(i + 1);
    if (i % 2 == 0) {
        iterator.previous();
    }
}

Вот тест для сравнения производительности двух вариантов, при вставке 20000 элементов вариант с итератором работает примерно в 500 раз быстрее, чем исходный вариант.