Какую структуру данных выбрать для добавления миллиона элементов и почему

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

Умеете ли вы задать уточняющие вопросы вместо заученного «LinkedList для вставки» и знаете ли, как коллекции ведут себя в памяти, а не только в O-нотации. Следом обычно спрашивают, сколько памяти займёт миллион Integer и как растёт ArrayList.

Как отвечать

Сначала уточните: куда добавляем (в конец, в начало, в середину), что потом делаем с данными (обходим, берём по индексу, ищем), нужна ли уникальность или порядок, примитивы это или объекты, пишут ли несколько потоков.

Ответ по умолчанию для добавления в конец: ArrayList, лучше сразу с ёмкостью new ArrayList<>(1_000_000) или через ensureCapacity. Добавление амортизированно O(1): массив растёт в полтора раза, при росте с нуля до миллиона это около тридцати копирований, а с заданной ёмкостью ни одного.

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

Другие варианты по ответам на уточнения:

• примитивы: int[] или коллекции без упаковки. Миллион Integer это около 16 МБ объектов плюс 4 МБ ссылок, а int[] занимает 4 МБ;
• уникальность: HashSet с заранее рассчитанной ёмкостью, с Java 19 удобно через HashSet.newHashSet(1_000_000);
• добавление с обоих концов: ArrayDeque;
• нужна сортировка: обычно выгоднее сложить в ArrayList и отсортировать один раз, чем платить O(log n) за каждую вставку в TreeSet;
• много потоков: каждый поток копит свою часть и потом их сливают, так работает parallelStream().collect(...).

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

Выбирают LinkedList «потому что вставка O(1)». На практике ArrayList быстрее и на добавлении в конец, и на обходе.

Вставляют в начало ArrayList через add(0, x). Каждая вставка сдвигает весь массив, и миллион таких операций дают O(n²).

Путают амортизированную и худшую сложность: говорят, что добавление в ArrayList стоит O(n) из-за расширения, и не объясняют, что дорогие копирования редки и в среднем операция стоит константу.