#include <stdio.h>
#include <stdlib.h>
 
#define TABLE_SIZE 10
 
// Node structure for chaining
struct Node {
    int data;
    struct Node* next;
};
 
struct Node* hashTable[TABLE_SIZE];
 
// Hash function
int hashFunction(int key) {
    return key % TABLE_SIZE;
}
 
// Insert key into hash table
void insert(int key) {
    int index = hashFunction(key);
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = key;
    newNode->next = NULL;
 
    if (hashTable[index] == NULL) {
        hashTable[index] = newNode;
    } else {
        // Insert at beginning of linked list
        newNode->next = hashTable[index];
        hashTable[index] = newNode;
    }
}
 
// Search key in hash table
int search(int key) {
    int index = hashFunction(key);
    struct Node* temp = hashTable[index];
    while (temp != NULL) {
        if (temp->data == key)
            return 1;
        temp = temp->next;
    }
    return 0;
}
 
// Display hash table
void display() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        struct Node* temp = hashTable[i];
        printf("[%d] -> ", i);
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}
 
int main() {
    int choice, key;
 
    while (1) {
        printf("\n1. Insert\n2. Search\n3. Display\n4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
 
        switch (choice) {
            case 1:
                printf("Enter key to insert: ");
                scanf("%d", &key);
                insert(key);
                break;
            case 2:
                printf("Enter key to search: ");
                scanf("%d", &key);
                if (search(key))
                    printf("Key %d found in hash table.\n", key);
                else
                    printf("Key %d not found.\n", key);
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
            default:
                printf("Invalid choice!\n");
        }
    }
}