> Как устроены структуры данных list, dict и set в Python? (Python)

В Python list - это динамический массив (на уровне C - массив указателей на PyObject). Элементы хранятся последовательно, что даёт O(1) доступ по индексу. При добавлении элемента, если массив заполнен, выделяется новый блок памяти большего размера (обычно с коэффициентом роста ~1.125), и элементы копируются. Амортизированная сложность вставки в конец - O(1), вставка в начало - O(n).

dict реализован как хеш-таблица с открытой адресацией (в Python 3.6+ - компактная версия, где ключи и значения хранятся отдельно от хеш-таблицы). Хеш-функция вычисляется для ключа, затем по модулю размера таблицы определяется индекс. При коллизиях используется probing (линейное зондирование). Средняя сложность операций - O(1), в худшем случае - O(n). С Python 3.7 гарантирован порядок вставки элементов.

set - это фактически та же хеш-таблица, что и dict, но без значений (только ключи). Использует ту же логику хеширования и разрешения коллизий. Операции добавления, удаления и проверки вхождения - в среднем O(1). Важно: элементы должны быть хешируемыми (immutable-типы, например, числа, строки, кортежи).