Java: итератор, указывающий на последний элемент в LinkedList

Question

В Java LinkedLists у нас есть итераторы.

Я могу использовать ListIterator, а затем выполнить линейный поиск, чтобы найти последний элемент, на который указывает итератор.Но это займет O (N) время.Как я могу найти Итератор, который указывает на последний элемент за время O (1)?

Answer 1

java.util.LinkedList на самом деле является двусвязным вариантом. Это может пройти с обоих концов. Следовательно, получение первого и последнего элемента одинаково быстро.

По крайней мере, так обстоит дело с реализацией Sun (Oracle?).

Answer 2

По определению связанного списка, указатель существует только на заголовок или первый элемент, и доступ ко всем остальным узлам возможен только последовательно!Боюсь, ответ НЕТ!Нет способа получить доступ к последнему элементу за O (1).Вы можете поместить содержимое связанного списка в массив или карту, и тогда следующий доступ может быть O (1)

Answer 3

Я не уверен, что это O (1), но если вы действительно хотите использовать итератор для последнего элемента (вместо простого получения последнего элемента), вы можете использовать метод listIterator (index), где index позиция в списке, с которой должен начинаться итератор.