Чому вставка в кінець масиву ефективніша?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Вставка в кінець динамічного масиву зазвичай амортизовано займає O(1), бо не потребує зсуву вже наявних елементів: достатньо записати значення за індексом size і збільшити size. Вставки на початок або в середину вимагають зсуву великої кількості елементів, що дає O(n) і гіршу кеш-локальність. Рідкісні перерозподіли пам'яті при рості ємності роблять додавання в кінець «майже завжди» O(1).

Детальний розбір

Як влаштований динамічний масив

Масив зберігає елементи в неперервній ділянці пам'яті (contiguous memory).
Є два числа: size (скільки елементів фактично) і capacity/ємність (скільки елементів можна зберігати без перевиділення пам'яті).
При заповненні capacity масив зазвичай «росте» кратно (наприклад, у 1.5-2 рази): виділяється новий блок пам'яті, і всі елементи копіюються в нього.

Що відбувається при вставці в кінець

Якщо є вільна ємність: записується елемент за індексом size, size збільшується на 1.
Якщо ємність вичерпана: один рідкісний «дорогий» крок перерозподілу (realloc + копіювання всіх елементів), після чого знову багато дешевих вставок.
Підсумок: амортизована складність O(1), чудовий кеш-профіль (послідовний запис), мінімум переміщень даних.

Що відбувається при вставці на початок/у середину

Потрібно звільнити місце під новий елемент, для цього зсуваються всі елементи правіше позиції вставки.
Зсув - це O(n) операцій копіювання/перенесення посилань, що гірше використовує кеш і може зробити недійсними посилання/ітератори.
Підсумок: вставка на початок/у середину - O(n) навіть за достатньої ємності.

Амортизована складність

Стратегія росту ємності (зазвичай геометрична: ×1.5-2) гарантує, що «дорогі» перерозподіли трапляються рідко. У перерахунку на послідовність з m додавань середня вартість однієї операції append стає константною: O(1) амортизовано.

Приклад на JavaScript

Проста ілюстрація часу виконання різних видів вставок (значення N підберіть під своє середовище, щоб не «заморозити» вкладку):

const N = 100_000; // зменшіть за потреби

console.time('push end');
let a = [];
for (let i = 0; i < N; i++) a.push(i);
console.timeEnd('push end');

console.time('unshift begin');
let b = [];
for (let i = 0; i < N; i++) b.unshift(i);
console.timeEnd('unshift begin');

console.time('splice middle');
let c = [];
for (let i = 0; i < N; i++) c.push(i);
// Вставимо в середину N/10 разів, щоб не було занадто довго
for (let i = 0; i < N / 10; i++) c.splice(Math.floor(c.length / 2), 0, i);
console.timeEnd('splice middle');

Очікувано: push працює помітно швидше, ніж unshift/splice, тому що не потребує масових зсувів.

Практичні висновки для web-розробника

Для черг і стеків використовуйте операції, що працюють з кінцем масиву: push/pop, найдешевші.
Якщо часто потрібен «перший елемент», уникайте частих unshift/shift. Краще використовуйте двосторонню чергу (deque) на двох стеках:

class Deque {
  constructor() { this.left = []; this.right = []; }
  pushBack(x) { this.right.push(x); }
  pushFront(x) { this.left.push(x); }
  popFront() {
    if (!this.left.length) while (this.right.length) this.left.push(this.right.pop());
    return this.left.pop();
  }
  popBack() {
    if (!this.right.length) while (this.left.length) this.right.push(this.left.pop());
    return this.right.pop();
  }
}

// Амортизовано O(1) без масових зсувів масиву

Винятки й нюанси

TypedArray у JS має фіксований розмір: «вставка в кінець» неможлива без створення нового буфера й копіювання (O(n)).
Незмінні оновлення (наприклад, [...arr, x] або arr.concat(x)) завжди створюють новий масив і копіюють елементи, це O(n). Тут «ефективність вставки в кінець» стосується змінюваних масивів.
JS-рушії оптимізують push/pop (fast path). Операції unshift/shift часто вимагають переміщення елементів і можуть призводити до деградації внутрішнього формату масиву.
Для дуже маленьких масивів різниця може бути непомітною, але при рості N ефект стає суттєвим.

Висновок

Вставка в кінець динамічного масиву ефективніша, бо не потребує зсуву наявних елементів і використовує неперервну пам'ять, що дає амортизовану складність O(1) і кращу кеш-локальність. Вставка на початок або в середину вимагає переміщення O(n) елементів і тому значно повільніша.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.