Какова алгоритмическая сложность добавления элемента в начало и конец списка в Python

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

Понимаете ли вы, что список это массив, и знаете ли, что такое амортизированная оценка.

Как отвечать

В конец: амортизированно O(1). В начало: O(n).

Причина в устройстве: list это динамический массив указателей, лежащих в памяти подряд.

Добавление в конец это запись в свободную ячейку и увеличение счётчика длины. Когда запас кончается, выделяется новый блок побольше и старые указатели копируются, что стоит линейно. Но происходит это редко, потому что запас берётся с избытком, и стоимость размазывается по многим дешёвым вставкам. Поэтому оценка амортизированная: отдельная операция иногда дорогая, а серия из n вставок стоит O(n).

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

Практическая разница огромна: наполнение списка на сто тысяч элементов через добавление в конец занимает миллисекунды, а через вставку в начало секунды, потому что суммарно получается порядка n² операций.

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

Второй способ обойти проблему: собирать список в конец и развернуть его в самом конце за один линейный проход. Часто это проще, чем менять структуру данных.

Полезно добавить оценки соседних операций: доступ по индексу постоянный, поиск по значению линейный, срез линеен по длине среза, сортировка это n log n.

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

Считают вставку в начало дешёвой.

Не могут объяснить, что значит амортизированная оценка.

Строят очередь на списке через извлечение из начала.

Не знают про двустороннюю очередь в стандартной библиотеке.