junior
Что работает быстрее — ArrayList или LinkedList
Однозначного ответа нет — зависит от операции. Однако на практике ArrayList быстрее в большинстве сценариев благодаря cache locality (данные в массиве лежат последовательно в памяти).
| Операция | ArrayList | LinkedList |
|---|---|---|
| get(index) | O(1) | O(N) |
| add(e) в конец | O(1) амортиз. | O(1) |
| add(0, e) в начало | O(N) | O(1) |
| remove(0) из начала | O(N) | O(1) |
| remove(index) из середины | O(N) | O(N) |
| Итерация | Быстрее (cache-friendly) | Медленнее (cache miss) |
| Потребление памяти | Меньше | Больше (~40-64 байт/элемент) |
Даже для вставки в середину ArrayList часто выигрывает у LinkedList, потому что System.arraycopy() — это нативная операция, копирующая блоки памяти, а LinkedList тратит O(N) на поиск позиции вставки.
На собеседовании: не говорите «ArrayList» или «LinkedList» однозначно. Скажите «зависит от операции» и перечислите сценарии. Добавьте, что на практике ArrayList предпочтительнее из-за cache locality.