Сложность времени для Java ArrayList

Question

Я нашел другие записи для этого вопроса, которые касались определенных методов, но ничего комплексного. Я хотел бы проверить мое собственное понимание наиболее часто используемых методов этой структуры данных:

O (1) - постоянное время:

isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)

O (N) - линейное время:

indexof(x)
clear()
remove(x)
remove(i)

Это правильно? Спасибо за вашу помощь.

Answer 1

Лучший ресурс - прямо из официального API :

Операции size, isEmpty, get, set, iterator и listIterator выполняются в постоянное время. Операция добавления выполняется за амортизированное постоянное время, то есть для добавления n элементов требуется время O (n). Все остальные операции выполняются за линейное время (грубо говоря). Коэффициент константы является низким по сравнению с таковым для реализации LinkedList.