Как устроен список в Python и какова временная сложность основных операций?

В Python список (list) реализован как динамический массив. Это означает, что элементы хранятся в непрерывном блоке памяти, и при необходимости размер массива увеличивается автоматически.

Основные операции и их временная сложность:

• Доступ по индексу (list[i]): O(1) — прямой доступ к элементу.
• Добавление в конец (append): амортизированное O(1) — обычно быстро, но иногда требует перераспределения памяти.
• Вставка или удаление в середине списка: O(n) — из-за необходимости сдвигать элементы.
• Поиск элемента (in или index): O(n) — перебор элементов.

Таким образом, списки удобны для операций с доступом по индексу и добавлением в конец, но менее эффективны для вставок и удалений в середине.

Пример:

lst = [1, 2, 3]
lst.append(4)      # O(1)
print(lst[2])      # O(1), выводит 3
lst.insert(1, 10)  # O(n), вставка в середину