When a room is full, add another cot

Every slot holds a list, not just a value

In a hostel with double rooms, a room designed for two just holds two occupants — no need to relocate anyone. Chaining applies the same idea to a hash table: each slot holds not one value but a small linked list of every key that has ever hashed there. Inserting always succeeds at the computed slot — you simply add to that slot's list.

This is Unit I's singly linked list, doing real work again, one per bucket.

struct Node { int key; struct Node *next; };
struct Node *table[TABLE_SIZE];   /* one linked-list head per slot */

void insert(int key)
{
    int index = key % TABLE_SIZE;
    struct Node *n = malloc(sizeof(struct Node));
    n->key = key;
    n->next = table[index];   /* insert-front, from Unit I Lesson 2 */
    table[index] = n;
}

Search means checking the bucket's whole list

Searching hashes the key to find the right bucket in one step, then walks that bucket's list comparing each entry — exactly Unit I Lesson 2's traversal, just scoped to one small list instead of the whole table.

The worst case is an old friend

If a poor hash function or bad luck sends every key to the same bucket, chaining degrades into a single long linked list — every lookup then costs Unit I's O(n) list traversal, exactly the cost a hash table exists to avoid. This is why Lesson 2's hash function quality matters: chaining does not fail when collisions happen, but it does lose its speed advantage if collisions happen too often.