Как работает динамический массив

В Python динамический массив реализован через тип list. Он автоматически управляет памятью, увеличивая или уменьшая размер при необходимости.

Основные принципы:

• При создании списка выделяется начальный буфер (например, на 4 элемента).
• При добавлении элементов (.append()) проверяется заполненность буфера. Если места нет, выделяется новый буфер большего размера (обычно в ~1.5–2 раза).
• Копирование элементов в новый буфер происходит за O(n), но амортизированная сложность добавления — O(1).

Пример:

lst = []  # Буфер, например, на 0 элементов
lst.append(1)  # Выделяется буфер (например, на 4 элемента)
for i in range(10):
    lst.append(i)  # При переполнении буфер расширяется

Нюансы:

• Уменьшение размера (например, при .pop()) не всегда сразу освобождает память.
• Изменение размера затратно, поэтому для больших списков лучше использовать .extend() или заранее задать размер (если возможно).