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.

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