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

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

Добавление в конец списка (append) - амортизированная O(1), в худшем случае O(n) из-за переаллокации. Добавление в начало (insert(0, ...)) - O(n), так как требует сдвига всех элементов. В CPython список - это динамический массив указателей, а не связный список, поэтому операции вставки в начало линейны по длине списка.

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

Список в Python реализован как динамический массив указателей на объекты. Это означает:

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

• insert(0, item) требует сдвига всех существующих элементов на одну позицию вправо. Это O(n) в худшем и среднем случае. Для больших списков операция становится дорогой.

• pop() с конца - O(1), pop(0) - O(n) по той же причине.

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

На практике

Для частых вставок в начало используйте collections.deque - она реализована как двусвязный список блоков и даёт O(1) для appendleft и popleft. Однако deque медленнее для произвольного доступа по индексу (O(n) против O(1) у списка).

Если нужна вставка в середину - списки тоже O(n), но для этого лучше подойдёт bisect.insort с O(log n) на поиск позиции + O(n) на вставку.

Для больших объёмов данных, где важна производительность вставок, рассмотрите blist или array.array (если тип данных однородный).

Пример кода

PYTHON
import time
from collections import deque

n = 100_000

# Список: вставка в начало - O(n)
lst = []
start = time.perf_counter()
for i in range(n):
    lst.insert(0, i)
print(f"list.insert(0): {time.perf_counter() - start:.3f}s")

# Deque: вставка в начало - O(1)
dq = deque()
start = time.perf_counter()
for i in range(n):
    dq.appendleft(i)
print(f"deque.appendleft: {time.perf_counter() - start:.3f}s")

# Список: append - амортизированно O(1)
lst2 = []
start = time.perf_counter()
for i in range(n):
    lst2.append(i)
print(f"list.append: {time.perf_counter() - start:.3f}s")

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

Начните с чёткого ответа: append - амортизированно O(1), insert(0) - O(n). Затем объясните причину: динамический массив, переаллокация, сдвиг элементов. Упомяните, что амортизированная оценка важна для append - в худшем случае одна операция может быть O(n), но в среднем по последовательности - O(1). Если спросят про альтернативы - расскажите про deque и trade-off между скоростью вставки и произвольным доступом. Покажите понимание внутреннего устройства CPython: массив указателей, фактор роста.

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

• Понимание разницы между амортизированной и худшей сложностью.
• Знание внутренней реализации списков в CPython.
• Умение обосновать выбор структуры данных под задачу.
• Понимание trade-off между списком и deque.
• Способность оценить реальную производительность, а не только теоретическую сложность.

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

• Утверждение, что append всегда O(1) - забывают про переаллокацию.
• Путаница между списком и связным списком - список не имеет O(1) вставки в начало.
• Игнорирование амортизированной оценки - говорят только про худший случай.
• Рекомендация deque для всех случаев, не упоминая медленный доступ по индексу.
• Непонимание, что insert в середину тоже O(n), а не O(log n).