Mekkora az időbeli komplexitása a listaelemek törlésének?

Временная сложность операции удаления элементов в списке зависит от типа списка и способа удаления:

• Для массива (например, std::vector в C++): удаление элемента по индексу требует сдвига всех последующих элементов влево, поэтому сложность — O(n), где n — количество элементов после удаляемого.

• Для связного списка (например, std::list в C++): удаление элемента, если у вас есть указатель на этот элемент, происходит за O(1), так как нужно просто переназначить указатели. Но если нужно найти элемент по значению или индексу, то поиск занимает O(n).

Таким образом, удаление в массиве — O(n), в связном списке — O(1) при наличии указателя на элемент, иначе O(n) на поиск.