В чем разница между ArrayList и LinkedList и когда их использовать
Что проверяют
Понимаете ли вы, чем отличается массив от связного списка по стоимости операций, и умеете ли выбирать по сценарию, а не по привычке.
Как отвечать
ArrayList хранит элементы в массиве, LinkedList это двусвязный список из узлов со ссылками.
| операция | ArrayList | LinkedList |
|---|---|---|
| доступ по индексу | за константу | обход с начала |
| вставка в конец | обычно за константу | за константу |
| вставка в середину | сдвиг хвоста | за константу, но нужно дойти |
| память | компактно | плюс две ссылки на элемент |
| обход | быстрее, данные рядом | медленнее, прыжки по памяти |
Практический вывод: ArrayList подходит почти всегда. Он выигрывает на чтении по индексу и на обходе, потому что элементы лежат подряд и хорошо ложатся в кэш процессора.
LinkedList оправдан, когда основная работа это вставки и удаления по уже имеющемуся итератору, а также когда нужна очередь с двух концов, но для последнего обычно берут ArrayDeque, он быстрее.
Где спотыкаются
Говорят «вставка в середину у LinkedList за константу» и забывают, что до середины ещё надо дойти за линейное время. Выигрыш есть только если позиция уже найдена итератором.
Не учитывают кэш процессора, а на практике именно он делает ArrayList быстрее почти во всех обходах.
Забывают про ensureCapacity и про то, что рост ArrayList это копирование массива, поэтому при известном размере его стоит задать сразу.