#include <stdio.h>
#include <stdlib.h>

#define HASH_TABLE_SIZE 10

struct Node {
    int data;
    struct Node* next;
};

struct HashTable {
    struct Node* table[HASH_TABLE_SIZE];
};

// Hash function to compute the index
int hash(int key) {
    return key % HASH_TABLE_SIZE;
}

// Insert a key into the hash table
void insert(struct HashTable* ht, int key) {
    int index = hash(key);
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
	fprintf(stderr, "Memory allocation failed.\n");
	exit(1);
    }
    newNode->data = key;
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

// Search for a key in the hash table
int search(struct HashTable* ht, int key) {
    int index = hash(key);
    struct Node* current = ht->table[index];
    while (current != NULL) {
	if (current->data == key) {
	    return 1; // Key found
	}
	current = current->next;
    }
    return 0; // Key not found
}

void display(struct HashTable* ht) {
    int i;
    struct Node* current;
    for (i = 0; i < HASH_TABLE_SIZE; i++) {
	printf("Index %d: ", i);
	current = ht->table[i];
	while (current != NULL) {
	    printf("%d -> ", current->data);
	    current = current->next;
	}
	printf("NULL\n");
    }
}

int main() {
    struct HashTable ht;
    int i,choice,key;
    for (i = 0; i < HASH_TABLE_SIZE; i++) {
	ht.table[i] = NULL;
    }

    while (choice!=4) {
	printf("\nChoose an operation:\n");
	printf("1. Display hash table\n");
	printf("2. Insert a key\n");
	printf("3. Search for a key\n");
	printf("4. Exit\n");

	scanf("%d", &choice);

	switch (choice) {
	    case 1:
		printf("Hash Table Contents:\n");
		display(&ht);
		break;
	    case 2:
		printf("Enter a key to insert: ");
		scanf("%d", &key);
		insert(&ht, key);
		printf("Key inserted into the hash table.\n");
		break;
	    case 3:
		printf("Enter a key to search: ");
		scanf("%d", &key);
		if (search(&ht, key)) {
		    printf("%d is found in the hash table.\n", key);
		} else {
		    printf("%d is not found in the hash table.\n", key);
		}
		break;
	    case 4:
		exit(0);
	    default:
		printf("Invalid choice. Please choose again.\n");
		break;
	}
    }

    return 0;
}