Что хотят услышать интервьюеры:

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

Определение:

Связанный список — это структура данных, где каждый узел хранит значение и ссылку на следующий узел, а иногда и на предыдущий.
Итерация — последовательный обход узлов по ссылкам.
Удаление узла зависит от того, известен ли сам узел и есть ли доступ к соседним узлам: если все нужные ссылки уже есть, операция выполняется быстро; если узел сначала нужно искать, основное время уходит на поиск.

Пример использования:

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

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def iterate(head):
    cur = head
    while cur:
        print(cur.value)
        cur = cur.next

def delete_first(head, target):
    dummy = Node(0, head)
    prev, cur = dummy, head

    while cur:
        if cur.value == target:
            prev.next = cur.next
            break
        prev, cur = cur, cur.next

    return dummy.next

Пояснение кода:

iterate(head) проходит по списку от головы до конца.
На каждой итерации берётся текущий узел и переход выполняется через cur = cur.next.
Время обхода пропорционально числу узлов, то есть O(n).
delete_first(head, target) сначала ищет узел со значением target.
Если узел найден, ссылка prev.next переназначается на cur.next, и узел исключается из цепочки.
Поиск в этом примере занимает O(n), а само переназначение ссылки — O(1).
Для удаления головы используется dummy, чтобы не делать отдельную ветку логики для первого элемента.

Ключевые моменты:

Итерация по связанному списку — O(n).
Удаление узла — O(1), если узел уже найден и есть нужные ссылки.
Если сначала нужно искать узел, общая сложность удаления становится O(n).
В односвязном списке удаление обычно требует знания предыдущего узла.
В двусвязном списке удаление проще, но поиск элемента всё равно остаётся O(n).
Сложность зависит не только от типа списка, но и от того, известен ли адрес удаляемого узла заранее.

Какая алгоритмическая сложность операций итерации и удаления узла в связанных списках?