Hash Map vs Array vs Linked List for Lookup in DSA C - Complexity Comparison

Time Complexity: Hash Map vs Array vs Linked List for Lookup

O(n) for array and linked list, O(1) average for hash map

Understanding Time Complexity

We want to understand how fast we can find a value in different data structures.

The question is: How does the time to find something change as the data grows?

Scenario Under Consideration

Analyze the time complexity of the following lookup operations.

// Lookup in array
int lookup_array(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

// Lookup in linked list
int lookup_linked_list(Node* head, int target) {
    Node* current = head;
    while (current != NULL) {
        if (current->value == target) return 1;
        current = current->next;
    }
    return 0;
}

// Lookup in hash map (simplified)
int lookup_hash_map(HashMap* map, int target) {
    int index = hash(target) % map->capacity;
    Entry* entry = map->buckets[index];
    while (entry != NULL) {
        if (entry->key == target) return 1;
        entry = entry->next;
    }
    return 0;
}

This code shows how to find a value in an array, a linked list, and a hash map.

Identify Repeating Operations

Look at what repeats when searching:

• Array: Loop through each element one by one.
• Linked List: Traverse nodes one by one until found or end.
• Hash Map: Check entries in one bucket's linked list after hashing.
• Dominant operation: Number of elements checked in the search.

How Execution Grows With Input

As the number of items (n) grows, how many checks happen?

Input Size (n)	Array & Linked List Checks	Hash Map Checks (average)
10	Up to 10 checks	About 1 check
100	Up to 100 checks	About 1 check
1000	Up to 1000 checks	About 1 check

Array and linked list checks grow directly with n. Hash map checks stay roughly the same if well sized.

Final Time Complexity

Time Complexity: O(n) for array and linked list, O(1) average for hash map lookup

This means array and linked list take longer as data grows, but hash map stays fast on average.

Common Mistake

[X] Wrong: "Hash map lookup is always O(1) no matter what."

[OK] Correct: If many keys collide, hash map lookup can slow down to O(n) in worst case.

Interview Connect

Knowing these differences helps you choose the right data structure and explain your choices clearly.

Self-Check

"What if the hash map uses a poor hash function causing many collisions? How would the lookup time change?"