Производительность Java ListIterator

Question

Я читал поток здесь о производительности Java ArrayList и LinkedList. Есть ответ от мистера Кевина Брока , который гласит следующее.

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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