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