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 find books quickly by their ID numbers. You have three ways to store books: an array, a linked list, and a hash map. Each way stores book IDs differently. You want to see how fast you can find a book in each storage.

🎯 Goal: You will create three data structures: an array, a linked list, and a hash map with the same book IDs. Then, you will write code to look up a specific book ID in each structure and print whether it was found or not.

📋 What You'll Learn

Create an array with book IDs: 101, 102, 103, 104, 105

Create a linked list with the same book IDs in the same order

Create a hash map with book IDs as keys and book names as values

Write lookup code to find book ID 103 in each data structure

Print the result of each lookup as 'Found' or 'Not Found'

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding how arrays, linked lists, and hash maps work and their lookup speeds is important for software developers to write efficient code.

1

Create the array and linked list of book IDs

Create an integer array called bookArray with these exact values: 101, 102, 103, 104, 105. Also, create a singly linked list called bookList with nodes containing the same values in the same order.

DSA C++

#include 

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

int main() {

    // Create bookArray with 101, 102, 103, 104, 105
    // Create linked list bookList with same values

    return 0;
}

Hint

Use an array initializer for bookArray. For the linked list, create the first node and then link the next nodes one by one.

2

Create the hash map of book IDs to names

Include the <unordered_map> header. Create an unordered_map<int, std::string> called bookMap with these exact entries: 101: "Book A", 102: "Book B", 103: "Book C", 104: "Book D", 105: "Book E".

DSA C++

#include 
#include 

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

int main() {
    int bookArray[5] = {101, 102, 103, 104, 105};

    Node* bookList = new Node{101, nullptr};
    bookList->next = new Node{102, nullptr};
    bookList->next->next = new Node{103, nullptr};
    bookList->next->next->next = new Node{104, nullptr};
    bookList->next->next->next->next = new Node{105, nullptr};

    // Create unordered_map bookMap with given entries

    return 0;
}

Hint

Use curly braces to initialize bookMap with key-value pairs inside the unordered_map declaration.

3

Write lookup code for book ID 103 in all structures

Write code to check if the book ID 103 is in bookArray by looping through it. Then, check if 103 is in the linked list bookList by traversing nodes. Finally, check if 103 is a key in bookMap using its find method. For each check, create a boolean variable: foundInArray, foundInList, and foundInMap.

DSA C++

#include 
#include 

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

int main() {
    int bookArray[5] = {101, 102, 103, 104, 105};

    Node* bookList = new Node{101, nullptr};
    bookList->next = new Node{102, nullptr};
    bookList->next->next = new Node{103, nullptr};
    bookList->next->next->next = new Node{104, nullptr};
    bookList->next->next->next->next = new Node{105, nullptr};

    std::unordered_map bookMap = {
        {101, "Book A"},
        {102, "Book B"},
        {103, "Book C"},
        {104, "Book D"},
        {105, "Book E"}
    };

    // Check if 103 is in bookArray, bookList, and bookMap

    return 0;
}

Hint

Use a for loop to check the array. Use a while loop to traverse the linked list. Use bookMap.find(103) != bookMap.end() to check the hash map.

4

Print the lookup results

Print the results of the lookups using std::cout. For each boolean variable (foundInArray, foundInList, foundInMap), print exactly these lines:
"Array lookup: Found" or "Array lookup: Not Found"
"Linked list lookup: Found" or "Linked list lookup: Not Found"
"Hash map lookup: Found" or "Hash map lookup: Not Found" depending on the boolean value.

DSA C++

#include 
#include 

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

int main() {
    int bookArray[5] = {101, 102, 103, 104, 105};

    Node* bookList = new Node{101, nullptr};
    bookList->next = new Node{102, nullptr};
    bookList->next->next = new Node{103, nullptr};
    bookList->next->next->next = new Node{104, nullptr};
    bookList->next->next->next->next = new Node{105, nullptr};

    std::unordered_map bookMap = {
        {101, "Book A"},
        {102, "Book B"},
        {103, "Book C"},
        {104, "Book D"},
        {105, "Book E"}
    };

    bool foundInArray = false;
    for (int i = 0; i data == 103) {
            foundInList = true;
            break;
        }
        current = current->next;
    }

    bool foundInMap = (bookMap.find(103) != bookMap.end());

    // Print the lookup results

    return 0;
}

Hint

Use std::cout and the ternary operator to print "Found" or "Not Found" based on each boolean variable.

Practice

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

easy

A. Array

B. Stack

C. Linked List

D. Hash Map

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 searching elements, which is O(n) unless index is known. Linked Lists require traversal, also O(n).

