Что происходит при добавлении элемента в заполненный массив списка в Python?

Добавление элемента в заполненный список Python

Простой ответ

Python списки динамические — они автоматически растут. Когда добавляешь элемент в заполненный список, он выделяет больше памяти и добавляет элемент.

Как работает список в памяти

# Список в Python имеет две характеристики:
# - length (размер — сколько элементов сейчас)
# - capacity (вместимость — сколько может вместить до переаллокации)

my_list = [1, 2, 3]

# Внутри (CPython):
struct PyListObject {
    Py_ssize_t ob_size;      // length = 3
    PyObject **ob_item;       // указатель на массив
    Py_ssize_t allocated;     // capacity > length
}

# Память (схематично):
# [1] [2] [3] [?] [?] [?]  ← есть место для ещё 3 элементов
#  ↑   ↑   ↑
#  Используется (3 элемента)
#                       ↑
#                       Выделено (6 мест)

Пошаговый процесс: my_list.append(4)

Сценарий 1: Есть место в памяти

my_list = [1, 2, 3]
# Состояние памяти:
# Выделено: 6 мест
# Используется: 3

my_list.append(4)

# 1. Проверяет: есть ли место?
#    allocated (6) > ob_size (3)? ДА

# 2. Простое добавление элемента
#    ob_item[3] = 4
#    ob_size += 1  → 4

# 3. Результат
# [1] [2] [3] [4] [?] [?]
#  Используется: 4, Выделено: 6

# Сложность: O(1) — константное время!

Сценарий 2: Памяти не хватает

my_list = [1, 2, 3, 4, 5, 6]
# Состояние:
# Используется: 6, Выделено: 6 (ПОЛНО!)

my_list.append(7)

# 1. Проверяет: есть ли место?
#    allocated (6) > ob_size (6)? НЕТ

# 2. Нужна переаллокация
#    Выделяет новую память большего размера
#    new_capacity = old_capacity + (old_capacity >> 3)
#    new_capacity = 6 + 6//8 = 6 + 0 = 6... (минимум +1)
#    Но в CPython это примерно:
#    new_capacity = 9  (в CPython используется формула: n + n//8 + 6)

# 3. Копирует старые данные
#    new_memory = [1] [2] [3] [4] [5] [6] [?] [?] [?]

# 4. Освобождает старую память
#    free(old_memory)

# 5. Добавляет новый элемент
#    new_memory[6] = 7
#    ob_size = 7

# Результат:
# [1] [2] [3] [4] [5] [6] [7] [?] [?]
#  Используется: 7, Выделено: 9

# Сложность: O(n) — приходится копировать всё!

Стратегия роста списка

# CPython использует амортизированный рост:
# При нехватке памяти увеличивает на ~12.5%

import sys

my_list = []
for i in range(100):
    # Смотрим, как растёт capacity
    if i == 0 or (i-1 != len(my_list) - 1):
        prev_size = len(my_list)
    
    my_list.append(i)
    
    # Capacity растёт в определённых точках:
    # 0 → 1 → 5 → 9 → 13 → 17 → ...

Реальный пример: измерение времени

import time

# Append в конец (БЫСТРО)
start = time.time()
my_list = []
for i in range(1_000_000):
    my_list.append(i)
print(f"Append 1M: {time.time() - start:.3f}s")
# Output: ~0.05s (очень быстро!)

# Insert в начало (МЕДЛЕННО)
start = time.time()
my_list = []
for i in range(10_000):  # Только 10K для примера
    my_list.insert(0, i)  # Вставляет в начало
print(f"Insert 10K: {time.time() - start:.3f}s")
# Output: ~0.3-0.5s (медленнее!)

# Почему insert медленнее?
# insert(0, x) должен:
# 1. Сдвинуть ВСЕ элементы на 1 позицию вправо → O(n)
# 2. Поставить новый элемент на позицию 0
# Повторяя это 10k раз → O(n²)

