Java ListIterator Performance

Question

Я читал thread здесь о производительности java ArrayList и LinkedList. Существует ответ от Mr Kevin Brock, который гласит следующее.

«Связанный список добавить не всегда O (1) [или это должно сказать addLast() является O (1)]. Это только справедливо, если все сделано из в ListIterator. Надстройка методы в реализации LinkList Java должны искать в списке, если дополнения не находятся на голове или хвосте. "

Я не понимаю, что он имел в виду под «только если это сделано через ListIterator». Означает ли это, что в связанном списке есть структура данных, которая содержит ссылку на каждый индекс, и как только мы получим классификатор из определенного индекса, то листератор сразу возвращается без прохождения списка, чтобы найти этот индекс?

Спасибо, ребята!

Answer 1

Это означает, что итератор указывает на узлы списка напрямую; и поэтому доступ через get (int) будет O (N), но iterator.next() wil будет O (1). У последнего есть прямая ссылка и не нужно ничего проходить; прежнему нужно будет пройти от главы списка.

Answer 2

Если вы добавите ссылку LinkedList, на которую указывает ListIterator, это O (1). Это то же самое, что добавить к началу LinkedList или конец ArrayList.

Answer 3

Комментарий относится к методу добавления двух аргументов, [add(int,E)] [1]. Предполагая линейно распределенный индекс, тогда это будет O (n), поскольку список должен быть итерирован, чтобы найти соответствующий узел. Он не применяется к add(E).

[1]: http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html#add(int, E)