В чем разница между временем вставки в ArraiList и LinkedList

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