В какой структуре данных Java (ArrayList или LinkedList) быстрее выполняется вставка элемента в середину?

Вставка в середину выполняется быстрее в LinkedList.

Причина:

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

Пример на Java:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        List<Integer> linkedList = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));

        // Вставка элемента 99 по индексу 2 (в середину)
        arrayList.add(2, 99);   // Медленнее: O(n) из-за сдвига элементов
        linkedList.add(2, 99);  // Быстрее: O(n) на поиск + O(1) на вставку
    }
}

Вывод: LinkedList предпочтительнее для частых операций вставки/удаления в середине списка, если не требуется интенсивный случайный доступ по индексу.