Сложность добавления в начало и конец Python list
За сколько работает добавление элемента в начало и в конец Python list? Почему append в конец обычно O(1), но не всегда строго O(1)?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
Вставка в начало list стоит O(n), потому что элементы нужно сдвинуть. append в конец - амортизированно O(1), но расширение внутреннего буфера иногда стоит O(n).
Полный разбор
Python list в CPython реализован как динамический массив ссылок. Добавление в начало требует освободить позицию 0 и сдвинуть все существующие элементы, поэтому это O(n).
Добавление в конец обычно кладет ссылку в уже выделенную свободную ячейку, поэтому стоит O(1). Когда capacity заканчивается, list выделяет новый больший буфер и копирует туда старые ссылки. Такой отдельный append стоит O(n), но средняя стоимость по длинной серии append остается амортизированно O(1).