Как устроены list, dict и set: сложность операций

Вопрос про «капот»: на чём построены основные коллекции и какая у операций сложность.

Сложность (Big-O) описывает, как растёт время операции при росте размера данных. O(1) — постоянное, O(n) — линейное.

Список (list) — динамический массив

Чёткий ответ. list — это массив указателей. Доступ по индексу и append в конец — O(1). А вот вставка/удаление в начало или поиск элемента по значению — O(n), потому что приходится двигать элементы или перебирать их.

Операция	Сложность
`lst[i]`, `lst[i] = x`	O(1)
`lst.append(x)`, `lst.pop()`	O(1)
`x in lst`, `lst.index(x)`	O(n)
`lst.insert(0, x)`, `lst.pop(0)`	O(n)

Словарь и множество — хеш-таблицы

dict и set построены на хеш-таблицах. Поэтому проверка x in s, вставка и удаление в среднем O(1) — не зависят от размера. Это главная причина выбирать множество вместо списка для проверок принадлежности.

big_list = list(range(100000))
big_set = set(big_list)

target = 99999
print("в множестве:", target in big_set)   # O(1)
print("в списке:   ", target in big_list)   # O(n), но результат тот же

Вывод:

в множестве: True
в списке:    True

Результат одинаков, но множество находит элемент за один шаг, а список в худшем случае перебирает все 100000 элементов. На больших данных разница огромна.

Когда что выбирать

Нужен порядок и доступ по индексу → list.
Нужны быстрые проверки «есть ли элемент» и уникальность → set.
Нужно сопоставление ключ → значение с быстрым доступом → dict.

# Подсчёт уникальных слов — set вместо ручной проверки in для списка
words = ["a", "b", "a", "c", "b", "a"]
unique = set(words)
print("уникальных:", len(unique))
print(sorted(unique))

Вывод:

уникальных: 3
['a', 'b', 'c']

Итог

list — массив: индекс и append за O(1), поиск и вставка в начало за O(n).
dict и set — хеш-таблицы: членство, вставка, удаление в среднем O(1).
Для частых проверок «есть ли элемент» используйте set, а не list.