Collision Handling Using Chaining in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the head of the linked list to NULL in the hash table.

DSA C

hashTable->buckets[index].head = [1];

Drag options to blanks, or click blank then click option'

ANULL

Bhead

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of NULL which is less clear.

Assigning 1 or an uninitialized variable.

In chaining, each bucket's linked list head should start as NULL to indicate it is empty.

2fill in blank

medium

Complete the code to create a new node and assign the key value in the chaining linked list.

DSA C

newNode = (Node*)malloc(sizeof(Node));
newNode->key = [1];

Drag options to blanks, or click blank then click option'

ANULL

Bkey

Cindex

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning value or index instead of key.

Assigning NULL which is invalid for key.

The new node's key field should be assigned the key passed to the insert function.

3fill in blank

hard

Fix the error in the code to insert the new node at the beginning of the linked list for chaining.

DSA C

newNode->next = [1];
hashTable->buckets[index].head = newNode;

Drag options to blanks, or click blank then click option'

AhashTable->buckets[index].head

BnewNode

CNULL

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Setting next to newNode causes a cycle.

Setting next to NULL loses the existing list.

The new node's next pointer should point to the current head of the list before updating the head.

4fill in blank

hard

Fill both blanks to complete the search function that traverses the linked list to find a key.

DSA C

Node* current = hashTable->buckets[index].head;
while (current != [1]) {
    if (current->key == [2]) {
        return current;
    }
    current = current->next;
}

Drag options to blanks, or click blank then click option'

ANULL

Bkey

C0

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of NULL to check end of list.

Comparing with index instead of key.

The loop continues until current is NULL, and compares current->key with the search key.

5fill in blank

hard

Fill all three blanks to complete the delete function that removes a node with a given key from the chain.

DSA C

Node* current = hashTable->buckets[index].head;
Node* prev = [1];
while (current != NULL && current->key != [2]) {
    prev = current;
    current = current->next;
}
if (current == NULL) return;
if (prev == NULL) {
    hashTable->buckets[index].head = current->next;
} else {
    prev->next = [3];
}
free(current);

Drag options to blanks, or click blank then click option'

ANULL

Bkey

Ccurrent->next

DhashTable->buckets[index].head

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing prev to head instead of NULL.

Comparing with index instead of key.

Setting prev->next to current instead of current->next.

Initially, prev is NULL. We look for the node with the key. If prev is NULL, we update head. Otherwise, prev->next skips the deleted node.

Practice

1. What is the main idea behind collision handling using chaining in hash tables?

easy

A. Store all elements that hash to the same index in a linked list at that index

B. Replace the existing element with the new one when a collision occurs

C. Use a secondary hash function to find a new index

D. Resize the hash table immediately when a collision happens

Solution

1. Step 1: Understand collision in hash tables

   When two keys hash to the same index, a collision occurs.

2. Step 2: Explain chaining method

   Chaining stores all collided elements in a linked list at that index, allowing multiple elements per slot.

3. Final Answer:

   Store all elements that hash to the same index in a linked list at that index -> Option A

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked list at each hash index [OK]

Common Mistakes:

• Confusing chaining with open addressing
• Thinking collisions overwrite existing data
• Believing resizing happens on every collision

2. Which of the following is the correct way to declare a node structure for chaining in C?

easy

A. typedef struct Node { int key; Node* next; } Node;

B. struct Node { int key; int next; };

C. typedef struct Node { int key; struct Node* next; } Node;

D. struct Node { int key; struct Node next; };

Solution

1. Step 1: Check correct pointer usage in struct

   In C, to create a linked list node, the next pointer must be a pointer to the same struct type.

2. Step 2: Validate typedef syntax

   typedef struct Node { int key; struct Node* next; } Node; correctly uses struct Node* next; and typedefs the struct as Node.

3. Final Answer:

   typedef struct Node { int key; struct Node* next; } Node; -> Option C

4. Quick Check:

   Pointer to struct Node is struct Node* next [OK]

