Где вставка в середину выполнится быстрее: в ArrayList или в LinkedList

Вставка в середину быстрее в `LinkedList`. **ArrayList**: - При вставке в середину (`add(index, element)`) все элементы справа сдвигаются вправо. - Время: **O(n)** (из-за копирования массива). **LinkedList**: - Вставка в середину требует обхода до нужного узла (**O(n)**), но само добавление — **O(1)** (перелинковка ссылок). - На практике, если индекс ближе к началу/концу, обход быстрее. **Пример**: ```java List arrayList = new ArrayList<>(List.of(1, 2, 3, 4)); arrayList.add(2, 99); // Медленнее (копирование массива) List linkedList = new LinkedList<>(List.of(1, 2, 3, 4)); linkedList.add(2, 99); // Быстрее (только перелинковка) ``` **Вывод**: `LinkedList` выигрывает при частых вставках в середину, особенно в больших коллекциях.