Как устроен и работает динамический массив на примере Python list

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

Принцип работы:

Внутри list использует непрерывный блок памяти для хранения ссылок на объекты. Этот блок имеет зарезервированную емкость, которая часто превышает текущее количество элементов.

1. Добавление элемента (append):

   • Если в зарезервированном блоке есть свободное место, новый элемент добавляется в конец. Это быстрая операция со сложностью O(1).
   • Если места нет, Python выделяет новый блок памяти большего размера (стратегия роста зависит от версии, но он всегда больше текущего).
   • Все элементы из старого блока копируются в новый. Эта операция имеет сложность O(N), где N — текущий размер списка.
   • Старый блок памяти освобождается.

2. Амортизированная сложность: Хотя операция копирования сама по себе затратна, она происходит редко. Благодаря стратегии "роста с запасом", большинство операций append выполняются за O(1). При усреднении затрат на большое количество добавлений, средняя (амортизированная) сложность append составляет O(1).

Пример роста list в CPython:

Можно отследить изменение размера выделенной памяти с помощью sys.getsizeof.

import sys

my_list = []
current_size = sys.getsizeof(my_list)
print(f"Размер пустого списка: {current_size} байт")

for i in range(16):
    my_list.append(i)
    new_size = sys.getsizeof(my_list)
    if new_size > current_size:
        print(f"Размер изменился на {len(my_list)} элементе. Новый размер: {new_size} байт")
        current_size = new_size

# Примерный вывод (точные значения могут отличаться):
# Размер пустого списка: 56 байт
# Размер изменился на 1 элементе. Новый размер: 88 байт  (выделено место под 4 элемента)
# Размер изменился на 5 элементе. Новый размер: 120 байт (выделено место под 8 элементов)
# Размер изменился на 9 элементе. Новый размер: 184 байт (выделено место под 16 элементов)

Особенности производительности:

• append() и pop() (с конца): Очень быстрые, амортизированная сложность O(1).
• insert(i, ...) и pop(i) (из середины/начала): Медленные, так как требуют сдвига всех последующих элементов. Сложность O(N).