ArrayList — динамический массив: доступ по индексу O(1), добавление в конец амортизированно O(1). LinkedList — двусвязный список: O(1) только при вставке или удалении у уже известного узла. По умолчанию — ArrayList.
А ещё LinkedList оправдан редко: много вставок через ListIterator в середину огромного списка
Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.
ArrayList хранит элементы в массиве. get(i) — прямой доступ O(1). add(e) в конец — O(1) амортизированно: когда массив заполнен, он растёт в 1,5 раза с копированием, но копирования редки. Вставка и удаление в середине — O(n): сдвиг хвоста через System.arraycopy (быстрый блочный сдвиг памяти).
LinkedList — двусвязный список узлов {prev, item, next}. get(i) — O(n): обход от ближайшего конца. Вставка и удаление — O(1), если узел уже найден (через ListIterator) или это края списка. add(i, x) по индексу сначала ищет позицию — O(n).
Почему ArrayList почти всегда выигрывает:
sottoarraycopy очень быстрый даже на тысячах элементов.Когда LinkedList: в новом коде — почти никогда. Для очередей и стеков есть ArrayDeque (кольцевой массив). Исключение — частые вставки и удаления в середине при обходе итератором огромного списка, и то стоит измерить.
Один верный вариант. Подумайте, потом откройте ответ.
Бэкенд-массив, рост в 1.5×, амортизированная O(1), стоимость вставки/удаления и когда массив лучше.
Иерархия интерфейсов, сложности операций основных структур, неизменяемые коллекции и принцип выбора по паттерну доступа.
Двусвязные узлы, реальная стоимость операций, cache locality и почему ArrayList/ArrayDeque почти всегда лучше.
sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.