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

В Python динамический массив (список, list) реализован как массив указателей на объекты.

Когда список создается или увеличивается:

1. Выделяется блок памяти для хранения указателей. Размер этого блока больше текущего количества элементов.
2. Существующие указатели копируются в новый блок.
3. В случае добавления элемента, указатель на него помещается в следующий свободный слот.

Особенности:

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

Таблица операций и их сложности:

# Пример работы динамического массива (списка) в Python
my_list = []  # Создание пустого списка (динамического массива)

# Добавление элементов в конец - чаще всего O(1)
my_list.append(1)
my_list.append(2)
my_list.append(3)

# my_list сейчас [1, 2, 3]. Если нужно перевыделить память, это O(н).

# Вставка в начало - O(н)
my_list.insert(0, 0) # [0, 1, 2, 3]

# Доступ по индексу - O(1)
print(my_list[2]) # Выведет 2

# Удаление с конца - O(1)
my_list.pop() # Удаляет 3. my_list сейчас [0, 1, 2]

# Удаление из середины - O(н)
del my_list[1] # Удаляет 1. my_list сейчас [0, 2]