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

Метод ArrayList.get(int index) выполняется за константное время O(1), потому что ArrayList реализован на основе обычного массива (Object[] elementData).

Как это работает:

1. Прямая адресация: Доступ к элементу происходит по формуле: адрес_начала_массива + (index * размер_элемента).
2. Одна операция: Это одна арифметическая операция и одно обращение к памяти, независимо от размера списка или значения индекса.
3. Проверка границ: Единственная дополнительная работа — проверка, что индекс находится в диапазоне [0, size), что также выполняется за O(1).

Пример:

ArrayList<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
String element = list.get(1); // Мгновенный доступ к элементу "B"

Сравнение с LinkedList:

• ArrayList.get(i): O(1) — прямое вычисление позиции.
• LinkedList.get(i): O(n) — требует последовательного обхода узлов от начала или конца списка до нужного индекса, что неприемлемо для частых случайных доступов.