Какова временная сложность поиска элемента в ArrayList в Java?

Сложность поиска в ArrayList зависит от его типа:

1. Поиск по индексу (get(int index)): O(1). Прямое обращение к элементу внутреннего массива по смещению.

2. Поиск по значению (contains(Object o), indexOf(Object o)): O(n). Требуется последовательный перебор элементов (в худшем случае — всех).

Пример:

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

// O(1) - доступ по индексу
String element = list.get(1);

// O(n) - поиск по значению (линейный обход)
boolean exists = list.contains("B");
int position = list.indexOf("B");

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