Hash Map vs Array vs Linked List for Lookup in DSA C - Trade-offs & Analysis

Mental Model

We want to find a value quickly by searching through different ways of storing data: a hash map, an array, or a linked list.

Analogy: Imagine looking for a book in a library: an array is like checking every book in order on a shelf, a linked list is like following a chain of books one by one, and a hash map is like using a special code to jump directly to the book's spot.

Array: [1] → [2] → [3] → [4] → null
Linked List: 1 → 2 → 3 → 4 → null
Hash Map: buckets with keys pointing directly to values

Dry Run Walkthrough

Input: Data: 4 elements {10, 20, 30, 40}, lookup value 30

Goal: Find if 30 exists using each data structure and compare steps

Step 1: Start lookup in array from index 0

[10] → [20] → [30] → [40] → null, checking index 0 (value 10)

Why: We must check each element in order to find the value

Step 2: Check index 1 (value 20)

[10] → [20] → [30] → [40] → null, checking index 1 (value 20)

Why: Value not found yet, continue searching

Step 3: Check index 2 (value 30), found it

[10] → [20] → [30] → [40] → null, found 30 at index 2

Why: Value found, stop searching

Step 4: Start lookup in linked list at head node

10 → 20 → 30 → 40 → null, at node with value 10

Why: Must traverse nodes one by one

Step 5: Move to next node with value 20

10 → 20 → 30 → 40 → null, at node with value 20

Why: Value not found, continue traversal

Step 6: Move to next node with value 30, found it

10 → 20 → 30 → 40 → null, found 30 at current node

Why: Value found, stop traversal

Step 7: Start lookup in hash map using hash function on 30

Hash map buckets: hash(30) → bucket index 0

Why: Hash function directs us to the bucket quickly

Step 8: Check bucket 0 for key 30, found it immediately

Bucket 0: 30 → value found

Why: Direct access avoids scanning all elements

Result:

Array final state: [10] → [20] → [30] → [40] → null, found 30 at index 2
Linked List final state: 10 → 20 → 30 → 40 → null, found 30 at node 3
Hash Map final state: bucket 0 contains 30, found immediately

Annotated Code

DSA C

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

// Linked List Node
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// Create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

// Insert at end of linked list
void insertLinkedList(Node** head, int val) {
    Node* node = newNode(val);
    if (*head == NULL) {
        *head = node;
        return;
    }
    Node* curr = *head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = node;
}

// Search in linked list
int searchLinkedList(Node* head, int target) {
    Node* curr = head;
    while (curr != NULL) {
        if (curr->val == target) {
            return 1; // found
        }
        curr = curr->next; // advance curr to next node
    }
    return 0; // not found
}

// Search in array
int searchArray(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return 1; // found
        }
    }
    return 0; // not found
}

// Simple hash map with chaining
#define BUCKETS 5

typedef struct HNode {
    int key;
    struct HNode* next;
} HNode;

HNode* hashTable[BUCKETS];

int hashFunction(int key) {
    return key % BUCKETS;
}

void insertHashMap(int key) {
    int index = hashFunction(key);
    HNode* node = (HNode*)malloc(sizeof(HNode));
    node->key = key;
    node->next = hashTable[index];
    hashTable[index] = node;
}

int searchHashMap(int key) {
    int index = hashFunction(key);
    HNode* curr = hashTable[index];
    while (curr != NULL) {
        if (curr->key == key) {
            return 1; // found
        }
        curr = curr->next; // advance curr to next node in bucket
    }
    return 0; // not found
}

int main() {
    int arr[] = {10, 20, 30, 40};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 30;

    // Linked List setup
    Node* head = NULL;
    for (int i = 0; i < size; i++) {
        insertLinkedList(&head, arr[i]);
    }

    // Hash Map setup
    for (int i = 0; i < size; i++) {
        insertHashMap(arr[i]);
    }

    // Search in Array
    printf("Array search for %d: %s\n", target, searchArray(arr, size, target) ? "Found" : "Not Found");

    // Search in Linked List
    printf("Linked List search for %d: %s\n", target, searchLinkedList(head, target) ? "Found" : "Not Found");

    // Search in Hash Map
    printf("Hash Map search for %d: %s\n", target, searchHashMap(target) ? "Found" : "Not Found");

    return 0;
}

curr = curr->next; // advance curr to next node

advance curr to next node — keeps traversing until value found or end

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

scan array elements one by one to find target

curr = hashTable[index]; while (curr != NULL) { if (curr->key == key) return 1; curr = curr->next; }

traverse linked nodes in hash bucket to find key

Output

Array search for 30: Found

Linked List search for 30: Found

Hash Map search for 30: Found

Complexity Analysis

Time: Array and Linked List: O(n) because they check elements one by one; Hash Map: O(1) average because it jumps directly to bucket

Space: Array: O(n) for storing elements; Linked List: O(n) for nodes with pointers; Hash Map: O(n) plus extra space for buckets and pointers

vs Alternative: Hash Map is faster for lookup than Array or Linked List because it avoids scanning all elements, but uses more memory for buckets

Edge Cases

Empty data structures

Search returns not found immediately

DSA C

while (curr != NULL) { ... } in searchLinkedList and searchHashMap

Target not present

Search scans all elements or bucket nodes and returns not found

DSA C

return 0 after full traversal in searchArray, searchLinkedList, searchHashMap

Multiple elements with same hash (collision)

Hash Map handles by chaining nodes in bucket

DSA C

curr = curr->next; in searchHashMap to traverse collisions

When to Use This Pattern

When you need fast lookup by key and can afford extra memory, use a hash map; if data is small or order matters, arrays or linked lists may be simpler.

Common Mistakes

Mistake: Assuming linked list lookup is as fast as array or hash map
Fix: Remember linked list lookup is O(n) because it must check nodes one by one

Mistake: Ignoring hash collisions in hash map lookup
Fix: Always traverse linked nodes in bucket to find key

Summary

Compares how fast we can find a value in hash map, array, and linked list.

Use hash map for fast average lookup, array for simple indexed access, linked list for dynamic size with sequential access.

Hash map uses a hash function to jump directly to data, avoiding scanning all elements.