Why deleting an element in a linkedlist costs O(1)

Question

As the textbook shown, a linkedlist is good for those situations where it frequently inserts or deletes since it costs O(1) for these operations. However, a node of linkedlist doesnot contains any pointer that points to the previous node. So if I need to delete a specific node, I may have to find the previous node and change the information of its next pointer, which costs O(n). Or, if not, the reference for the next node will be affected. I don't know how to solve this problem.

// 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;
}

I expect insert or delete the node in O(1).

Answer 1

There's no reason why you have to start with a pointer to the node itself. You can work with pointers to preceding nodes.

Answer 2

The code does not delete the current node at position, instead the code emulates deletion of the current node by copying the next node's data and next pointer into the current node, then it deletes the next node. This is why the code is O(1). If there are any existing pointers to the next node, then those pointers become invalid since it it the next node that is being deleted. The code fails to delete anything if position is _last, since there is no next node, instead this is the one case where it should require O(n) time to scan the list in order to delete the actual last node and update _last to point to the prior node.