Сравнение структур
Когда выбираешь структуру данных под задачу, главный вопрос — какая операция будет выполняться чаще всего. Сводная таблица по уже знакомым структурам (детальнее — в теме «Сложность O(1) vs O(n)»):
| Структура | Поиск по значению | Доступ по индексу | Вставка в начало | Сохраняет порядок добавления |
|---|---|---|---|---|
ArrayList | O(n) | O(1) | O(n) | да |
LinkedList | O(n) | O(n) | O(1) | да |
HashMap/HashSet | O(1) | — | — | нет |
TreeMap/TreeSet | O(log n) | — | — | да, отсортированный |
Копнуть глубже
Как выбирать на практике — три вопроса:
- Нужен ли быстрый поиск “есть ли это значение”? →
HashSet/HashMap. - Нужен ли порядок (отсортированный или вставки)? →
TreeMap/TreeSet(отсортированный) илиArrayList/LinkedList(порядок вставки). - Много ли вставок в начало/середину? →
LinkedList. Если нет — почти всегдаArrayListлучше по умолчанию.
Частая ошибка новичков — использовать ArrayList.contains() там, где нужен HashSet.contains(): на маленьких данных разницы не видно, но при росте коллекции до тысяч элементов O(n)-поиск в списке начинает заметно тормозить программу.
🎤 Закрыл тему, если можешь объяснить:
• по какому критерию выбирать структуру данных под задачу;
• почему `ArrayList.contains()` в цикле — частая ошибка производительности (если дошёл до 2-го слоя).
• почему `ArrayList.contains()` в цикле — частая ошибка производительности (если дошёл до 2-го слоя).