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

Concept Flow - Hash Map vs Array vs Linked List for Lookup

Start Lookup

↓

Choose Data Structure

↓

Array

↓

Index Access

↓

Compare Key

↓

Found?

↓

Return

↓

End Lookup

Lookup starts by choosing the data structure, then uses index access for arrays, node traversal for linked lists, or hash computation for hash maps to find the key.

Execution Sample

DSA C

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

This code searches for a key in an array by checking each element one by one.

Execution Table

Step	Operation	Data Structure	Pointer/Index	Action	Visual State
1	Start Lookup	Array	i=0	Check arr[0] == key?	[5, 3, 7, 1, 9]
2	Compare	Array	i=0	5 == 7? No	[5, 3, 7, 1, 9]
3	Increment Index	Array	i=1	Move to next element	[5, 3, 7, 1, 9]
4	Compare	Array	i=1	3 == 7? No	[5, 3, 7, 1, 9]
5	Increment Index	Array	i=2	Move to next element	[5, 3, 7, 1, 9]
6	Compare	Array	i=2	7 == 7? Yes	[5, 3, 7, 1, 9]
7	Return Index	Array	i=2	Found key at index 2	[5, 3, 7, 1, 9]
8	End Lookup	Array	-	Lookup complete	[5, 3, 7, 1, 9]
9	Start Lookup	Linked List	current=head	Check node value == key?	5 -> 3 -> 7 -> 1 -> 9 -> null
10	Compare	Linked List	5	5 == 7? No	5 -> 3 -> 7 -> 1 -> 9 -> null
11	Move Next	Linked List	3	Go to next node	5 -> 3 -> 7 -> 1 -> 9 -> null
12	Compare	Linked List	3	3 == 7? No	5 -> 3 -> 7 -> 1 -> 9 -> null
13	Move Next	Linked List	7	Go to next node	5 -> 3 -> 7 -> 1 -> 9 -> null
14	Compare	Linked List	7	7 == 7? Yes	5 -> 3 -> 7 -> 1 -> 9 -> null
15	Return Node	Linked List	7	Found key at node with value 7	5 -> 3 -> 7 -> 1 -> 9 -> null
16	End Lookup	Linked List	-	Lookup complete	5 -> 3 -> 7 -> 1 -> 9 -> null
17	Start Lookup	Hash Map	Compute hash	Hash(key) = 2	[Bucket0: 5, Bucket1: 3, Bucket2: 7, Bucket3: 1, Bucket4: 9]
18	Access Bucket	Hash Map	Bucket2	Check bucket for key	[Bucket0: 5, Bucket1: 3, Bucket2: 7, Bucket3: 1, Bucket4: 9]
19	Compare	Hash Map	Bucket2	7 == 7? Yes	[Bucket0: 5, Bucket1: 3, Bucket2: 7, Bucket3: 1, Bucket4: 9]
20	Return Value	Hash Map	Bucket2	Found key in bucket 2	[Bucket0: 5, Bucket1: 3, Bucket2: 7, Bucket3: 1, Bucket4: 9]
21	End Lookup	Hash Map	-	Lookup complete	[Bucket0: 5, Bucket1: 3, Bucket2: 7, Bucket3: 1, Bucket4: 9]
22	Stop	-	-	All lookups done	-

💡 Lookup stops when key is found or all elements checked.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
Array index i	0	1	2	-	-	-	2
Linked List current node	5	3	7	-	-	-	7
Hash Map bucket index	-	-	2	-	-	-	2

Key Moments - 3 Insights

Why does array lookup stop early at index 2?

Because at step 6 in the execution_table, the array element matches the key, so the function returns immediately without checking further.

Why does linked list lookup need to traverse nodes one by one?

As shown in steps 9 to 15, linked list nodes are connected sequentially, so each node must be checked until the key is found or list ends.

How does hash map find the key so quickly?

At step 17, the hash function computes the bucket index directly, allowing immediate access to the bucket where the key should be, avoiding full traversal.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array index when the key is found?

A 0

B 1

C 2

D 3

💡 Hint

Check step 6 where the comparison returns true and the index is recorded.

At which step does the linked list pointer move from node with value 3 to node with value 7?

A Step 11

B Step 13

C Step 12

D Step 10

💡 Hint

Look at the 'Move Next' operation in the linked list section of the execution_table.

If the hash function returned bucket 3 instead of 2, what would change in the execution_table?

A Bucket accessed would be Bucket3 instead of Bucket2

B The key would be found at Bucket2 anyway

C The linked list traversal would be used instead

D The array index would change

💡 Hint

Refer to steps 17 and 18 where bucket access depends on hash value.

Concept Snapshot

Lookup in Array: check elements one by one until key found or end.
Lookup in Linked List: traverse nodes sequentially until key found.
Lookup in Hash Map: compute hash to find bucket, then check bucket.
Array lookup is O(n), Linked List lookup is O(n), Hash Map lookup is O(1) average.
Hash Map uses extra space but is fastest for lookup.
Arrays have direct index access; linked lists do not.

Full Transcript

This visual execution compares lookup operations in three data structures: array, linked list, and hash map. The lookup starts by choosing the data structure. For arrays, it checks each element by index until the key is found or the end is reached. For linked lists, it traverses nodes one by one, comparing values. For hash maps, it computes a hash to find the bucket directly and checks the bucket for the key. The execution table shows step-by-step operations, pointer or index positions, and the visual state of the data structure. Variable tracking shows how indexes and pointers move during lookup. Key moments clarify why array lookup stops early, why linked lists require traversal, and how hash maps achieve fast access. The quiz tests understanding of these steps. The snapshot summarizes lookup behavior and performance for each data structure.

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