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

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

Start Lookup

↓

Choose Data Structure

↓

Array

↓

Linear [Traverse

↓

Check Key

↓

Compare

↓

Found?

↓

Return

↓

End

Lookup starts by choosing the data structure, then follows its specific search steps until the item is found or not.

Execution Sample

DSA Javascript

const arr = [10, 20, 30];
const map = {a: 10, b: 20};
const list = {head: {value: 10, next: {value: 20, next: null}}};

// Lookup 20 in each

This code shows lookup of value 20 in an array, a hash map, and a linked list.

Execution Table

Step	Data Structure	Operation	Details	Result	Visual State
1	Array	Start Search	Check index 0	Value 10 != 20	[10, 20, 30]
2	Array	Check Next	Check index 1	Value 20 == 20 (Found)	[10, 20, 30]
3	Array	Return	Return index 1	Found at index 1	[10, 20, 30]
4	Linked List	Start at Head	Node value 10	Value 10 != 20	10 -> 20 -> null
5	Linked List	Move Next	Node value 20	Value 20 == 20 (Found)	10 -> 20 -> null
6	Linked List	Return	Return node with value 20	Found node	10 -> 20 -> null
7	Hash Map	Compute Hash	Key 'b'	Hash computed	{a:10, b:20}
8	Hash Map	Direct Access	Access map['b']	Value 20 == 20 (Found)	{a:10, b:20}
9	Hash Map	Return	Return value 20	Found value	{a:10, b:20}
10	All	End	Lookup complete	All found 20	Array: [10,20,30], List: 10->20->null, Map: {a:10,b:20}

💡 Lookup ends when value 20 is found in each data structure or all elements checked.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 5	After Step 7	After Step 8	Final
Array Index	N/A	0	1	N/A	N/A	N/A	N/A	1
Linked List Current Node	Head (10)	Head (10)	N/A	10	20	N/A	N/A	20
Hash Map Key	N/A	N/A	N/A	N/A	N/A	'b'	'b'	'b'
Lookup Result	None	None	Found at index 1	None	Found node	None	Found value	Found 20 in all

Key Moments - 3 Insights

Why does array lookup check each index one by one?

Because arrays do not have keys, we must check each element until we find the value or reach the end (see steps 1 and 2).

Why does linked list lookup need to move node by node?

Linked lists store elements in nodes linked by pointers, so we must follow each 'next' pointer to check values (see steps 4 and 5).

How does hash map find the value so quickly?

Hash maps use a hash function to directly compute the location of the key, so they access the value immediately without searching (see steps 7 and 8).

Visual Quiz - 3 Questions

Look at the execution table, at which step does the array find the value 20?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Check the 'Result' column for the array rows in steps 1-3.

At which step does the linked list move to the node with value 20?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at the 'Operation' and 'Details' columns for linked list steps.

If the hash map key was 'a' instead of 'b', which step would change?

A Step 9

B Step 8

C Step 7

D Step 10

💡 Hint

Step 7 shows the hash key used for computing the hash.

Concept Snapshot

Lookup in Array: Check each element one by one until found or end.
Lookup in Linked List: Traverse nodes from head, checking each value.
Lookup in Hash Map: Compute hash of key, access value directly.
Hash Map is fastest for lookup, Array and Linked List are slower.
Use Hash Map for quick key-value access, Array for indexed data, Linked List for dynamic insertion.

Full Transcript

This visual execution compares lookup operations in three data structures: array, linked list, and hash map. Lookup starts by choosing the data structure. For arrays, it checks each index sequentially until the value is found or the end is reached. For linked lists, it traverses nodes starting from the head, following next pointers and checking values. For hash maps, it computes a hash for the key and accesses the value directly without searching. The execution table shows each step, operation, and the state of the data structure. Variable tracking shows how indexes, current nodes, keys, and results change over time. Key moments clarify why arrays and linked lists require sequential checks, while hash maps provide direct access. The quiz tests understanding of when values are found and how hash keys affect lookup. The snapshot summarizes the lookup behavior and performance differences among these data structures.

Practice

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

easy

A. Hash Map

B. Array

C. Linked List

D. Stack

Solution

1. Step 1: Understand lookup times for each data structure

   Hash Maps use keys to directly access values, giving average O(1) time. Arrays require scanning or index access, O(n) or O(1) if index known. Linked Lists require scanning, O(n).

2. Step 2: Compare average lookup speeds

   Hash Map is fastest for key-based lookup because it uses hashing. Arrays and Linked Lists are slower for key lookup.

3. Final Answer:

   Hash Map -> Option A

4. Quick Check:

   Fastest lookup by key = Hash Map [OK]

Hint: Hash Map uses keys for O(1) lookup, arrays and lists do not [OK]

Common Mistakes:

• Thinking arrays are always fastest because of index access
• Confusing linked list traversal with direct access
• Assuming stack is a lookup structure

2. Which of the following is the correct way to check if a key exists in a JavaScript Map?

easy

A. map.includes(key)

B. key in map

C. map.contains(key)

D. map.has(key)

Solution

1. Step 1: Recall JavaScript Map methods

   JavaScript Map has a method called has() to check if a key exists.

2. Step 2: Evaluate each option

   map.has(key) uses map.has(key) which is correct. 'key in map' works for objects, not Map. 'contains' and 'includes' are not Map methods.

3. Final Answer:

   map.has(key) -> Option D

4. Quick Check:

   Check key in Map = map.has(key) [OK]

Hint: Use map.has(key) to check keys in JavaScript Map [OK]

Common Mistakes:

• Using 'in' operator on Map instead of Object
• Using non-existent methods like contains or includes on Map
• Confusing array methods with Map methods

3. What will be the output of the following code?

const arr = [10, 20, 30, 40];
const map = new Map();
map.set('a', 1);
map.set('b', 2);

console.log(arr.indexOf(30));
console.log(map.has('b'));
console.log(map.get('c'));

medium

A. 2 true null

B. -1 false undefined

C. 2 true undefined

D. 3 true undefined

Solution

1. Step 1: Analyze array indexOf(30)

   Array arr is [10,20,30,40]. indexOf(30) returns 2 because 30 is at index 2.

2. Step 2: Check map.has('b') and map.get('c')

   map.has('b') is true because 'b' exists. map.get('c') returns undefined because 'c' key does not exist.

3. Final Answer:

   2 true undefined -> Option C

4. Quick Check:

   indexOf(30)=2, has('b')=true, get('c')=undefined [OK]

Hint: indexOf returns index or -1; Map.get returns undefined if key missing [OK]

Common Mistakes:

• Assuming map.get returns null for missing keys
• Confusing array index with value
• Thinking map.has returns value instead of boolean

4. The following code tries to find if a value exists in a linked list. What is the bug?

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function contains(head, target) {
  if (head === null) return false;
  while (head.next !== null) {
    if (head.value === target) return true;
    head = head.next;
  }
  return false;
}

medium

A. It misses checking the last node's value

B. It causes infinite loop

C. It throws an error on empty list

D. It incorrectly compares values

Solution

1. Step 1: Understand the loop condition

   The loop runs while head.next !== null, so it stops before the last node.

2. Step 2: Check if last node is checked

   Because loop stops before last node, last node's value is never checked, so target in last node is missed.

3. Final Answer:

   It misses checking the last node's value -> Option A

4. Quick Check:

   Loop condition excludes last node check [OK]

Hint: Loop until node is null, not node.next [OK]

Common Mistakes:

• Using head.next !== null instead of head !== null
• Assuming last node is checked inside loop

5. You need to frequently check if a user ID exists and also maintain the order of insertion. Which data structure is best suited for this in JavaScript?

hard

A. Array

B. Map

C. Linked List

D. Set

Solution

1. Step 1: Understand requirements

   We need fast existence check and order preservation of user IDs.

2. Step 2: Compare data structures

   Array preserves order but slow lookup (O(n)). Linked List preserves order but slow lookup (O(n)). Map preserves order and fast lookup by key and stores key-value pairs. Set preserves insertion order and fast lookup for unique values but does not store key-value pairs.

3. Step 3: Choose best fit

   Map stores key-value pairs, preserves insertion order, and offers O(1) lookup, making it ideal for checking existence and maintaining order.

4. Final Answer:

   Map -> Option B

5. Quick Check:

   Fast lookup + order + key-value = Map [OK]

Hint: Use Map for key-value pairs with order and fast lookup [OK]

Common Mistakes:

• Choosing Set when key-value pairs are needed
• Using Array and expecting fast lookup
• Confusing Linked List order with lookup speed