Почему получение элемента по индексу в ArrayList выполняется за константное время O(1)?

ArrayList внутри использует обычный массив (Object[] elementData) для хранения элементов.

Причина O(1)-доступа:

1. Прямая адресация: Операция get(index) сводится к доступу к элементу массива по формуле: элемент = elementData[index].
2. Вычисление адреса: Адрес в памяти вычисляется за константное время: базовый_адрес_массива + (index * размер_элемента).

Пример и сравнение:

ArrayList<String> list = new ArrayList<>();
list.add("A"); // elementData[0] = "A"
list.add("B"); // elementData[1] = "B"
list.add("C"); // elementData[2] = "C"

String item = list.get(2); // O(1): прямое чтение elementData[2] -> "C"

Контраст с LinkedList: В LinkedList для доступа к элементу по индексу n необходимо пройти последовательно через n узлов, что является операцией O(n).