Java

Для ArrayList или для LinkedList операция добавления элемента в середину (list.add(list.size()/2, newElement)) медленнее?



Для ArrayList:

• проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив (O(N));

• копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо (O(N));

• вставка элемента (O(1)).



Для LinkedList:

• поиск позиции вставки (O(N));

• вставка элемента (O(1)).



В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет вызова быстрого системного метода System.arraycopy().