Динамический массив, например list в Python, представляет собой упорядоченную коллекцию элементов, размер которой может изменяться в процессе выполнения программы.
В основе работы динамического массива лежит статический массив фиксированного размера. Когда динамический массив создается, ему выделяется определенный объем памяти для хранения элементов (начальная емкость). При добавлении новых элементов:
Если в текущем статическом массиве есть свободное место, элемент просто добавляется в конец.
Если статический массив полностью заполнен, выполняется следующая процедура:
Удаление элементов также может приводить к изменению размера внутреннего статического массива. Если после удаления элементов занимаемое место становится значительно меньше общей емкости, может произойти "сжатие" — создание нового, меньшего статического массива и копирование в него оставшихся элементов для экономии памяти.
Основные операции:
| Операция | Средняя сложность | Описание |
|---|---|---|
| Добавление в конец | O(1) в среднем | Чаще всего происходит за константное время. |
| Вставка в начало | O(n) | Требует сдвига всех последующих элементов. |
| Вставка по индексу | O(n) | Требует сдвига части элементов. |
| Удаление с конца | O(1) | Быстрая операция. |
| Удаление с начала | O(n) | Требует сдвига всех последующих элементов. |
| Удаление по индексу | O(n) | Требует сдвига части элементов. |
| Доступ по индексу | O(1) | Быстрая операция благодаря непрерывности. |
| Поиск элемента | O(n) | Требует перебора элементов. |
Эта "амортизированная" сложность O(1) для добавления в конец означает, что хотя иногда (при перевыделении памяти) операция занимает O(n), в среднем за большое количество добавлений стоимость распределяется, делая среднее время константным.
Пример добавления с перевыделением памяти:
python