ArrayList и LinkedList

Основа с Junior

Динамический массив и связный список изнутри, сложность операций и выбор.

Что важно знать

ArrayList — массив, растёт в 1,5 раза; доступ O(1), вставка в середину O(n) из-за сдвига.
LinkedList — двусвязный список; доступ O(n), плохая локальность памяти.
Начальная ёмкость при известном размере экономит копирования.

Критерии освоения

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 считается амортизированно O(1), хотя иногда требует копирования всего массива? Middle
Ёмкость растёт в 1,5 раза: копирования всё реже, сумма копирований на n вставок — геометрическая прогрессия, то есть O(n). На одну вставку — константа в среднем, хотя отдельная…
Что лежит в основе ArrayList? Junior
В основе — массив, который при заполнении заменяется большим с копированием элементов (примерно в 1,5 раза).
Сколько стоит получение элемента по индексу в LinkedList? Junior
O(n): произвольного доступа нет, до позиции нужно дойти по ссылкам (JDK начинает с ближнего конца).
Что верно про управление ёмкостью ArrayList? Middle
Ёмкость растёт, но не уменьшается сама; clear() обнуляет ссылки, а массив остаётся прежнего размера. Пустой ArrayList без аргументов выделяет массив лениво — при первом добавлении…

Разборы темы

ArrayList: динамический массив изнутри
Бэкенд-массив, рост в 1.5×, амортизированная O(1), стоимость вставки/удаления и когда массив лучше.
LinkedList и миф о дешёвой вставке
Двусвязные узлы, реальная стоимость операций, cache locality и почему ArrayList/ArrayDeque почти всегда лучше.

← Вся карта «Java»

Закрытая бета

Знать тему — половина дела

На живом собеседовании sotto слышит вопрос интервьюера и показывает короткий ответ и план. Оставьте контакт — пришлём доступ и промокод.

Промокод на 2 часа — сверх пробных 30 минут
Программа для Windows — скачать сразу, войти — через Яндекс ID или VK ID
Первыми узнаете о версии для Mac — пока sotto только для Windows
Прямая связь с разработчиком: что улучшить — сделаем