Какая операция в ArrayList выполняется за константное время

Что проверяют

Понимаете ли вы, что ArrayList построен на массиве, и можете ли вывести сложность операций из устройства, а не по памяти. Следом спрашивают про амортизированную сложность add и про то, когда лучше взять другую структуру.

Как отвечать

За O(1) выполняются операции, которым ничего не нужно сдвигать:

• get(index): адрес элемента вычисляется из индекса, поиска нет;
• set(index, value): замена на месте;
• size() и isEmpty(): размер хранится в поле;
• add(value) в конец: амортизированно O(1). Когда массив заполнен, создаётся новый примерно в 1,5 раза больше, и элементы копируются за O(n). Это случается редко, поэтому в среднем на вставку приходится константа;
• удаление последнего элемента: remove(size - 1), в Kotlin removeAt(lastIndex), сдвигать нечего.

За O(n) работают add(0, x) и remove(0) (сдвиг всего хвоста), а также contains() и indexOf() (линейный поиск через equals). Ёмкость по умолчанию 10, но массив выделяется лениво, при первом добавлении. Если размер известен заранее, передайте его в конструктор или вызовите ensureCapacity(), чтобы избежать лишних копирований.

Для Android добавьте практику. В Kotlin mutableListOf() и ArrayList() дают тот же java.util.ArrayList. ArrayList<Int> хранит упакованные Integer, и для больших наборов чисел выгоднее IntArray, а для отображения целых ключей на объекты SparseArray вместо HashMap<Int, T>. Очередь с удалением из головы строят на ArrayDeque, а не на ArrayList с remove(0). И про removeLast(): на старых версиях Android он может упасть с NoSuchMethodError, если компилятор привяжет вызов к методу из Java 21, поэтому надёжнее removeAt(lastIndex).

Где спотыкаются

Называют add просто O(1) без слова «амортизированно» и не могут объяснить, куда девается копирование массива.

Считают contains() константным, путая ArrayList с HashSet.

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