Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що означає "динамічний масив"?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Динамічний масив** - це масив змінного розміру, який зберігається в неперервній області пам'яті й автоматично збільшує (а іноді й зменшує) свою місткість при додаваннях/видаленнях, забезпечуючи швидкий доступ за індексом і амортизовано O(1) час для додавання в кінець. **Ключове:** коли при додаванні елементів size досягає capacity, створюється новий буфер більшого розміру (зазвичай удвічі більший), усі елементи копіюються в нього, а старий звільняється, що й дає амортизовано O(1) на push у кінець.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Динамічний масив - це масив змінного розміру, який зберігається в неперервній області пам'яті й автоматично збільшує (а іноді й зменшує) свою місткість при додаваннях/видаленнях, забезпечуючи швидкий доступ за індексом і амортизовано 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<T>, 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 (зазвичай подвоєння) і неперервне розміщення елементів у пам'яті.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.