Hint: Use struct Node* for next pointer in C structs [OK]

Common Mistakes:

• Using struct Node next instead of pointer
• Missing typedef keyword or incorrect syntax
• Declaring next as int instead of pointer

3. Consider the following code snippet for inserting keys into a hash table using chaining. What will be the output after inserting keys 5, 15, and 25 if the hash function is key % 10?

typedef struct Node {
  int key;
  struct Node* next;
} Node;

Node* hashTable[10] = {NULL};

void insert(int key) {
  int index = key % 10;
  Node* newNode = malloc(sizeof(Node));
  newNode->key = key;
  newNode->next = hashTable[index];
  hashTable[index] = newNode;
}

// Insert keys
insert(5);
insert(15);
insert(25);

// Print keys at index 5
Node* temp = hashTable[5];
while(temp != NULL) {
  printf("%d -> ", temp->key);
  temp = temp->next;
}
printf("NULL\n");

medium

A. NULL

B. 5 -> 15 -> 25 -> NULL

C. 15 -> 25 -> 5 -> NULL

D. 25 -> 15 -> 5 -> NULL

Solution

1. Step 1: Calculate hash index for each key

   All keys 5, 15, 25 % 10 = 5, so all go to index 5.

2. Step 2: Trace insertion order in chaining

   Each new node is inserted at the head, so order is 25 (last inserted), then 15, then 5.

3. Final Answer:

   25 -> 15 -> 5 -> NULL -> Option D

4. Quick Check:

   New nodes added at head = 25 -> 15 -> 5 [OK]

Hint: New nodes go to head of list in chaining [OK]

Common Mistakes:

• Assuming insertion at tail instead of head
• Miscomputing hash index
• Printing keys in wrong order

4. The following code for inserting into a chained hash table has a bug. What is the bug?

void insert(int key) {
  int index = key % 10;
  Node newNode;
  newNode.key = key;
  newNode.next = hashTable[index];
  hashTable[index] = &newNode;
}

medium

A. No bug, code is correct

B. newNode is a local variable and will be lost after function ends

C. next pointer is not assigned properly

D. Hash function is incorrect

Solution

1. Step 1: Identify variable scope issue

   newNode is declared as a local variable on the stack inside insert function.

2. Step 2: Explain why this causes a bug

   After function returns, newNode memory is invalid, so hashTable points to invalid memory.

3. Final Answer:

   newNode is a local variable and will be lost after function ends -> Option B

4. Quick Check:

   Local variable address stored = invalid pointer [OK]

Hint: Use malloc for nodes, not local variables [OK]

Common Mistakes:

• Ignoring variable lifetime
• Thinking hash function is wrong
• Assuming next pointer assignment is incorrect

5. You have a hash table of size 7 using chaining. You insert keys: 10, 21, 17, 14, 28. The hash function is key % 7. After all insertions, which index will have the longest chain and what will be the order of keys in that chain if new nodes are inserted at the head?

hard

A. Index 0: 28 -> 14 -> 21 -> NULL

B. Index 3: 17 -> 14 -> 28 -> NULL

C. Index 3: 14 -> 17 -> 28 -> NULL

D. Index 4: 10 -> 21 -> NULL

Solution

1. Step 1: Compute hash index for each key

   10 % 7 = 3, 21 % 7 = 0, 17 % 7 = 3, 14 % 7 = 0, 28 % 7 = 0.

2. Step 2: Group keys by index and order insertion at head

   Index 0 keys inserted in order: 21, then 14, then 28 (last inserted at head). So chain at index 0 is 28 -> 14 -> 21 -> NULL.
   Index 3 keys are 10 and 17.

3. Final Answer:

   Index 0: 28 -> 14 -> 21 -> NULL -> Option A

4. Quick Check:

   Longest chain at index 0 with keys inserted at head [OK]

Hint: Calculate key % size, insert new nodes at head [OK]

Common Mistakes:

• Miscomputing hash indexes
• Mixing up insertion order in chains
• Choosing wrong index for longest chain