В чем разница временной сложности вставки в конец в ArrayList и LinkedList

Вставка в конец (`add(E element)`): **ArrayList**: - В среднем O(1) - амортизированная сложность - В худшем случае O(n) при расширении массива (копирование элементов) - Пример: ```java ArrayList list = new ArrayList<>(); list.add(1); // O(1) ``` **LinkedList**: - Всегда O(1) - просто создание нового узла - Но требует больше памяти на хранение ссылок - Пример: ```java LinkedList list = new LinkedList<>(); list.add(1); // O(1) ``` Нюанс: несмотря на одинаковую O(1), ArrayList обычно быстрее на практике из-за локальности кэша процессора (данные хранятся в непрерывной области памяти).