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

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

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

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