Що означає "динамічний масив"?

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

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

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

Розгорнута відповідь

Ключова ідея

Динамічний масив поєднує властивості звичайного (статичного) масиву та гнучкість зміни розміру. Усередині в нього є:

буфер фіксованої довжини (capacity) у неперервній пам'яті;
лічильник фактичної кількості елементів (size), який може бути меншим за capacity.

Коли при додаванні елементів size досягає capacity, створюється новий буфер більшого розміру (зазвичай удвічі більший), усі елементи копіюються в нього, а старий звільняється. Така стратегія дає амортизовано O(1) на push у кінець: дорогі операції розширення трапляються рідко і «розподіляються» на безліч дешевих додавань.

Складність операцій

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

Як це працює всередині

Є поля size і capacity. Гарантується size ≤ capacity.
При нестачі місця буфер перевиділяється з ростом, наприклад, ×2 (іноді ×1.5). Що більший коефіцієнт росту, то рідше копіювання, але то вищий середній «порожній» запас пам'яті.
Іноді реалізують «усадку» (shrink) при сильному зменшенні розміру (наприклад, якщо size ≤ capacity/4, зменшити capacity вдвічі), щоб повернути пам'ять системі.
Елементи лежать послідовно в пам'яті, що покращує локальність посилань і кеш-влучання CPU під час лінійного обходу.

Плюси

Швидкий випадковий доступ O(1).
Амортизовано O(1) додавання в кінець.
Хороша кеш-локальність при ітерації.

Мінуси

Вставки/видалення в середині/на початку коштують O(n) через зсуви.
Іноді витрачає більше пам'яті, ніж потрібно (capacity > size).
Перевиділення можуть спричиняти рідкісні, але «дорогі» паузи (небажано в системах реального часу).

Порівняння з альтернативами

Статичний масив: фіксований розмір, немає перерозподілів; динамічний змінюється, зручніший при заздалегідь невідомій кількості елементів.
Зв'язний список: дешеві вставки/видалення в середині, але немає випадкового доступу (O(n)) і гірша кеш-локальність.
У мовах: C++ - std::vector, Java - ArrayList, C# - List, Python - list, JavaScript - Array (у JS масиви вже динамічні по суті).

Приклад реалізації (TypeScript)

class DynArray<T> {
  private buf: (T | undefined)[];
  private _size = 0;
  private _capacity: number;

  constructor(initialCapacity = 0) {
    this._capacity = initialCapacity;
    this.buf = new Array<T | undefined>(this._capacity);
  }

  size(): number { return this._size; }
  capacity(): number { return this._capacity; }
  isEmpty(): boolean { return this._size === 0; }

  get(i: number): T {
    if (i < 0 || i >= this._size) throw new RangeError("Index out of bounds");
    return this.buf[i] as T;
  }

  set(i: number, value: T): void {
    if (i < 0 || i >= this._size) throw new RangeError("Index out of bounds");
    this.buf[i] = value;
  }

  push(value: T): void {
    if (this._size === this._capacity) this.resizeUp();
    this.buf[this._size++] = value;
  }

  pop(): T | undefined {
    if (this._size === 0) return undefined;
    const v = this.buf[--this._size];
    this.buf[this._size] = undefined; // допомогти GC
    // Опційно: shrink, якщо стало занадто порожньо
    // if (this._size > 0 && this._size <= this._capacity / 4) this.resizeDown();
    return v as T;
  }

  insert(index: number, value: T): void {
    if (index < 0 || index > this._size) throw new RangeError("Index out of bounds");
    if (this._size === this._capacity) this.resizeUp();
    for (let i = this._size; i > index; i--) this.buf[i] = this.buf[i - 1];
    this.buf[index] = value;
    this._size++;
  }

  removeAt(index: number): T {
    if (index < 0 || index >= this._size) throw new RangeError("Index out of bounds");
    const v = this.buf[index] as T;
    for (let i = index; i < this._size - 1; i++) this.buf[i] = this.buf[i + 1];
    this.buf[--this._size] = undefined;
    return v;
  }

  private resizeUp(): void {
    const newCap = this._capacity === 0 ? 1 : this._capacity * 2;
    const newBuf = new Array<T | undefined>(newCap);
    for (let i = 0; i < this._size; i++) newBuf[i] = this.buf[i];
    this.buf = newBuf;
    this._capacity = newCap;
  }

  // private resizeDown(): void {
  //   const newCap = Math.max(1, Math.floor(this._capacity / 2));
  //   if (newCap < this._size) return; // безпека
  //   const newBuf = new Array<T | undefined>(newCap);
  //   for (let i = 0; i < this._size; i++) newBuf[i] = this.buf[i];
  //   this.buf = newBuf;
  //   this._capacity = newCap;
  // }
}

// Використання
const a = new DynArray<number>(2);
a.push(10);
a.push(20);
a.push(30); // тригерить розширення буфера
console.log(a.size(), a.capacity()); // 3, 4
console.log(a.get(1)); // 20
a.insert(1, 15); // [10, 15, 20, 30]
a.pop(); // видалить 30
a.removeAt(0); // видалить 10

Примітка: у JavaScript звичайні масиви вже динамічні, тому приклад вище демонструє концепцію стратегії росту і зсувів, а не низькорівневе керування пам'яттю.

Коли використовувати

Колекція з частими додаваннями в кінець і рідкісними вставками в середину.
Потрібен швидкий випадковий доступ за індексом.
Потрібна хороша продуктивність при ітерації (локальність даних).

Підводні камені та деталі

Перерозподіл іноді «дорогий»: копіює всі елементи; у критичних місцях можна заздалегідь зарезервувати capacity (наприклад, vector::reserve у C++).
Ріст на ×2 дає просте доведення амортизованого O(1): кожен елемент копіюється обмежену кількість разів (порядку log n), вартість копіювань розкладається на безліч дешевих push.
Занадто малий коефіцієнт росту (наприклад, +1) робить додавання O(n) в середньому; занадто великий збільшує пікове споживання пам'яті.
У деяких мовах при перерозподілі старі вказівники/ітератори на елементи стають недійсними (актуально для C++). У керованих середовищах посилання на самі елементи лишаються дійсними, але вказівник на внутрішній буфер може змінюватися.

Підсумок

Динамічний масив - базова й ефективна структура даних для послідовностей зі швидким доступом за індексом і частими додаваннями в кінець. Його ключ до продуктивності - стратегічне керування capacity (зазвичай подвоєння) і неперервне розміщення елементів у пам'яті.

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

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

Premium

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