Какая структура данных реализует список в Python и почему операции добавления и удаления могут быть O(1)
Что проверяют
Знаете ли вы, что list в CPython это динамический массив, а не связный список, и понимаете ли слово «амортизированная». Следом спрашивают, какие операции со списком как раз не O(1) и что взять вместо него.
Как отвечать
В CPython список это структура PyListObject: указатель на непрерывный массив ссылок на объекты, текущая длина и число выделенных ячеек allocated. Сами элементы лежат отдельно, поэтому в одном списке уживаются значения разных типов.
append: если свободная ячейка есть, ссылка кладётся в неё за O(1). Если нет, выделяется массив с запасом и ссылки копируются. Запас небольшой, около 1/8 размера плюс константа, но рост пропорциональный, поэтому n вставок в сумме стоят O(n), а одна в среднем O(1). Это и есть амортизированная оценка;pop(): снятие с конца O(1), сдвигать ничего не нужно. Когда список сильно пустеет, память перераспределяется, но и это амортизируется;insert(0, x),pop(0),del a[i]: O(n), все элементы правее сдвигаются;x in a,a.remove(x): O(n), линейный поиск.
Рост легко показать: sys.getsizeof у растущего списка меняется не на каждой вставке, а скачками.
Если нужны быстрые операции с обоих концов, берут collections.deque: вставка и удаление слева и справа за O(1), зато доступ по индексу в середину медленный. Для проверки вхождения нужен set.
Для data-ml важно ещё одно: массив NumPy имеет фиксированный размер, и np.append каждый раз создаёт новый массив целиком. Накопление в цикле через np.append даёт O(n²), правильно собрать данные в список и один раз вызвать np.array.
Где спотыкаются
Говорят, что при переполнении массив растёт в полтора или два раза. Для многих языков это так, но CPython увеличивает список примерно на 12,5%, и эта деталь сразу показывает, знаете ли вы реализацию.
Называют O(1) без слова «амортизированно». Отдельная вставка, попавшая на перевыделение, стоит O(n), и для задач с жёсткими задержками это важно.
Делают очередь на списке через pop(0). На больших объёмах BFS или обработка потока с такой очередью становится квадратичной.