Почему вставка в начало списка имеет высокую сложность?

Почему вставка в начало массива медленная?

Массивы хранят элементы в непрерывной области памяти. Когда вы вставляете элемент в начало, все последующие элементы должны быть сдвинуты на одну позицию вправо, чтобы освободить место. Это требует O(n) операций, где n — количество элементов в массиве. Например, если у вас массив из 1000 элементов, вставка в начало потребует 1000 сдвигов.

Пример на JavaScript

let arr = [2, 3, 4, 5];
// Вставка 1 в начало
arr.unshift(1); // Сдвигает все элементы вправо
console.log(arr); // [1, 2, 3, 4, 5]

Метод unshift выполняет эту операцию за O(n). Для больших массивов это может быть неэффективно.

Сравнение со связанными списками

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

Вывод

Используйте массивы, когда нужен быстрый доступ по индексу, и избегайте частых вставок в начало. Для частых вставок в начало лучше подходят связанные списки или другие структуры данных, такие как deque.