ArrayList работает быстрее, когда речь идет о случайном доступе к элементам (получение элемента по индексу) благодаря тому, что элементы хранятся в виде массива в непрерывной области памяти.
LinkedList быстрее при вставке или удалении элементов в середине списка, так как для этого достаточно обновить ссылки соседних элементов, а не сдвигать все последующие элементы, как в ArrayList.
| Операция | ArrayList | LinkedList |
|---|---|---|
| Получение | O(1) | O(n) (в худшем случае) |
| Вставка/Удаление в конец | O(1) на практике, O(n) в худшем случае (при расширении) | O(1) |
| Вставка/Удаление в середине | O(n) | O(1) (при известном итераторе), O(n) (при поиске) |