Hash Map vs Array vs Linked List for Lookup in DSA Javascript - Key Differences

Recall & Review

beginner

What is the average time complexity for lookup in a Hash Map?

The average time complexity for lookup in a Hash Map is O(1), meaning it can find an item very quickly regardless of the size of the data.

beginner

How does lookup in an Array work when searching for a value without knowing the index?

Lookup in an Array without knowing the index requires checking each element one by one, leading to O(n) time complexity, where n is the number of elements.

beginner

Why is lookup in a Linked List slower than in a Hash Map?

Lookup in a Linked List is slower because it requires checking each node from the start until the target is found, resulting in O(n) time complexity.

beginner

Which data structure is best for fast lookup by key: Hash Map, Array, or Linked List?

Hash Map is best for fast lookup by key because it uses a hashing function to directly access the data, making lookup O(1) on average.

beginner

What is a real-life example to understand why Hash Maps are faster for lookup than Arrays or Linked Lists?

Think of a Hash Map like a phone book where you can directly jump to a person's page using their name, while an Array or Linked List is like searching through a list of names one by one.

What is the average time complexity of lookup in a Hash Map?

A O(n)

B O(log n)

C O(1)

D O(n^2)

Hash Maps provide average O(1) lookup time by using a hashing function to directly access data.

If you want to find a value in an Array without knowing the index, what is the time complexity?

A O(n)

B O(1)

C O(log n)

D O(n log n)

You must check each element one by one, so the time complexity is O(n).

Which data structure requires traversing nodes one by one to find a value?

A Linked List

B Array

C Hash Map

D Binary Search Tree

Linked Lists require checking each node sequentially, leading to O(n) lookup time.

Which data structure is best for fast key-based lookup?

A Array

B Linked List

C Stack

D Hash Map

Hash Maps use hashing to access data quickly, making them best for key-based lookup.

Why is lookup in an Array slower than in a Hash Map when the index is unknown?

A Because Arrays are unordered

B Because you must check each element one by one

C Because Arrays use hashing

D Because Arrays have linked nodes

Without the index, you must scan each element, making lookup O(n).

Explain the difference in lookup speed between Hash Maps, Arrays, and Linked Lists.

Think about how each data structure finds data.

Describe a real-life analogy to understand why Hash Maps are faster than Arrays or Linked Lists for lookup.

Imagine looking up a name in a phone book versus a list.

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