Почему удаление элемента в связанном списке стоит O(1) ⇐ C++

[Anonymous]

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

Код: Выделить всё

// These operations have to find the previous node of the position, so it costs O(n).
node* erase(node* head, int pos);
node* erase(node* node_to_delete);

// This operation costs O(1), but it affect the validation of the reference of the next node.
node* erase(node* position) {
if (position == _last)
return _last;
auto tmp = position -> next;
position -> val = position -> next -> val;
position -> next = position -> next -> next;
delete tmp;
if (tmp == _last)
_last = position;
_size--;
return position;
}

Я ожидаю вставки или удаления узла в O(1).

Подробнее здесь: https://stackoverflow.com/questions/782 ... t-costs-o1