Как устроен список в Python и какова временная сложность основных операций

Что проверяют

Знаете ли вы, что это динамический массив указателей, и понимаете ли, откуда берётся стоимость каждой операции.

Как отвечать

list в CPython это динамический массив указателей на объекты, а не связный список. Структура хранит указатель на непрерывный блок памяти, текущую длину и выделенную ёмкость.

Отсюда сложности:

• доступ и присваивание по индексу: O(1), потому что адрес вычисляется арифметикой. Отрицательные индексы тоже O(1);
• append: амортизированно O(1). При нехватке места блок перевыделяется с запасом, и редкое копирование размазывается по многим дешёвым вставкам;
• pop() с конца: O(1);
• insert(0, x) и pop(0): O(n), сдвигается весь хвост. Для очереди берут collections.deque с постоянным временем с обоих концов;
• remove(x): O(n), сначала поиск, потом сдвиг;
• x in list: O(n). Для частых проверок нужен set или dict;
• len: O(1), длина хранится в структуре;
• срез: O(k) по длине среза, создаётся новый список;
• sort: O(n log n), алгоритм timsort, устойчивый и очень быстрый на частично упорядоченных данных;
• extend и copy: линейно по числу добавляемых или копируемых элементов.

Про рост: перевыделение идёт не удвоением, а с умеренным запасом, поэтому память расходуется экономнее, а амортизированная оценка сохраняется.

Про память стоит сказать отдельно: элементы это указатели, сами объекты разбросаны по куче. Поэтому список чисел заметно тяжелее массива в языке со значениями и хуже ложится на кэш процессора. Для численных задач берут array или numpy.

Где спотыкаются

Называют list связным списком и говорят про O(n) доступ.

Считают insert(0, x) дешёвой операцией.

Проверяют вхождение в списке внутри цикла и получают квадрат.

Не знают про амортизацию и называют append линейной операцией.