2. Step 2: Compare average lookup times

   Hash Map average lookup is O(1), Array and Linked List average lookup is O(n). So Hash Map is fastest for key-based lookup.

3. Final Answer:

   Hash Map -> Option D

4. Quick Check:

   Fastest lookup = 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 faster than array
• Assuming stack is good for key lookup

2. Which of the following is the correct way to declare a hash map in C++ using STL for integer keys and string values?

easy

A. std::unordered_map map;

B. std::map map;

C. std::hash_map map;

D. std::unordered_map map;

Solution

1. Step 1: Identify correct STL container for hash map

   In modern C++, std::unordered_map is the standard hash map container. std::hash_map is deprecated or non-standard.

2. Step 2: Check key and value types

   We want integer keys and string values, so std::unordered_map is correct. std::map map; uses std::map which is a balanced tree, not hash map. std::unordered_map map; swaps key and value types.

3. Final Answer:

   std::unordered_map map; -> Option A

4. Quick Check:

   Correct hash map syntax = std::unordered_map map; [OK]

Hint: Use std::unordered_map for hash maps in C++ [OK]

Common Mistakes:

• Using std::map instead of unordered_map for hash map
• Swapping key and value types
• Using deprecated std::hash_map

3. What will be the output of the following C++ code snippet?

#include <iostream>
#include <unordered_map>
int main() {
    std::unordered_map map = {{1, "one"}, {2, "two"}, {3, "three"}};
    if (map.find(2) != map.end()) {
        std::cout << map[2];
    } else {
        std::cout << "Not found";
    }
    return 0;
}

medium

A. three

B. Not found

C. two

D. Compilation error

Solution

1. Step 1: Understand the map initialization and lookup

   The unordered_map is initialized with keys 1, 2, 3 and their string values. The code checks if key 2 exists using find.

2. Step 2: Check the condition and output

   Since key 2 exists, map[2] returns "two" which is printed.

3. Final Answer:

   two -> Option C

4. Quick Check:

   Key 2 found, output = two [OK]

Hint: Check if key exists before accessing map to avoid errors [OK]

Common Mistakes:

• Assuming map[2] returns "Not found" if key missing
• Confusing find() return value
• Thinking unordered_map is ordered

4. The following code tries to find an element in a linked list but causes a runtime error. What is the main issue?

#include <iostream>
struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = nullptr;
    // No nodes added
    Node* current = head;
    while (current->data != 5) {
        current = current->next;
    }
    std::cout << "Found 5";
    return 0;
}

medium

A. Infinite loop because next is never updated

B. Dereferencing null pointer when list is empty

C. Missing return statement in main

D. Incorrect struct definition

Solution

1. Step 1: Analyze linked list initialization

   The list is empty (head is nullptr). The pointer current is set to nullptr.

2. Step 2: Identify cause of runtime error

   The code tries to access current->data without checking if current is nullptr, causing a null pointer dereference and runtime crash.

3. Final Answer:

   Dereferencing null pointer when list is empty -> Option B

4. Quick Check:

   Null pointer access causes runtime error [OK]

Hint: Always check pointer is not null before dereferencing [OK]

Common Mistakes:

• Ignoring null pointer checks
• Assuming list has elements without adding
• Confusing infinite loop with crash

5. You need to store a large dataset of user IDs (integers) and their names (strings) for fast lookup by ID. Which data structure is best and why? Choose the best option considering lookup speed, memory, and insertion time.

hard

A. Hash Map, because it offers average O(1) lookup and efficient insertion

B. Linked List, because it uses less memory and is easy to insert

C. Array, because it provides O(1) lookup by index

D. Binary Search Tree, because it keeps data sorted for fast lookup

Solution

1. Step 1: Evaluate array suitability

   Array lookup by index is O(1), but user IDs are keys, not indices, so array lookup is O(n) unless IDs are continuous and small, which is unlikely.

2. Step 2: Compare linked list and binary search tree

   Linked list lookup is O(n), slow for large data. Binary search tree lookup is O(log n), better but slower than hash map average O(1).

3. Step 3: Assess hash map advantages

   Hash map provides average O(1) lookup and insertion, ideal for large datasets with arbitrary keys like user IDs.

4. Final Answer:

   Hash Map, because it offers average O(1) lookup and efficient insertion -> Option A

5. Quick Check:

   Best for fast key lookup = Hash Map [OK]

Hint: Use hash map for fast key-based lookup and insertion [OK]

Common Mistakes:

• Assuming array is always fastest for lookup
• Ignoring hash map memory overhead
• Choosing linked list for fast lookup