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

Короткий ответ

Добавление в конец списка - амортизированная O(1), в начало - O(n), в середину - O(n). Это связано с тем, что список хранит элементы в непрерывном массиве: вставка в начало или середину требует сдвига всех последующих элементов. В конец добавление обычно O(1), но при переполнении массива происходит reallocation с копированием всех элементов, поэтому амортизированная сложность остаётся O(1).

Подробное объяснение

Список Python - это динамический массив указателей на объекты. Каждый элемент - это ссылка (8 байт на 64-битной системе), а сами объекты хранятся отдельно в куче.

Добавление в конец (append):

• Если в выделенном массиве есть свободное место - просто записываем указатель по индексу size и увеличиваем размер. Это O(1).
• Если массив заполнен - выделяется новый массив большего размера (обычно в 1.125 раза больше), все элементы копируются, затем добавляется новый. Это O(n), но происходит редко. Амортизированная сложность - O(1), потому что количество операций копирования при многократных append'ах в сумме даёт O(n) на n операций.

Добавление в начало (insert(0, x)):

• Все существующие элементы сдвигаются на одну позицию вправо. Это требует O(n) операций копирования указателей, даже если в массиве есть место. Плюс возможный reallocation, но доминирует именно сдвиг.

Добавление в середину (insert(i, x)):

• Сдвигаются элементы с индекса i до конца. В среднем это n/2 элементов, поэтому сложность - O(n). Константа меньше, чем для вставки в начало, но асимптотика та же.

Почему не O(1) для начала?
В отличие от связного списка, массив не позволяет вставить элемент без сдвига. Python не использует связный список для list - это осознанный trade-off: быстрый доступ по индексу O(1) ценой медленных вставок в середину.

На практике

• Для частых вставок в начало или середину используйте collections.deque (для начала/конца) или bisect.insort с последующей вставкой, если нужен порядок.
• Если нужна вставка в середину с сохранением порядка и частыми операциями - рассмотрите blist или sortedcontainers.SortedList.
• Для массовых вставок в начало эффективнее собрать новый список и развернуть его, чем вызывать insert(0, ...) в цикле.
• append - самый быстрый способ расширения списка; для конкатенации list1 + list2 создаётся новый список - это O(n+m).

Пример кода

PYTHON
import timeit

# append - O(1) амортизированно
lst = []
for i in range(100_000):
    lst.append(i)  # быстро

# insert в начало - O(n)
lst = list(range(100_000))
lst.insert(0, -1)  # сдвиг 100k элементов

# insert в середину - O(n)
lst = list(range(100_000))
lst.insert(50_000, -1)  # сдвиг ~50k элементов

# сравнение времени
setup = "lst = list(range(100_000))"
print(timeit.timeit("lst.append(1)", setup=setup, number=1000))
print(timeit.timeit("lst.insert(0, 1)", setup=setup, number=1000))
print(timeit.timeit("lst.insert(50_000, 1)", setup=setup, number=1000))

Как отвечать на собеседовании

Начните с чёткого ответа: O(1) для конца, O(n) для начала и середины. Затем объясните причину - массив указателей и сдвиг элементов. Упомяните амортизацию для append и почему reallocation не портит асимптотику. Если спросят про deque - скажите, что он реализован как doubly-linked list блоков, поэтому O(1) для обоих концов, но медленный доступ по индексу. Для senior-позиции добавьте про кэш-локальность и почему массив быстрее связного списка на практике.

Что проверяет интервьюер

• Понимание внутреннего устройства list как динамического массива.
• Знание разницы между амортизированной и худшей сложностью.
• Умение объяснить trade-off между list и deque.
• Понимание, что сложность вставки зависит от позиции, а не от размера данных (элементы - указатели, копирование ссылок - O(1) на элемент).
• Способность рассуждать о реальной производительности, а не только об асимптотике.

Типичные ошибки

• Утверждение, что append всегда O(1) - забывают про reallocation.
• Путаница между list и связным списком - говорят, что вставка в начало O(1).
• Не учитывают, что insert в середину тоже O(n), а не O(n/2) - константа не влияет на асимптотику.
• Предлагают deque для вставки в середину - это ошибка, deque оптимизирован только для концов.
• Забывают, что сложность относится к копированию указателей, а не самих объектов - объекты не перемещаются.