Introduction

Deletion in a chained hash table can be O(1) if you already have direct access to the node being removed and the chain is implemented as a doubly linked list. The reason is simple: removing a node from a doubly linked list only requires a constant number of pointer updates and no traversal to find the previous node.

Separate chaining stores collisions in per-bucket lists

In a hash table with separate chaining, the hash function picks a bucket and all keys that collide in that bucket are stored in a small container such as a linked list.

Conceptually:

• hash key
• choose bucket
• find node in that bucket's chain
• insert, look up, or delete inside the chain

If the chain is a doubly linked list, each node knows both:

• its next node
• its previous node

That extra prev link is what makes deletion cheap once the node is known.

Deleting a known node from a doubly linked list is constant time

Suppose you already have a pointer to the node:

prev <-> target <-> next

To remove target, you only need to relink its neighbors:

target->prev->next = target->next;
target->next->prev = target->prev;

With edge-case checks for head or tail nodes, that is still constant work. There is no scan through the list to find the predecessor because the node already stores it.

The hidden assumption is "known node" or average-case bucket lookup

This is where explanations often get sloppy. Deletion is not magically O(1) in every possible sense.

There are two related statements:

1. deleting a known node from a doubly linked list is O(1)
2. deleting by key from a well-sized hash table is O(1) on average

The first statement is about linked-list mechanics. The second is about average-case hash-table behavior.

If you only know the key, you still have to hash into the bucket and search that bucket's chain for the matching node. That search is O(1) on average for a good hash table with short chains, but not worst-case O(1) if all keys collide badly.

Why a singly linked list changes the deletion story

In a singly linked list, a node does not know its predecessor. So if you want to delete target, you often need to traverse from the bucket head to find the node before it.

That makes the linked-list part of deletion O(k) where k is the chain length.

The doubly linked list removes that predecessor search, which is why the deletion step itself becomes constant time.

A simple bucket example

Imagine a bucket chain:

[A] <-> [B] <-> [C]

If you want to delete B and you already have a pointer to B, the work is just:

• set A.next to C
• set C.prev to A

That is constant regardless of the overall table size.

Average-case versus worst-case still matters

Hash tables are usually discussed in average-case terms. With a good hash function and a reasonable load factor, bucket chains stay short, so lookup and deletion by key are effectively constant-time on average.

In the worst case, if many keys land in the same bucket, the search inside that chain becomes linear. The doubly linked list does not eliminate that worst-case lookup cost. It only makes the actual unlink operation constant once the node is identified.

Common Pitfalls

• Forgetting that O(1) deletion often assumes you already have the node reference.
• Confusing average-case hash-table complexity with worst-case guarantees.
• Assuming the doubly linked list removes the need to find the correct bucket or key.
• Ignoring that a singly linked list usually needs predecessor traversal for deletion.
• Saying "hash table deletion is always O(1)" without qualifying the assumptions.

Summary

• A doubly linked list supports O(1) removal once the node to delete is already known.
• In a chained hash table, that makes the unlink step constant-time.
• Deletion by key is still only average-case O(1) because you must find the node in the bucket first.
• The prev pointer is what eliminates predecessor traversal.
• The common shorthand is true only when its assumptions are stated clearly.