Что важно знать
ArrayList— массив, растёт в 1,5 раза; доступ O(1), вставка в середину O(n) из-за сдвига.LinkedList— двусвязный список; доступ O(n), плохая локальность памяти.- Начальная ёмкость при известном размере экономит копирования.
Этап 2 из 11 · ≈ 4 ч
ArrayList и LinkedList
Основа с Junior
Динамический массив и связный список изнутри, сложность операций и выбор.
Критерии освоения
Junior ≈ 4 ч
- Объясняет устройство ArrayList и рост массива
- Называет сложность основных операций ArrayList и LinkedList
Практика. Реализовать свой динамический массив с ростом и сравнить скорость с ArrayList.
Middle ≈ 2 ч
- Объясняет, почему LinkedList на практике проигрывает даже на вставках
Практика. Замерить JMH вставку в середину ArrayList и LinkedList на разных размерах и объяснить результат.
Проверка знаний
Войдите, чтобы пройти тест: сданный тест отмечает тему пройденной на карте и в ИПР.
Вопросы с собеседований
Смотреть всеСколько стоит удаление элемента из середины ArrayList и почему?Middle
O(n): хвост сдвигается влево через System.arraycopy, последняя ячейка обнуляется. Удаление в цикле — квадратичная работа.
Полный разборЧем ArrayList отличается от LinkedList и что брать по умолчанию?Junior
ArrayList — динамический массив: доступ по индексу O(1), добавление в конец амортизированно O(1). LinkedList — двусвязный список: O(1) только при вставке или удалении у уже известного узла. По умолчанию — ArrayList.
Полный разборПочему добавление в конец ArrayList считается амортизированно O(1), хотя иногда требует копирования всего массива?Middle
Ёмкость растёт в 1,5 раза: копирования всё реже, сумма копирований на n вставок — геометрическая прогрессия, то есть O(n). На одну вставку — константа в среднем, хотя отдельная вставка бывает O(n).
Полный разборЧто лежит в основе ArrayList?Junior
В основе — массив, который при заполнении заменяется большим с копированием элементов (примерно в 1,5 раза).
Полный разборСколько стоит получение элемента по индексу в LinkedList?Junior
O(n): произвольного доступа нет, до позиции нужно дойти по ссылкам (JDK начинает с ближнего конца).
Полный разборЧто верно про управление ёмкостью ArrayList?Middle
Ёмкость растёт, но не уменьшается сама; clear() обнуляет ссылки, а массив остаётся прежнего размера. Пустой ArrayList без аргументов выделяет массив лениво — при первом добавлении (10).
Полный разборДля чего служит интерфейс Iterator?Junior
Iterator даёт единый способ обойти коллекцию, не раскрывая её устройства: hasNext() и next().
Полный разборРазборы темы
- ArrayList: динамический массив изнутри
Бэкенд-массив, рост в 1.5×, амортизированная O(1), стоимость вставки/удаления и когда массив лучше.
- LinkedList и миф о дешёвой вставке
Двусвязные узлы, реальная стоимость операций, cache locality и почему ArrayList/ArrayDeque почти всегда лучше.
Партнёр платформы
Разбор собеседования
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.