Почему утверждение «вставка в середину LinkedList работает за O(1)» вводит в заблуждение?
O(1) — только перецепление ссылок. Чтобы вставить по индексу, сначала нужно дойти до позиции — O(n). Итого add(i, x) линейный и у LinkedList, и у ArrayList.
- Настоящая константа — вставка через ListIterator, который уже стоит на месте
- У ArrayList наоборот: поиск O(1), сдвиг O(n), но сдвиг быстрый (arraycopy)
- Края списка — O(1) у обоих (ArrayList — в конец)
А ещё Асимптотика без константы вводит в заблуждение
Подробно
Полная стоимость операции складывается из поиска и изменения. У связного списка поиск линейный, у массива — константный, зато изменение наоборот. Поэтому add(i, e) стоит O(n) в обеих реализациях, просто время уходит в разное. Настоящая константа получается, когда позиция уже в руках: обход через ListIterator с последующим add/remove, либо работа с началом и концом списка. Именно поэтому LinkedList имеет смысл как очередь или дек, но и там ArrayDeque обычно быстрее.
Что хотят услышать
- Разделение поиска и вставки.
- Когда действительно O(1).
Частые ошибки
- Сравнивать структуры по асимптотике одной операции, забывая про стоимость поиска позиции.
- Выбирать LinkedList «потому что много вставок» без учёта паттерна доступа.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Утверждение верно для любой позиции, а ArrayList вставляет в середину за O(log n)
- ✗Вставка в LinkedList на самом деле требует копирования всех узлов после позиции
- ✗LinkedList не поддерживает вставку в середину
- ✓Перецепить ссылки — O(1), но до нужной позиции сначала приходится дойти по узлам за O(n)
Что спросят дальше
- В каких случаях LinkedList действительно выигрывает?
- Почему ArrayDeque обычно предпочтительнее LinkedList в роли очереди?
Разбор темы
- LinkedList и миф о дешёвой вставке
Двусвязные узлы, реальная стоимость операций, cache locality и почему ArrayList/ArrayDeque почти всегда лучше.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.