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

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

Динамический массив (Dynamic Array) — это структура данных, которая автоматически увеличивает размер при необходимости. В Python это реализовано встроенным типом list, который управляет памятью самостоятельно.

Механизм работы динамического массива

1. Выделение памяти

Когда создаём список, Python выделяет память для определённого количества элементов (не ровно столько, сколько нужно, а с запасом):

# Создание пустого списка
my_list = []
print(len(my_list))      # 0 элементов
print(my_list.__sizeof__())  # размер в байтах

# Python выделяет память заранее
my_list = [1, 2, 3]
print(len(my_list))       # 3 элемента (текущий размер)

2. Динамическое расширение

Когда попытаемся добавить элемент, а места нет, Python:

1. Выделяет новый, больший блок памяти
2. Копирует все элементы туда
3. Освобождает старый блок

my_list = [1, 2, 3]
# Внутренняя ёмкость (capacity) может быть, например, 4-5 элементов

my_list.append(4)  # элемент вписывается в существующую ёмкость
my_list.append(5)  # ёмкость может быть переполнена
my_list.append(6)  # Python резко увеличивает ёмкость

# После переполнения Python может выделить ёмкость на 9+ элементов

3. Стратегия увеличения ёмкости

Python использует стратегию амортизированного роста: увеличивает ёмкость примерно в 1.125 раза (12.5% каждый раз):

import sys

# Проверяем текущую ёмкость списка
my_list = []
for i in range(20):
    old_size = sys.getsizeof(my_list)
    my_list.append(i)
    new_size = sys.getsizeof(my_list)
    
    # Выводим когда размер в памяти изменился
    if old_size != new_size:
        print(f"Элемент {i}: переаллокация, новый размер = {new_size}")

Основные операции

Append (добавление в конец)

my_list = [1, 2, 3]
my_list.append(4)  # O(1) амортизированная сложность
# Внутри: если есть свободное место, просто добавляет
# Если нет — переаллоцирует и добавляет

Insert (вставка в середину)

my_list = [1, 2, 3]
my_list.insert(1, 99)  # O(n) — нужно сдвинуть все элементы после позиции
# Результат: [1, 99, 2, 3]

Delete и Pop

my_list = [1, 2, 3, 4, 5]
my_list.pop()      # O(1) — удаление с конца
my_list.pop(0)     # O(n) — удаление с начала, нужно сдвинуть
del my_list[2]     # O(n) — то же самое для удаления из середины

Доступ по индексу

my_list = [10, 20, 30, 40]
value = my_list[2]     # O(1) — прямой доступ, быстро
my_list[1] = 100       # O(1) — изменение элемента, быстро

Сложность операций

# O(1) — константная сложность
my_list.append(x)           # добавить в конец (амортизированная)
my_list[i]                  # доступ по индексу
my_list[i] = x              # изменение элемента
my_list.pop()               # удаление с конца

# O(n) — линейная сложность
my_list.insert(i, x)        # вставка в позицию i
my_list.pop(i)              # удаление из позиции i
my_list.remove(x)           # удаление по значению
x in my_list                # поиск элемента

# O(n log n) — при сортировке
my_list.sort()
sorted(my_list)

Слайсинг (Slicing)

my_list = [0, 1, 2, 3, 4, 5]

# Создаёт новый список (O(k), где k — размер слайса)
slice_1 = my_list[1:4]      # [1, 2, 3]
slice_2 = my_list[::2]      # [0, 2, 4]
slice_3 = my_list[::-1]     # [5, 4, 3, 2, 1, 0] — разворот

# Присваивание слайса
my_list[1:3] = [99, 100]    # [0, 99, 100, 3, 4, 5]

Сравнение с другими структурами

# Динамический массив (list) — быстро для append и доступа
my_list = [1, 2, 3]
my_list.append(4)           # O(1) ✓ быстро
value = my_list[2]          # O(1) ✓ быстро

# Связный список (deque) — быстро для обеих концов
from collections import deque
my_deque = deque([1, 2, 3])
my_deque.append(4)          # O(1) ✓ быстро
my_deque.appendleft(0)      # O(1) ✓ быстро (в list это O(n))
value = my_deque[1]         # O(n) ✗ медленнее

# Set — быстрый поиск
my_set = {1, 2, 3}
1 in my_set                 # O(1) ✓ быстро
my_set.add(4)               # O(1) в среднем
my_set.pop()                # O(1)

Оптимизация

# Плохо — множество append в цикле
result = []
for i in range(1000000):
    result.append(i)        # может быть много переаллокаций

# Хорошо — если знаешь размер заранее
result = [0] * 1000000     # выделяет сразу всю память
for i in range(1000000):
    result[i] = i

# Хорошо — list comprehension (одна аллокация)
result = [i for i in range(1000000)]

Внутренние детали в CPython

# В CPython список хранит указатели на объекты
# При расширении увеличивает размер внутреннего массива
# Текущая формула: new_size = (old_size >> 3) + (old_size < 9 ? 3 : 6)
# То есть примерно: new_size = old_size + old_size // 8 + 3/6

my_list = []
print(my_list.__sizeof__())  # начальный размер в байтах

for i in range(100):
    my_list.append(i)

print(my_list.__sizeof__())  # конечный размер

Итого

Динамический массив в Python (list):

• Автоматически увеличивает ёмкость по мере добавления элементов
• Использует стратегию амортизированного роста
• Append и доступ по индексу работают за O(1)
• Вставка в середину — O(n), требует сдвига элементов
• Идеален для последовательного доступа и добавления в конец
• Не идеален для удаления из начала (используй deque вместо этого)