Какая сложность поиска по ключу в списке

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

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

Как отвечать

Поиск по ключу в List это линейный проход: O(n) сравнений через equals, независимо от реализации.

• ArrayList: contains, indexOf, stream().filter(...).findFirst() идут по массиву слева направо, O(n). Зато доступ по индексу get(i) стоит O(1);
• LinkedList: поиск по значению тоже O(n), а get(i) уже не O(1): список идёт от ближайшего конца, в худшем случае через n/2 узлов;
• отсортированный список: Collections.binarySearch даёт O(log n) для списков с RandomAccess. Для большого LinkedList метод делает O(log n) сравнений, но O(n) переходов по ссылкам. На неотсортированном списке результат не определён.

На практике: если поиск по ключу нужен часто, список один раз за O(n) перекладывают в HashMap, например через Collectors.toMap(User::getId, Function.identity()), и дальше ищут в среднем за O(1). Учтите, что toMap бросает исключение на дубликатах ключей. Нужен порядок ключей или диапазоны, берите TreeMap с O(log n). На десятке элементов линейный проход по ArrayList не хуже, оптимизировать стоит от реальных объёмов.

Типичный разбор кода: два списка по 100 тысяч элементов, для каждого элемента первого вызывается contains по второму. Это O(n·m), десять миллиардов сравнений. После переноса второго списка в HashSet остаётся O(n + m).

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

Путают get(index) и поиск по ключу и отвечают O(1) для ArrayList.

Забывают про equals и hashCode. Без переопределённого equals метод contains сравнивает ссылки и не находит «такой же» объект, а если переопределён только equals, HashMap перестаёт находить равные ключи.

Говорят, что LinkedList ищет быстрее, потому что «вставка у него O(1)». Вставка без поиска позиции и поиск это разные операции.