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

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

Знаете ли вы, что list в CPython это динамический массив указателей, а не связный список, и можете ли объяснить слово «амортизированная». В data-ml следом почти всегда спрашивают, как правильно собирать массив numpy или датафрейм в цикле.

Как отвечать

• в конец, append: амортизированное O(1). Список держит запас ёмкости; когда он кончается, CPython выделяет новый буфер примерно на восьмую часть больше и копирует указатели. Отдельная операция может стоить O(n), но в среднем по длинной серии вставок выходит константа;
• в начало, insert(0, x): O(n), все указатели сдвигаются на одну позицию. Сдвиг идёт через memmove и быстр на практике, но сотни тысяч таких вставок в цикле дают квадрат;
• в середину, insert(i, x): стоимость пропорциональна числу элементов после позиции i, то есть O(n) в общем случае. Сюда же pop(0) и remove(x);
• поиск места и вставка: bisect.insort находит позицию за O(log n), но сама вставка остаётся линейной.

Если нужно часто добавлять с обоих концов, берите collections.deque: append и appendleft за O(1), но доступ по индексу в середину у неё линейный.

Для data-ml главное следствие: np.append каждый раз создаёт новый массив и копирует всё содержимое, поэтому цикл из n таких вызовов стоит O(n²). То же с pd.concat на каждой итерации. Правильно накопить строки в обычном списке и один раз вызвать np.array(...) или pd.DataFrame(...), либо сразу выделить массив нужного размера через np.empty и заполнять по индексу. Метод DataFrame.append удалён в pandas 2.0, но в старом коде он встречается и страдал той же проблемой.

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

Называют список связным и говорят, что вставка в начало стоит O(1). В Python это верно для deque, но не для list.

Говорят «append всегда O(1)», не упоминая редкие дорогие расширения. На вопрос «а в худшем случае?» нужно ответить O(n) и объяснить амортизацию.

Собирают numpy-массив через np.append в цикле и удивляются, почему препроцессинг на миллионе строк идёт минутами.