Какая алгоритмическая сложность вставки в нулевую позицию списка Python?

Сложность вставки в нулевую позицию: O(n)

Ответ простой: вставка элемента в начало списка Python имеет сложность O(n), где n — количество элементов в списке.

Почему O(n)?

Python списки используют динамический массив (как ArrayList в Java). Элементы хранятся в памяти подряд:

До вставки:
Мемория: [10] [20] [30] [40] [50] [   ] [   ]
 Индекс:   0    1    2    3    4

Вставляем значение 5 в позицию 0:

После вставки:
Мемория: [5] [10] [20] [30] [40] [50] [   ]
 Индекс:  0   1    2    3    4    5

Что происходит внутри list.insert(0, element):

1. Сдвиг всех элементов на одну позицию вправо: 10 к 1, 20 к 2, 30 к 3 и т.д. Это n операций!
2. Вставка нового элемента в позицию 0: 1 операция
3. Возможное переразмещение в памяти если массив переполнен: O(n) дополнительно

Итого: n операций сдвига + возможное переразмещение = O(n).

Сравнение со вставкой в конец

Вставка в конец (list.append()) имеет O(1) амортизированную сложность:

ls = [1, 2, 3, 4, 5]

# O(n) — медленно, нужно сдвинуть все
ls.insert(0, 999)  # [999, 1, 2, 3, 4, 5]

# O(1) — быстро, просто добавляем в конец
ls.append(999)     # [1, 2, 3, 4, 5, 999]

Практический пример

import time

# Тестируем вставку в начало
ls = list(range(100000))
start = time.time()
ls.insert(0, -1)
print(f"Вставка в начало 100k элементов: {time.time() - start:.4f} сек")

# Тестируем вставку в конец
ls = list(range(100000))
start = time.time()
ls.append(-1)
print(f"Вставка в конец 100k элементов: {time.time() - start:.6f} сек")

Как не попасть в ловушку

Плохо — O(n²) сложность

result = []
for item in items:
    result.insert(0, item)  # Вставляем в начало КАЖДЫЙ раз

Хорошо — O(n) сложность

# Вариант 1: добавляй в конец, потом разворачивай
result = []
for item in items:
    result.append(item)
result.reverse()

# Вариант 2: используй collections.deque
from collections import deque
result = deque()
for item in items:
    result.appendleft(item)  # O(1) в deque!

deque vs list для вставки в начало

from collections import deque
import time

# Вставка в начало со списком — O(n²) в цикле
start = time.time()
ls = []
for i in range(10000):
    ls.insert(0, i)
print(f"list.insert(0): {time.time() - start:.4f} сек")

# Вставка в начало с deque — O(n) в цикле
start = time.time()
dq = deque()
for i in range(10000):
    dq.appendleft(i)
print(f"deque.appendleft(): {time.time() - start:.6f} сек")

Практический совет на собеседовании

Вставка в позицию 0 это O(n), потому что нужно переместить все n элементов вправо. Если часто нужно вставлять в начало, используй deque, где appendleft() это O(1).

Это показывает:

• Понимание внутреннего устройства списков
• Знание альтернатив
• Практический опыт оптимизации