Как происходит расширение динамического массива?

Динамический массив — это структура данных, которая предоставляет интерфейс списка (добавление, удаление, доступ по индексу), но внутри использует обычный массив фиксированного размера. Ключевая идея в том, чтобы скрыть от пользователя ручное управление памятью, автоматически увеличивая внутренний буфер при необходимости.

Как работает расширение

При создании динамического массива выделяется начальный буфер (например, на 10 элементов). Пока есть свободное место, новые элементы добавляются в конец за O(1). Когда массив заполняется, происходит следующее:

• Выделяется новый массив большего размера. Коэффициент роста (growth factor) часто равен 2 (удвоение) или 1.5 (как в Java ArrayList).
• Все элементы из старого массива копируются в новый.
• Старый массив освобождается (сборка мусора или ручное освобождение).
• Добавляемый элемент помещается в новый массив, а указатель на внутренний буфер начинает ссылаться на новый массив.

Амортизированная сложность

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

Пример на Python (упрощённая реализация)

class DynamicArray:
    def __init__(self, initial_capacity=4):
        self.capacity = initial_capacity
        self.size = 0
        self.data = [None] * self.capacity

    def append(self, value):
        # Если места нет — расширяем
        if self.size == self.capacity:
            self._resize()
        self.data[self.size] = value
        self.size += 1

    def _resize(self):
        # Увеличиваем capacity в 2 раза
        self.capacity *= 2
        new_data = [None] * self.capacity
        # Копируем старые элементы
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        print(f"Массив расширен до {self.capacity} элементов")

Где применяется

Динамические массивы — основа многих стандартных коллекций: ArrayList в Java, vector в C++, list в Python (хотя там реализация немного иная), List<T> в .NET. Они идеальны, когда нужен частый доступ по индексу и последовательное добавление в конец, но количество элементов заранее неизвестно.

Вывод: Понимание механизма расширения помогает писать эффективный код, избегая частых ресайзов (например, задавая начальную capacity, если известно примерное количество элементов) и правильно оценивая амортизированную сложность операций.