Чем ArrayList отличается от LinkedList и когда LinkedList действительно быстрее?
Проверила команда Сопровод · Обновлено
Короткий ответ
ArrayList хранит элементы в массиве: доступ по индексу за O(1), вставка в конец в среднем тоже, вставка в середину сдвигает хвост. LinkedList — двусвязный список: get(i) идет по узлам от ближнего края, зато вставка и удаление через итератор, который уже стоит на месте, занимают O(1). На практике почти всегда быстрее ArrayList, а для очереди берут ArrayDeque.
Почему этот вопрос задают
Вопрос отделяет тех, кто выучил таблицу сложности, от тех, кто понимает, как коллекция лежит в памяти и что из этого следует на реальном железе.
Как рассуждать
- Начните с устройства: массив с запасом против цепочки узлов со ссылками в обе стороны
- Сравните доступ по индексу, вставку в конец и вставку в середину
- Объясните, почему поиск места для вставки съедает выигрыш связного списка
- Назовите узкий случай, где
LinkedListбыстрее, и замену ему для очереди
Ответ с примером
Журнал показаний счетчиков управляющей компании хранит 100 000 записей за месяц. В ArrayList они лежат в одном массиве, и get(50_000) сразу вычисляет адрес ячейки. Когда массив заполнен, создается новый, примерно в полтора раза больше, и элементы копируются туда, поэтому вставка в конец в среднем стоит O(1). Вставка в середину сдвигает половину массива, но это одно быстрое копирование через System.arraycopy.
LinkedList держит каждую запись в отдельном узле со ссылками на соседей. Чтобы вставить запись в середину, ему надо пройти 50 000 узлов, разбросанных по куче, и процессор не может подгрузить их заранее. Выигрыш появляется, только когда ListIterator уже стоит на нужном месте: например, при вставке поправок рядом с найденными записями за один проход по большому журналу.
| Операция на 100 000 записей | ArrayList | LinkedList |
|---|---|---|
| get(50 000) | одно обращение к массиву | около 50 000 переходов по узлам |
| Добавить в конец | запись в свободную ячейку, изредка копирование | новый узел и две ссылки |
| Вставить в середину по индексу | сдвиг 50 000 ссылок одним копированием | около 50 000 переходов, потом две ссылки |
| Вставить через итератор на месте | сдвиг хвоста массива | новый узел и две ссылки |
ArrayList и LinkedList: в чем разница
| Свойство | ArrayList | LinkedList |
|---|---|---|
| Устройство | массив с запасом | двусвязный список узлов |
| Память на элемент | ссылка около 4 байт плюс запас | ссылка и узел около 24 байт |
| Интерфейсы | List, RandomAccess | List, Deque |
| Когда брать | почти всегда | вставки и удаления через итератор в большом списке |
Как ответить сильнее
Что добавит опытный кандидат
Что спросят следом
Доступно по подписке
Приемы опытных и готовые ответы
Частые ошибки
«В
LinkedListвставка в середину O(1), поэтому для частых вставок он лучше»Уточните, что O(1) — только перестановка ссылок. Сначала нужно дойти до места, а это O(n) по узлам, разбросанным по памяти
«
ArrayListпри каждом добавлении копирует весь массив»Объясните, что массив растет примерно в полтора раза с запасом. Копирование случается редко, поэтому вставка в конец в среднем стоит O(1)
«Для очереди лучше всего подходит
LinkedList»Назовите
ArrayDeque: он работает на кольцевом массиве, быстрее добавляет и удаляет с обоих концов и не создает узел на каждый элемент«
LinkedListэкономнее по памяти, потому что не держит запас»Посчитайте: у
ArrayListна элемент уходит ссылка около 4 байт плюс запас, уLinkedListк ссылке добавляется узел около 24 байт
Сигналы для интервьюера
Сильный ответ
Сам говорит, что учебная таблица сложности обманчива, объясняет это поиском места и кэшем процессора и предлагает ArrayDeque для очереди
Тревожный сигнал
Отвечает только таблицей сложности и не может сказать, какую коллекцию выбрал бы для журнала на миллион записей и почему
Красный флаг
Не знает, что лежит внутри ArrayList, и считает, что обе коллекции устроены одинаково и отличаются только названием
Как еще могут спросить
- В чем разница между
ArrayListиLinkedListв Java? - Какая сложность у операций
getиaddвArrayListиLinkedList? - Когда стоит использовать
LinkedListвместоArrayList? - Как
ArrayListувеличивает свой внутренний массив?











