Какая скорость вставки в List?

Скорость вставки в List (временная сложность)

Время вставки в Python list зависит от позиции вставки. Это один из самых важных вопросов о структурах данных.

Операции вставки и их сложность

import time

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

# 1. append() — вставка в конец
# Временная сложность: O(1) amortized
my_list.append(6)  # [1, 2, 3, 4, 5, 6]

# 2. insert(index, value) — вставка в позицию
# Временная сложность: O(n) — нужно сдвинуть все элементы
my_list.insert(0, 0)     # [0, 1, 2, 3, 4, 5, 6]  O(n)
my_list.insert(3, 3.5)   # вставка в середину — O(n)
my_list.insert(len(my_list), 99)  # вставка в конец (через insert) — O(n)

# 3. extend() — добавить несколько элементов
# Временная сложность: O(k) где k — количество добавляемых элементов
my_list.extend([7, 8, 9])  # O(k)

Детальный анализ

append() — O(1) amortized

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

# Python выделяет память с запасом
print(len(my_list))       # 5 элементов
print(my_list.__sizeof__()) # реальный размер буфера больше

# append работает очень быстро, пока есть свободная память
for i in range(100):
    my_list.append(i)  # каждый append — O(1)

# Когда буфер заполнится, Python:
# 1. Выделяет новый буфер большего размера
# 2. Копирует все элементы туда (O(n))
# 3. Добавляет новый элемент
# Но это случается редко, поэтому amortized O(1)

insert(index, value) — O(n)

# insert() требует сдвинуть все элементы ПОСЛЕ позиции вставки
my_list = [1, 2, 3, 4, 5]  # 5 элементов

# insert в начало — сдвинуть все 5 элементов
my_list.insert(0, 0)       # O(n) где n=5

# insert в конец — никого не сдвигать
my_list.insert(len(my_list), 6)  # технически O(n) (встроенная функция),
                                  # но на практике как append

# insert в середину
my_list = [1, 2, 3, 4, 5]  # n=5
my_list.insert(3, 3.5)     # O(n) сдвинуть 2 элемента (3, 4, 5)

Сравнение скоростей на практике

import timeit

# Test 1: append — очень быстро
setup = "my_list = []"
stmt = "my_list.append(1)"
time_append = timeit.timeit(stmt, setup, number=1000000)
print(f"append: {time_append:.6f} сек")  # примерно 0.1 сек

# Test 2: insert(0, value) — медленнее
setup = "my_list = list(range(1000))"
stmt = "my_list.insert(0, -1)"
time_insert_start = timeit.timeit(stmt, setup, number=10000)
print(f"insert(0): {time_insert_start:.6f} сек")  # примерно 0.5 сек

# Test 3: insert в конец через insert
setup = "my_list = list(range(1000))"
stmt = "my_list.insert(len(my_list), 9999)"
time_insert_end = timeit.timeit(stmt, setup, number=10000)
print(f"insert(end): {time_insert_end:.6f} сек")  # примерно 0.5 сек

# Test 4: append (для сравнения)
setup = "my_list = list(range(1000))"
stmt = "my_list.append(9999)"
time_append_big = timeit.timeit(stmt, setup, number=10000)
print(f"append на список из 1000: {time_append_big:.6f} сек")  # примерно 0.01 сек

Выводы

Когда использовать List

# ✅ ХОРОШО
my_list = []
for i in range(1000):
    my_list.append(i)  # O(1) * 1000 = O(n)

# ✅ ХОРОШО — когда нужны вставки в конец
results = []
for item in data:
    results.append(process(item))

# ❌ ПЛОХО — если много вставок в начало
my_list = []
for i in range(1000):
    my_list.insert(0, i)  # O(n) * 1000 = O(n²) !!!

Альтернативы если нужны быстрые вставки

# collections.deque — O(1) для вставки в обе стороны
from collections import deque

my_deque = deque()
my_deque.appendleft(1)  # O(1) вставка в начало
my_deque.append(2)      # O(1) вставка в конец
my_deque.popleft()      # O(1) удаление с начала

# linked list — O(1) вставка если есть указатель на позицию
# но Python не имеет встроенного linked list

# heapq — для приоритетных очередей
import heapq
heap = []
heapq.heappush(heap, 5)   # O(log n)
heapq.heappop(heap)        # O(log n)

Практический совет

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