Как работает динамический массив?
Sobes Copilot
Получайте ответы в реальном времени
Ответ от нейросети
sobes.tech AI
Динамический массив, например list в Python, представляет собой упорядоченную коллекцию элементов, размер которой может изменяться в процессе выполнения программы.
В основе работы динамического массива лежит статический массив фиксированного размера. Когда динамический массив создается, ему выделяется определенный объем памяти для хранения элементов (начальная емкость). При добавлении новых элементов:
-
Если в текущем статическом массиве есть свободное место, элемент просто добавляется в конец.
-
Если статический массив полностью заполнен, выполняется следующая процедура:
- Выделяется новый, более крупный статический массив (обычно в два или полтора раза больше по размеру, чем текущий).
- Все элементы из старого массива копируются в новый.
- Новый элемент добавляется в конец нового массива.
- Старый статический массив освобождается.
Удаление элементов также может приводить к изменению размера внутреннего статического массива. Если после удаления элементов занимаемое место становится значительно меньше общей емкости, может произойти "сжатие" — создание нового, меньшего статического массива и копирование в него оставшихся элементов для экономии памяти.
Основные операции:
| Операция | Средняя сложность | Описание |
|---|---|---|
| Добавление в конец | O(1) в среднем | Чаще всего происходит за константное время. |
| Вставка в начало | O(n) | Требует сдвига всех последующих элементов. |
| Вставка по индексу | O(n) | Требует сдвига части элементов. |
| Удаление с конца | O(1) | Быстрая операция. |
| Удаление с начала | O(n) | Требует сдвига всех последующих элементов. |
| Удаление по индексу | O(n) | Требует сдвига части элементов. |
| Доступ по индексу | O(1) | Быстрая операция благодаря непрерывности. |
| Поиск элемента | O(n) | Требует перебора элементов. |
Эта "амортизированная" сложность O(1) для добавления в конец означает, что хотя иногда (при перевыделении памяти) операция занимает O(n), в среднем за большое количество добавлений стоимость распределяется, делая среднее время константным.
Пример добавления с перевыделением памяти:
# Изначально list может выделить место для 0 или небольшого числа элементов.
# Допустим, внутренний массив имеет емкость 4.
my_list = [1, 2, 3, 4] # Емкость заполнена
# Добавление элемента 5
# Текущий массив заполнен.
# Создается новый массив (например, емкостью 8).
# Элементы 1, 2, 3, 4 копируются в новый массив.
# Элемент 5 добавляется в новый массив.
# Старый массив освобождается.
my_list.append(5) # my_list теперь [1, 2, 3, 4, 5]