Как перебрать элементы LinkedList в обратном порядке без медленного get(index)

Для обхода в обратном порядке используется метод descendingIterator(), который возвращает итератор, начинающий с последнего элемента и идущий к первому. Каждый переход по ссылке prev занимает O(1).

Iterator<String> it = linkedList.descendingIterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

Альтернативный способ — использовать ListIterator, инициализированный позицией в конце списка:

ListIterator<String> it = linkedList.listIterator(linkedList.size());
while (it.hasPrevious()) {
    System.out.println(it.previous());
}

Использование get(index) в цикле от конца к началу приведет к O(N^2), потому что каждый вызов get(i) потребует обхода списка от начала или конца до позиции i.

На собеседовании: назовите descendingIterator() как основной способ. Объясните, почему get(index) в цикле — это O(N^2).