Ответ.

История вопроса

Списки (list) — один из базовых встроенных типов данных в Python с первых версий языка. Со временем их внутреннее устройство совершенствовалось, в частности, для повышения производительности и удобства программирования.

Проблема

Важно понимать, что списки в Python реализованы не как связанные, а как динамические массивы. Ошибочное представление приводит к неэффективному коду или неверному подсчету сложности операций.

Решение

Списки реализованы как динамические массивы, которые при необходимости увеличивают размер аллоцированной памяти "скачкообразно" (расширяясь), чтобы избежать постоянных затрат при добавлении элементов. Это позволяет вставлять и удалять элементы в конец списка за амортизированное O(1) время. Вставка или удаление в середине/начале требует перемещения элементов, что занимает O(n) времени.

Пример кода:

my_list = [1, 2, 3]
my_list.append(4)      # Добавление в конец
my_list.insert(1, 'a') # Вставка по индексу
print(my_list)

Ключевые особенности:

Динамическое изменение размера без явного выделения/освобождения памяти пользователем.
Вставка и удаление из конца — быстрая операция, из начала/середины — медленная.
Список может содержать элементы любого типа (гетерогенность).

Вопросы с подвохом.

Можно ли считать list в Python аналогом массива в C? В чем отличие?

Нет, массив в C содержит элементы фиксированного типа, размещенные подряд в памяти. Python list — это массив указателей на объекты, каждый из которых ссылается на самостоятельный объект произвольного типа в куче.

Что произойдет, если вставлять элементы в начало списка в цикле? Это быстро?

Нет, это медленно: при вставке в начало (position 0) каждый раз сдвигаются все существующие элементы вправо. Амортизированная сложность — O(n) на операцию, для больших списков приводит к деградации производительности.

В чем разница между операторами + и append/extend для списков?

создает новый список, не меняя старые. append добавляет элемент в конец исходного списка. extend добавляет к списку все элементы из другой последовательности, изменяя сам объект.

lst1 = [1, 2]
lst2 = [3, 4]
lst3 = lst1 + lst2     # lst3 — новый список
lst1.append(lst2)      # lst1 станет [1, 2, [3, 4]]
lst1.extend(lst2)      # lst1 станет [1, 2, 3, 4], если lst1 не сброшен после предыдущей append

Типовые ошибки и анти-паттерны

Использование list для частых вставок/удалений из начала списка (лучше использовать collections.deque)
Ошибочное ожидание, что list занимает мало памяти и содержит "плотные" данные, как массивы C/Java
Случайное вложение списка внутрь себя (append списка в сам список)

Пример из жизни

Негативный кейс

В проекте для хранения и постоянного удаления первых элементов использовался list. Заметили заметное замедление при большом объеме данных.

Плюсы:

Начало легко, много встроенных методов.

Минусы:

Производительность деградировала, ошибки с памятью при большом объеме.

Позитивный кейс

После выявления проблемы заменили list на collections.deque, который оптимизирован под такие операции.