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

Временная сложность удаления элемента в односвязном списке зависит от того, есть ли у нас указатель на удаляемый элемент или только на голову списка.

• Если нужно удалить элемент, зная только голову списка, то сначала нужно пройти по списку, чтобы найти элемент и его предыдущий узел. Это занимает O(n) времени, где n — количество элементов в списке.
• Если у нас есть указатель на предыдущий элемент (или на сам удаляемый элемент, если это первый элемент), то удаление происходит за O(1), так как достаточно перенастроить ссылки.

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