Question

In simple chaining, what data structure is appropriate ?

• A. Double linked list
• B. Circular linked list
• C. Single linked list
• D. Binary tree

Hint:

For hash table collisions, "chaining" almost always implies using a linked list. Each slot in the hash table acts as the head of a linked list for all the elements that hash to that slot.

Answer 1

The Correct Option is C

Step 1: Understand "chaining" in the context of data structures. Chaining is a common technique used to resolve hash collisions in a hash table. When two keys hash to the same index in the array, the colliding items are stored in a secondary data structure linked from that index.
Step 2: Evaluate the suitability of the options for this purpose.

(A) Double linked list: This would work, but the backward pointer is unnecessary for simple collision resolution. The primary operations are inserting at the head (or tail) and traversing forward, which a singly linked list handles efficiently.
(B) Circular linked list: This adds unnecessary complexity. There is no need for the last element to point back to the first in a hash chain.
(C) Single linked list: This is the most common and appropriate data structure for chaining. It's simple, memory-efficient, and provides all the necessary functionality: insert a new node (usually at the beginning for O(1) insertion) and traverse the list to find an element.
(D) Binary tree (specifically, a self-balancing one like a Red-Black Tree): This can be used for chaining and improves the worst-case lookup time from O(n) to O(log n), but it's more complex and typically used only when the number of collisions is expected to be very large. For "simple chaining," a linked list is the standard choice.
Therefore, a single linked list is the most appropriate and common data structure for simple chaining.