За сколько работает добавление в начало и конец списка в Python?

В Python сложность операций добавления в список зависит от позиции:

• Добавление в конец списка (list.append()) работает за амортизированное время O(1), так как списки реализованы как динамические массивы.
• Добавление в начало списка (list.insert(0, value)) работает за O(n), потому что все элементы сдвигаются вправо для освобождения места.

Если нужно эффективно добавлять элементы в начало и конец, лучше использовать collections.deque, где обе операции выполняются за O(1):

from collections import deque

d = deque()
d.append(1)       # добавление в конец — O(1)
d.appendleft(0)   # добавление в начало — O(1)