Why deletion of elements of hash table using doubly-linked list is O(1)?

The problem presented here is : consider you have are looking at a particular element of a hashtable. How costly is it to delete it?

Suppose you have a simple linked list :

v ----> w ----> x ----> y ----> z
                |
            you're here

Now if you remove x, you need to connect w to y to keep your list linked. You need to access w and tell it to point to y (you want to have w ----> y). But you can't access w from x because it's simply linked! Thus you have to go through all your list to find w in O(n) operations, and then tell it to link to y. That's bad.

Then, suppose you're doubly-linked :

v <---> w <---> x <---> y <---> z
                |
            you're here

Cool, you can access w and y from here, so you can connect the two (w <---> y) in O(1) operation!

It seems to me that the hash table part of this is mostly a red herring. The real question is: "can we delete the current element from a linked list in constant time, and if so how?"

The answer is: it's a little tricky, but in effect yes, we can -- at least usually. We do not (normally) have to traverse the entire linked list to find the previous element. Instead, we can swap the data between the current element and the next element, then delete the next element.

The one exception to this is when/if we need/want to delete the last item in the list. In this case, there is no next element to swap with. If you really have to do that, there's no real way to avoid finding the previous element. There are, however, ways that will generally work to avoid that -- one is to terminate the list with a sentinel instead of a null pointer. In this case, since we never delete the node with the sentinel value, we never have to deal with deleting the last item in the list. That leaves us with relatively simple code, something like this:

template <class key, class data>
struct node {
    key k;
    data d;
    node *next;
};

void delete_node(node *item) {
    node *temp = item->next;
    swap(item->key, temp->key);
    swap(item->data, temp->data);
    item ->next = temp->next;
    delete temp;
}