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.

Practice

1. Which data structure provides the fastest average lookup time for finding an element by key?

easy

A. Stack

B. Hash Map

C. Linked List

D. Array

Solution

1. Step 1: Understand lookup times for each data structure

   Hash Map uses hashing to find keys quickly, usually in constant time O(1). Arrays require scanning or index access, O(1) if index known but O(n) if searching by value. Linked Lists require scanning all nodes, O(n).

2. Step 2: Compare average lookup times

   Hash Map is fastest on average for key lookup due to direct hashing. Arrays and Linked Lists are slower for key-based search.

3. Final Answer:

   Hash Map -> Option B

4. Quick Check:

   Fastest lookup by key = Hash Map [OK]

Hint: Hash Map lookup is usually O(1), faster than arrays or lists [OK]

Common Mistakes:

• Confusing array index access with key lookup
• Thinking linked list lookup is fast
• Assuming stack is good for key lookup

2. Which of the following is the correct way to declare an array of 5 integers in C?

easy

A. int arr(5);

B. int arr = new int[5];

C. array<int> arr(5);

D. int arr[5];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with type, name, and size in square brackets, e.g., int arr[5];

2. Step 2: Check each option

   int arr[5]; matches correct C syntax. int arr = new int[5]; uses C++ style new keyword. int arr(5); is invalid syntax. array<int> arr(5); is C++ template syntax, not C.

3. Final Answer:

   int arr[5]; -> Option D

4. Quick Check:

   C array declaration = int arr[5]; [OK]

Hint: C arrays use square brackets for size, no new keyword [OK]

Common Mistakes:

• Using C++ new keyword in C
• Using parentheses instead of brackets
• Confusing C++ templates with C arrays

3. Consider the following C code snippet using a linked list for lookup:

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

int lookup(Node* head, int key) {
  Node* current = head;
  while (current != NULL) {
    if (current->key == key) {
      return current->value;
    }
    current = current->next;
  }
  return -1;
}

// List: (1,10) -> (2,20) -> (3,30) -> NULL
// Call: lookup(head, 2);

What is the output of lookup(head, 2);?

medium

A. 20

B. 10

C. 30

D. -1

Solution

1. Step 1: Trace the linked list nodes

   The list nodes have keys and values: (1,10), (2,20), (3,30). The function searches for key 2.

2. Step 2: Follow lookup function logic

   Starting at head (key=1), key != 2, move next. Next node key=2 matches, return value 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Found key 2 with value 20 [OK]

Hint: Linked list lookup scans nodes until key found [OK]

Common Mistakes:

• Returning value of first node always
• Confusing key and value fields
• Returning -1 when key exists

4. The following C code attempts to find a value in an array but has a bug:

int find(int arr[], int size, int target) {
  for (int i = 0; i <= size; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

What is the bug in this code?

medium

A. Return value should be arr[i], not i

B. Function should return void

C. Loop condition should be i < size, not i <= size

D. Array parameter should be int* arr

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= size, which means i can be equal to size. Array indices go from 0 to size-1, so arr[size] is out of bounds.

2. Step 2: Correct loop condition

   Change condition to i < size to avoid accessing out of bounds memory.

3. Final Answer:

   Loop condition should be i < size, not i <= size -> Option C

4. Quick Check:

   Array index must be less than size [OK]

Hint: Array indices go 0 to size-1, use i < size in loops [OK]

Common Mistakes:

• Using <= size causes out-of-bounds access
• Returning arr[i] instead of index
• Changing return type unnecessarily

5. You need to store a large number of unique integer keys with associated values and perform frequent lookups. Which data structure is best and why?

hard

A. Hash Map - because it provides average constant time lookup

B. Linked List - because it allows easy insertion

C. Array - because it uses contiguous memory

D. Binary Search Tree - because it keeps keys sorted

Solution

1. Step 1: Understand requirements

   We need to store many unique keys with values and do frequent lookups efficiently.

2. Step 2: Evaluate data structures

   Array is inefficient for key lookup unless keys are indices. Linked List has slow O(n) lookup. Binary Search Tree has O(log n) lookup but more complex. Hash Map offers average O(1) lookup, ideal for fast access.

3. Final Answer:

   Hash Map - because it provides average constant time lookup -> Option A

4. Quick Check:

   Fast lookup with many keys = Hash Map [OK]

Hint: For fast key lookup, choose Hash Map over arrays or lists [OK]

Common Mistakes:

• Choosing array for non-index keys
• Ignoring lookup speed in linked lists
• Preferring BST without sorting need