Чем ArrayList отличается от LinkedList и когда LinkedList действительно быстрее?

ЗнаниеJuniorЧасто

Проверила команда СопроводОбновлено

Короткий ответ

ArrayList хранит элементы в массиве: доступ по индексу за O(1), вставка в конец в среднем тоже, вставка в середину сдвигает хвост. LinkedList — двусвязный список: get(i) идет по узлам от ближнего края, зато вставка и удаление через итератор, который уже стоит на месте, занимают O(1). На практике почти всегда быстрее ArrayList, а для очереди берут ArrayDeque.

Почему этот вопрос задают

Вопрос отделяет тех, кто выучил таблицу сложности, от тех, кто понимает, как коллекция лежит в памяти и что из этого следует на реальном железе.

Как рассуждать

  1. Начните с устройства: массив с запасом против цепочки узлов со ссылками в обе стороны
  2. Сравните доступ по индексу, вставку в конец и вставку в середину
  3. Объясните, почему поиск места для вставки съедает выигрыш связного списка
  4. Назовите узкий случай, где LinkedList быстрее, и замену ему для очереди

Ответ с примером

Журнал показаний счетчиков управляющей компании хранит 100 000 записей за месяц. В ArrayList они лежат в одном массиве, и get(50_000) сразу вычисляет адрес ячейки. Когда массив заполнен, создается новый, примерно в полтора раза больше, и элементы копируются туда, поэтому вставка в конец в среднем стоит O(1). Вставка в середину сдвигает половину массива, но это одно быстрое копирование через System.arraycopy.

LinkedList держит каждую запись в отдельном узле со ссылками на соседей. Чтобы вставить запись в середину, ему надо пройти 50 000 узлов, разбросанных по куче, и процессор не может подгрузить их заранее. Выигрыш появляется, только когда ListIterator уже стоит на нужном месте: например, при вставке поправок рядом с найденными записями за один проход по большому журналу.

Операция на 100 000 записейArrayListLinkedList
get(50 000)одно обращение к массивуоколо 50 000 переходов по узлам
Добавить в конецзапись в свободную ячейку, изредка копированиеновый узел и две ссылки
Вставить в середину по индексусдвиг 50 000 ссылок одним копированиемоколо 50 000 переходов, потом две ссылки
Вставить через итератор на местесдвиг хвоста массивановый узел и две ссылки

ArrayList и LinkedList: в чем разница

СвойствоArrayListLinkedList
Устройствомассив с запасомдвусвязный список узлов
Память на элементссылка около 4 байт плюс запасссылка и узел около 24 байт
ИнтерфейсыList, RandomAccessList, 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 увеличивает свой внутренний массив?

Похожие вопросы

ЗнаниеMiddleЧасто

Как устроен HashMap внутри: бакеты, коллизии, расширение и деревья с Java 8?

HashMap хранит записи в массиве бакетов. Номер бакета считается из hashCode() ключа: старшие биты хеша смешиваются с младшими, результат обрезается маской по размеру таблицы. Ключи с одним номером лежат в бакете цепочкой и различаются через equals(). Когда записей больше 0,75 от емкости, таблица удваивается. С Java 8 длинная цепочка превращается в красно-черное дерево.

  • Коллекции
  • HashMap
262
ЗадачаJuniorЧасто

Удалите из списка все отмененные заказы так, чтобы не получить ConcurrentModificationException

Удаляйте через removeIf: orders.removeIf(o -> o.status() == Status.CANCELLED). Метод удаляет все подходящие элементы за O(n) и сдвигает остальные один раз. Запасной вариант — явный Iterator и его remove(). Вызов list.remove внутри for-each меняет список в обход итератора, и на следующем шаге тот бросает ConcurrentModificationException. Удаление по индексу в цикле вперед пропускает соседний элемент.

  • Коллекции
  • ArrayList
266
ЗадачаSeniorЧасто

Реализуйте LRU-кэш на заданное число элементов на основе LinkedHashMap

LinkedHashMap умеет хранить порядок доступа: передайте третьим аргументом конструктора true, это флаг accessOrder, и каждый get или put перенесет запись в конец. Переопределите removeEldestEntry, чтобы он возвращал size() > capacity: после вставки карта сама удалит самую давнюю запись. Чтение и запись идут за O(1). Класс не потокобезопасен, для общего кэша нужна синхронизация.

  • Коллекции
  • LinkedHashMap
245
ЗнаниеJuniorЧасто

Чем стек отличается от кучи в Java и что хранится в каждой области?

Стек есть у каждого потока: в нем лежат кадры вызванных методов с параметрами, локальными переменными примитивных типов и ссылками. Куча одна на всю JVM: в ней живут все объекты и массивы, и ее чистит сборщик мусора. Локальная переменная хранит в стеке ссылку, сам объект лежит в куче. Аргументы Java передает по значению: копируется число или ссылка.

  • JVM
  • память
244

Частые вопросы по теме

Короткие ответы на частые вопросы по этой теме.

Хватит сказать, что новая емкость примерно в полтора раза больше старой: в OpenJDK это oldCapacity + (oldCapacity >> 1). Важнее следствие: вставка в конец в среднем стоит O(1), а известный заранее размер лучше передать в конструктор.

Да, если вы их делали. Скажите, что коллекции сравнивают через JMH: простой цикл с System.nanoTime искажают прогрев JIT и сборка мусора. Без своих замеров опирайтесь на устройство памяти и кэш процессора.

Повторите устройство HashMap, контракт equals и hashCode и ConcurrentModificationException при удалении в цикле. От списков интервьюер часто переходит к картам, а оттуда к потокобезопасным коллекциям вроде ConcurrentHashMap.

