Какова сложность удаления элемента из списка по индексу?

Удаление из середины или начала Python-списка требует сдвига последующих ссылок и имеет O(n) сложность в худшем случае. Удаление последнего элемента обычно O(1) амортизированно.

Для индекса i число сдвигаемых элементов примерно n-i-1. Это не копирование самих вложенных объектов, а перемещение ссылок в массиве. list.remove(value) дополнительно ищет значение, тогда как del items[i] и pop(i) используют индекс. Для частых удалений с обоих концов подходит deque; для произвольных позиций выбор структуры зависит от поиска и доступа. Сложная финализация удалённого объекта может добавить собственную стоимость.