Hash Map vs Array vs Linked List for Lookup in DSA C - Build Both Approaches

Hash Map vs Array vs Linked List for Lookup

📖 Scenario: Imagine you run a small library. You want to quickly find if a book is available by its ID number. You have three ways to store book IDs: an array, a linked list, and a hash map. Each way has different speed for looking up a book.

🎯 Goal: You will create three data structures: an array, a linked list, and a hash map (using a simple array with chaining). Then you will write code to check if a book ID is in each structure. Finally, you will print the results to see which method finds the book fastest.

📋 What You'll Learn

Create an array of book IDs

Create a linked list of book IDs

Create a simple hash map with chaining for book IDs

Write functions to search for a book ID in each data structure

Print whether the book ID was found in each structure

💡 Why This Matters

🌍 Real World

Libraries, stores, and many apps need to quickly find items by ID. Choosing the right data structure helps make searches fast and efficient.

💼 Career

Understanding arrays, linked lists, and hash maps is essential for software developers to write efficient code and optimize performance.

1

Create the array and linked list of book IDs

Create an integer array called book_array with these exact values: 101, 202, 303, 404, 505. Also create a linked list of book IDs with the same values in the same order. Use a struct called Node with an int id and a Node* next. Create the linked list head called book_list.

DSA C

#include 
#include 

// Define Node struct for linked list
typedef struct Node {
    int id;
    struct Node* next;
} Node;

int main() {
    // Create book_array with 101, 202, 303, 404, 505
    // Create linked list book_list with same values
    // Your code here

    return 0;
}

Hint

Use a for loop to create the linked list nodes from the array values in reverse order.

2

Create a simple hash map for book IDs

Create a hash map using an array of pointers to Node called hash_map with size 5. Initialize all entries to NULL. Write a hash function called hash_function that takes an int id and returns id % 5. Insert the book IDs 101, 202, 303, 404, 505 into the hash map using chaining (linked list) at the hashed index.

DSA C

#include 
#include 

// Define Node struct for linked list
typedef struct Node {
    int id;
    struct Node* next;
} Node;

int hash_function(int id) {
    return id % 5;
}

int main() {
    int book_array[5] = {101, 202, 303, 404, 505};

    Node* book_list = NULL;
    Node* temp;
    int values[5] = {101, 202, 303, 404, 505};
    for (int i = 4; i >= 0; i--) {
        temp = (Node*)malloc(sizeof(Node));
        temp->id = values[i];
        temp->next = book_list;
        book_list = temp;
    }

    Node* hash_map[5] = {NULL};
    // Insert book IDs into hash_map using chaining
    // Your code here

    return 0;
}

Hint

Use the hash function to find the index, then add a new node at the front of the linked list at that index.

3

Write search functions for each data structure

Write three functions: int search_array(int* arr, int size, int target), int search_list(Node* head, int target), and int search_hash_map(Node* hash_map[], int size, int target). Each function returns 1 if target is found, else 0. search_array searches the array linearly. search_list searches the linked list linearly. search_hash_map uses the hash function to find the index and searches the linked list at that index.

DSA C

#include 
#include 

// Define Node struct for linked list
typedef struct Node {
    int id;
    struct Node* next;
} Node;

int hash_function(int id) {
    return id % 5;
}

int search_array(int* arr, int size, int target) {
    // Your code here
}

int search_list(Node* head, int target) {
    // Your code here
}

int search_hash_map(Node* hash_map[], int size, int target) {
    // Your code here
}

int main() {
    int book_array[5] = {101, 202, 303, 404, 505};

    Node* book_list = NULL;
    Node* temp;
    int values[5] = {101, 202, 303, 404, 505};
    for (int i = 4; i >= 0; i--) {
        temp = (Node*)malloc(sizeof(Node));
        temp->id = values[i];
        temp->next = book_list;
        book_list = temp;
    }

    Node* hash_map[5] = {NULL};
    for (int i = 0; i id = values[i];
        temp->next = hash_map[index];
        hash_map[index] = temp;
    }

    return 0;
}

Hint

Use simple loops to check each element or node for the target ID.

4

Print search results for a target book ID

In main, set an integer variable target to 303. Use the three search functions to check if target is in book_array, book_list, and hash_map. Print the results exactly as follows (each on its own line):
Array: Found or Array: Not Found
Linked List: Found or Linked List: Not Found
Hash Map: Found or Hash Map: Not Found

DSA C

#include 
#include 

// Define Node struct for linked list
typedef struct Node {
    int id;
    struct Node* next;
} Node;

int hash_function(int id) {
    return id % 5;
}

int search_array(int* arr, int size, int target) {
    for (int i = 0; i id == target) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

int search_hash_map(Node* hash_map[], int size, int target) {
    int index = hash_function(target);
    Node* current = hash_map[index];
    while (current != NULL) {
        if (current->id == target) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

int main() {
    int book_array[5] = {101, 202, 303, 404, 505};

    Node* book_list = NULL;
    Node* temp;
    int values[5] = {101, 202, 303, 404, 505};
    for (int i = 4; i >= 0; i--) {
        temp = (Node*)malloc(sizeof(Node));
        temp->id = values[i];
        temp->next = book_list;
        book_list = temp;
    }

    Node* hash_map[5] = {NULL};
    for (int i = 0; i id = values[i];
        temp->next = hash_map[index];
        hash_map[index] = temp;
    }

    int target = 303;
    // Print search results for target
    // Your code here

    return 0;
}

Hint

Use printf to print the exact lines. Call each search function with target and print "Found" or "Not Found" accordingly.