Zašto je lakše tražiti elemente po indeksu u ArrayList-u nego u LinkedList-u?

В ArrayList элементы хранятся в виде массива в памяти. Для доступа к элементу по индексу используется прямое вычисление адреса памяти (базовый адрес + индекс * размер элемента), что занимает константное время O(1).

В LinkedList элементы хранятся в виде узлов, каждый из которых содержит ссылку на следующий (и, возможно, предыдущий) узел. Для доступа к элементу по индексу необходимо последовательно пройти по узлам от начала или конца списка до нужного индекса. Это занимает время, пропорциональное индексу элемента, в худшем случае O(n).