Общие вопросы на интервью

Общий вопросС опытомЧасто

Почему вы хотите работать у нас?

Назовите две-три причины, которые связывают вас именно с этой компанией: продукт, задачи, масштаб, команда. Каждую подкрепите фактом, который нашли сами: новость, проект, текст вакансии, свой опыт клиента. Потом покажите, что принесете со своей стороны. Слова о стабильности и известном бренде подходят любой компании, поэтому на них ответ не держится.

  • мотивация
  • о компании
290
Общий вопросБез опытаЧасто

Какие у вас сильные стороны?

Хватит двух-трех сильных сторон, которые нужны на этой работе, если к каждой есть пример: что сделали и какой был результат. Берите качества из текста вакансии, а не из списка «ответственный, коммуникабельный». Без опыта примеры ищите в учебе, практике и подработке. Говорите спокойно, без лишней скромности и без хвастовства.

  • сильные стороны
  • без опыта
276
Общий вопросБез опытаЧасто

Кем вы видите себя через 5 лет?

Расскажите, какие задачи хотите решать через несколько лет и чему для этого научитесь. Свяжите план с тем, что дает эта компания, и покажите первый шаг, который уже сделали. Точную должность называть не обязательно. Важнее, чтобы план был реальным и вел через эту работу, а не мимо нее.

  • мотивация
  • карьерные планы
289
ИсторияС опытомЧасто

Расскажите о конфликте с коллегой: из-за чего он возник и как вы его решили?

Расскажите один реальный конфликт по рабочему вопросу: из-за чего разошлись, чего хотела каждая сторона и как вы договорились. Говорите спокойно, без оценок коллеги. Покажите, что вы искали решение, где-то уступили и сохранили рабочие отношения. Закончите результатом и тем, что теперь делаете, чтобы похожий спор не повторился.

  • конфликты
  • работа в команде
252
ИсторияС опытомЧасто

Каким профессиональным достижением вы гордитесь больше всего?

Назовите одно достижение, близкое к задачам новой работы, и расскажите его как историю: какая была проблема, что сделали лично вы и что изменилось в цифрах. Сильнее всего звучит результат, который держится и после вас: новый порядок работы, правило, схема. Если результат общий, прямо скажите, какая часть в нем ваша.

  • достижения
  • результат в цифрах
276
Общий вопросБез опытаЧасто

Опыта работы еще нет, а интервьюер просит рассказать о себе: что вы скажете?

Начните с того, кто вы сейчас и на какую работу пришли. Вместо стажа расскажите об учебе, практике и подработке, которые похожи на задачи вакансии, и назовите один результат с цифрой. Закончите тем, почему хотите начать карьеру именно здесь. Уложитесь в одну-две минуты и не пересказывайте резюме по порядку.

  • о себе
  • без опыта
244

Вопросы руководителю на интервью

ИсторияРуководительЧасто

Как вы делегируете задачи: что отдаете команде, а что оставляете себе?

Назовите свое правило: что вы отдаете команде и что оставляете себе, и покажите его на одной задаче. Расскажите, кому и почему передали, какие полномочия и рамки дали, как проверяли без мелкого контроля. Закончите честным итогом: что получилось хуже или медленнее, чем у вас, и что вы выиграли.

  • делегирование
  • команда
255
КейсРуководительЧасто

Два сотрудника вашей команды месяц не разговаривают друг с другом, и общий отчет уже сорвал срок — что сделаете?

Поговорите сначала с каждым по отдельности: что случилось, с чего началось и что мешает работать. Потом соберите обоих вместе и обсуждайте работу: кто за какие данные и шаги отвечает. За такой ссорой часто стоит размытая ответственность. Запишите договоренности, назовите новый срок для сорванного отчета и через пару недель проверьте, что все работает.

  • конфликт
  • ответственность
242
ИсторияРуководительЧасто

Расскажите о сотруднике, которого вы вырастили: каким он пришел и чего добился?

Возьмите одного человека и покажите путь: каким он пришел, какие задачи вы ему давали по нарастающей и чем помогали, кем он стал и за какой срок. Назовите цифру роста: новая должность, своя зона, люди в подчинении. Скажите честно, где он вырос сам, а где сработали ваши решения.

  • развитие сотрудников
  • наставничество
303
ИсторияРуководительЧасто

Расскажите о цели, которую ваша команда не выполнила: когда вы это поняли и что сделали?

Назовите цель с цифрой и честный итог. Главное в ответе — момент, когда вы поняли, что цель срывается, и по какой цифре это увидели. Дальше расскажите, кому и когда сказали, что пересобрали, чтобы спасти главное, и какой один вывод сделали для следующего плана.

  • цели
  • провал
241
Общий вопросРуководительЧасто

Как вы измеряете результат своей команды?

Назовите два-три показателя, которые отражают то, ради чего существует ваша команда, и их текущие цифры. Добавьте показатель качества, который не дает гнаться за одним числом. Скажите, как часто смотрите на цифры, кто их видит и какое решение вы приняли по ним в последний раз.

  • показатели
  • цели
216
ИсторияРуководительЧасто

Расскажите, как вы разложили цель компании на задачи для своей команды

Возьмите одну цель компании с цифрой и сроком и покажите, как вы ее разбили: на какие части, по какому признаку, какие личные цели получил каждый сотрудник. Расскажите, как следили за ходом и что меняли по дороге. Закончите итогом план-факт честно, даже если цель выполнена не целиком.

  • цели
  • планирование
227