Как отличаются операции добавления элементов в ArrayList и LinkedList в Java?

В Java операции добавления элементов в ArrayList и LinkedList отличаются по производительности и внутреннему устройству:

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

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

Пример:

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("элемент"); // добавление в конец, быстро если не нужно расширение

LinkedList<String> linkedList = new LinkedList<>();
linkedList.addFirst("элемент"); // добавление в начало, быстро
linkedList.addLast("элемент");  // добавление в конец, быстро