为什么删除链表中的元素需要花费O(1)

Question

正如教科书所示，链表适用于频繁插入或删除的情况，因为这些操作的成本为 O(1)。然而，链表的节点不包含任何指向前一个节点的指针。因此，如果我需要删除某个特定节点，我可能必须找到前一个节点并更改其

next

指针的信息，这需要 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) 中插入或删除节点。

Answer 1

没有理由必须从指向节点本身的指针开始。您可以使用指向前面节点的指针。