Какую операцию можно выполнить за константное время в ArrayList?

Операции за O(1) в ArrayList

ArrayList — это динамический массив, который предоставляет несколько операций с константной сложностью O(1). Это означает, что время выполнения не зависит от размера коллекции.

Основные операции O(1)

1. Получение элемента по индексу

Это главная сильная сторона ArrayList. Операция get(index) работает за O(1), потому что ArrayList внутренне использует обычный массив, и доступ к элементу по индексу требует только одно вычисление адреса в памяти.

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

// Все эти операции работают за O(1)
String first = list.get(0);   // O(1)
String second = list.get(1);  // O(1)
String last = list.get(2);    // O(1)

2. Установка элемента по индексу

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

list.set(1, "Z");  // O(1) — просто заменяем значение на позиции 1

3. Проверка размера

Метод size() возвращает количество элементов за O(1), так как ArrayList хранит размер в переменной экземпляра.

int length = list.size();  // O(1) — просто возвращает переменную

4. Проверка пустоты

Метод isEmpty() также работает за O(1).

boolean empty = list.isEmpty();  // O(1)

Операции, которые НЕ являются O(1)

Важно помнить, что другие операции требуют больше времени:

• Добавление в конец: add(E) — O(1) в амортизированном времени (когда нет пересоздания массива)
• Добавление в начало/середину: add(index, E) — O(n) — требует сдвига всех элементов после этой позиции
• Удаление: remove(index) — O(n) — требует сдвига элементов
• Поиск: indexOf(E) — O(n) — требует обхода всех элементов
• Удаление по значению: remove(Object) — O(n) — нужно найти и удалить

Практический пример

public class ArrayListComplexity {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < 1000000; i++) {
            numbers.add(i);
        }
        
        // Все эти операции выполняются одинаково быстро, независимо от размера
        int first = numbers.get(0);           // O(1)
        int middle = numbers.get(500000);     // O(1) — такая же скорость!
        int last = numbers.get(999999);       // O(1) — такая же скорость!
        
        numbers.set(500000, 999);             // O(1)
        int size = numbers.size();            // O(1)
    }
}

Внутренняя реализация

Почему это работает? ArrayList хранит элементы в обычном Java-массиве:

private Object[] elementData;  // Внутренний массив
private int size;              // Количество элементов

public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException();
    return elementData[index];  // Прямой доступ по индексу — O(1)
}

Всё это делает ArrayList идеальным выбором для случаев, когда нужен часто доступ к элементам по индексу, но при этом важно помнить о стоимости вставки/удаления в середину.