Визуализация переаллокации

Шаг 1: Создаём список
my_list = []
┌─────────────┐
│             │ capacity=0, length=0
└─────────────┘

Шаг 2: Добавляем первый элемент
my_list.append(1)
┌─────┐
│  1  │ capacity=1, length=1
└─────┘

Шаг 3: Добавляем второй (нужна переаллокация)
my_list.append(2)
┌─────────────┐
│  1  │  2  │ │ capacity=5, length=2
└─────────────┘

Шаг 4-5: Добавляем 3-5 (есть место)
my_list.extend([3, 4, 5])
┌─────────────┐
│  1  │  2  │  3  │  4  │  5  │ capacity=5, length=5
└─────────────┘

Шаг 6: Добавляем 6-й элемент (нужна переаллокация!)
my_list.append(6)
┌───────────────────────────┐
│  1  │  2  │  3  │  4  │  5  │  6  │  ?  │  ?  │ capacity=10, length=6
└───────────────────────────┘

Формула роста в CPython

# CPython использует эту формулу при переаллокации:
def new_capacity(old_capacity):
    if old_capacity == 0:
        return 1
    return old_capacity + (old_capacity >> 3) + 6
    # (old_capacity >> 3) это old_capacity // 8

# Примеры:
print(new_capacity(0))   # 1
print(new_capacity(1))   # 1 + 0 + 6 = 7
print(new_capacity(5))   # 5 + 0 + 6 = 11
print(new_capacity(10))  # 10 + 1 + 6 = 17
print(new_capacity(100)) # 100 + 12 + 6 = 118

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

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

# O(1) — константное время
my_list.append(6)           # Добавляет в конец
my_list[-1]                 # Доступ по индексу
my_list[2]                  # Доступ по индексу

# O(n) — линейное время
my_list.insert(0, 99)       # Вставляет в начало (сдвигает всё)
my_list.pop(0)              # Удаляет из начала (сдвигает всё)
my_list.remove(3)           # Удаляет элемент (может требовать сдвига)
my_list.clear()             # Очищает (но не освобождает память)

# O(n) для расширения
my_list.extend([10, 11, 12])  # Добавляет много элементов

# O(n log n) для сортировки
my_list.sort()              # Timsort алгоритм

Оптимизация: pre-allocate память

# ❌ Медленно — много переаллокаций
my_list = []
for i in range(1_000_000):
    my_list.append(i)

# ✅ Быстрее — выделить место заранее
my_list = [0] * 1_000_000  # Выделяем место
for i in range(1_000_000):
    my_list[i] = i  # Просто присваиваем

# ✅ Альтернатива
my_list = list(range(1_000_000))  # Создаём сразу

Другие типы данных

# List — динамический массив (как описано выше)
my_list = [1, 2, 3]
my_list.append(4)  # Переаллокация при необходимости

# Tuple — фиксированный размер
my_tuple = (1, 2, 3)  # Размер фиксирован
# my_tuple.append(4)  # AttributeError — нельзя!!

# Deque — двусторонняя очередь (быстро append и appendleft)
from collections import deque
my_deque = deque([1, 2, 3])
my_deque.append(4)       # O(1)
my_deque.appendleft(0)   # O(1) — также быстро!

# Array — типизированный массив (для чисел)
import array
my_array = array.array('i', [1, 2, 3])  # 'i' = int
my_array.append(4)  # Переаллокация

Заключение

При добавлении элемента в список:

1. Если есть место — O(1), элемент добавляется мгновенно
2. Если нет места — O(n), требуется переаллокация и копирование
3. Амортизированная сложность — O(1) в среднем благодаря стратегии роста
4. Память растёт на ~12.5% при переаллокации (в CPython)
5. Append в конец быстро, но insert в начало медленно

Правило: Используй append() в конец, а не insert() в начало. Если нужны операции в обе стороны — используй deque из collections.