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

Что проверяют

Понимаете ли вы, что у удаления из связного списка две разные цены: найти узел и отцепить его. Для специальности данных и ML вопрос почти всегда уходит в Python: чем list отличается от связного списка и когда нужен deque.

Как отвечать

• итерация: O(n) для любого связного списка, узлы проходятся по ссылкам next от головы;
• удаление по значению или индексу: O(n), потому что узел сначала нужно найти. Само перевешивание ссылок стоит O(1);
• удаление, когда ссылка на узел уже есть: в двусвязном списке O(1), у узла есть prev. В односвязном O(1), только если вы держите и предыдущий узел, например идёте двумя указателями prev и cur. Иначе снова O(n) на поиск предыдущего;
• голова и хвост: удалить голову всегда O(1). Хвост в односвязном списке стоит O(n) даже при известной ссылке на него, потому что нужен предпоследний узел;
• фиктивный узел: sentinel перед головой убирает частный случай удаления первого элемента.

Теперь Python. Встроенный list это динамический массив: доступ по индексу O(1), но pop(0), del lst[i] и insert(0, x) сдвигают хвост и стоят O(n). collections.deque устроен как двусвязный список блоков: append, appendleft, pop, popleft за O(1), зато доступ к середине O(n). OrderedDict связывает словарь с двусвязным списком, поэтому move_to_end и popitem(last=False) работают за O(1), на этом строят LRU-кэши.

Для ML уместно сказать, почему связные списки на практике редкость: узлы разбросаны по памяти, процессорный кэш не помогает, а NumPy и pandas выигрывают именно за счёт непрерывных массивов и векторизации. При этом deque(maxlen=N) отлично подходит для скользящего окна по потоку.

Где спотыкаются

Говорят «удаление в связном списке O(1)» без условия. Интервьюер сразу спросит, откуда взялась ссылка на узел, и ответ развалится.

Называют list в Python связным списком и пишут очередь на lst.pop(0). На миллионе элементов это заметно медленнее, чем deque.popleft().

Удаляют элементы в цикле for x in lst: lst.remove(x). Индексы сдвигаются, и часть элементов пропускается. Нужно собрать новый список или идти по копии.