Запутанный момент в документации по списку

Question

Мне не ясно по пункту в документации Список .

Там написано:

i) Обратите внимание, что эти операции могут выполняться во времени, пропорциональном значение индекса для некоторых реализаций (класс LinkedList, для пример).
ii) Таким образом, перебор элементов в списке обычно предпочтительнее индексировать через него, если вызывающий не знает осуществление.

Обратите внимание, что я поставил (i) и (ii) в цитате.

Точка (i) довольно очевидна из-за способа доступа к связанному списку по сравнению со случайным доступом к массиву.

Хотя я не могу понять пункт (ii).
Что мы получим, выбрав итератор, если не знаем реализацию?
Я имею в виду, если реализация LinkedList, есть ли разница в производительности, чем доступ по индексу?
Я думаю, нет, так как Iterator будет манипулировать LinkedList в любом случае.
Так что не будет никакой разницы.

Так в чем же смысл рекомендации (ii) в документе?

Answer 1

Итератор связанного списка может просто иметь указатель на следующий узел в списке и переходить к следующему узлу каждый раз, когда вызывается next().Это не начинается с самого начала каждый раз.Принимая во внимание, что если вы используете индекс и вызываете get(i), связанный список должен выполнять итерацию от начала до i-го элемента на каждой итерации.

Что вы пропустили, так это то, что реализация итератора ArrayList и одна изLinkedList совершенно разные.

Answer 2

Нет, если реализация - LinkedList, то итератор будет гораздо более эффективным - O (n) для итерации по всему списку вместо O (N ² ). Поскольку итератор предоставляется списком, он имеет доступ к внутренним структурам данных. Он может просто сохранить ссылку на «текущий узел», что делает его постоянной операцией для перехода к следующему: просто перейдите по ссылке!

(Если вы все еще в замешательстве, я предлагаю вам взглянуть на реализацию - это, вероятно, сделает ее более понятной.)