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

Вставка элемента в начало LinkedList выполняется быстрее, чем в ArrayList.

Причина:

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

Пример на Java:

// Быстрая вставка в начало (O(1))
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.addFirst(1);

// Медленная вставка в начало (O(n))
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0, 1); // Требует копирования массива

Вывод: Для частых операций вставки/удаления в начале или конце списка LinkedList предпочтительнее. Для частого произвольного доступа по индексу — ArrayList.