Как Python list устроен под капотом и какова асимптотика добавления элемента в конец?

В CPython list — динамический массив ссылок на объекты. Добавление в конец имеет амортизированную сложность O(1), но отдельное расширение массива может потребовать O(n).

Список резервирует дополнительную ёмкость, поэтому большинство append не перераспределяет весь буфер. Индексный доступ — O(1), вставка в начало обычно O(n) из-за сдвига ссылок. Сами объекты не обязаны лежать рядом: непрерывно размещён массив указателей. Это описание реализации CPython, а не обязательная внутренняя структура для любой реализации Python.

Источник: github.com.