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

Динамический массив, например list в Python, представляет собой упорядоченную коллекцию элементов, размер которой может изменяться в процессе выполнения программы.

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

1. Если в текущем статическом массиве есть свободное место, элемент просто добавляется в конец.

2. Если статический массив полностью заполнен, выполняется следующая процедура:

   • Выделяется новый, более крупный статический массив (обычно в два или полтора раза больше по размеру, чем текущий).
   • Все элементы из старого массива копируются в новый.
   • Новый элемент добавляется в конец нового массива.
   • Старый статический массив освобождается.

Удаление элементов также может приводить к изменению размера внутреннего статического массива. Если после удаления элементов занимаемое место становится значительно меньше общей емкости, может произойти "сжатие" — создание нового, меньшего статического массива и копирование в него оставшихся элементов для экономии памяти.

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