Hash Map vs Array vs Linked List for Lookup in DSA Javascript - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Lookup Time Complexity in Different Data Structures

Consider the following JavaScript code snippets that perform lookup operations. Which option correctly shows the output time complexity for each data structure?

DSA Javascript

const array = [1, 2, 3, 4, 5];
const linkedList = { head: { value: 1, next: { value: 2, next: null } } };
const hashMap = new Map([[1, 'a'], [2, 'b'], [3, 'c']]);

A Array: O(n), Linked List: O(n), Hash Map: O(1)

B Array: O(1), Linked List: O(1), Hash Map: O(n)

C Array: O(n), Linked List: O(1), Hash Map: O(n)

D Array: O(1), Linked List: O(n), Hash Map: O(1)

💡 Hint

Think about how each data structure stores and accesses elements.

Arrays and linked lists require scanning elements for lookup, so they take O(n) time. Hash maps use keys to directly access values, so lookup is O(1).

🧠 Conceptual

intermediate

Best Data Structure for Fast Lookup by Key

Which data structure is best suited for fast lookup by a unique key in JavaScript?

A Linked List

B Array

C Hash Map

D Stack

💡 Hint

Consider which structure uses keys to access values directly.

Hash maps store key-value pairs and allow direct access by key, making lookup very fast.

❓ Predict Output

advanced

Output of Lookup in Linked List vs Array

What will be the output of the following JavaScript code?

DSA Javascript

const array = [10, 20, 30, 40];
const linkedList = { value: 10, next: { value: 20, next: { value: 30, next: null } } };

function lookupArray(arr, target) {
  return arr.includes(target);
}

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

console.log(lookupArray(array, 30));
console.log(lookupLinkedList(linkedList, 40));

A false\ntrue

B true\nfalse

C true\ntrue

D false\nfalse

💡 Hint

Check if the target exists in each data structure.

The array contains 30, so lookupArray returns true. The linked list does not contain 40, so lookupLinkedList returns false.

🔧 Debug

advanced

Identify the Error in Hash Map Lookup Code

What error will the following JavaScript code produce when trying to lookup a key in a hash map?

DSA Javascript

const hashMap = new Map([[1, 'one'], [2, 'two']]);

function getValue(key) {
  return hashMap[key];
}

console.log(getValue(1));

A Returns 'one'

B TypeError

C ReferenceError

D undefined

💡 Hint

How do you access values in a Map object?

Using bracket notation on a Map returns undefined because Map requires the get() method for lookup.

🧠 Conceptual

expert

Why Linked List Lookup is Slower than Hash Map Lookup

Why is lookup in a linked list generally slower than lookup in a hash map?

A Linked list stores elements sequentially and requires traversal; hash map uses hashing for direct access.

B Linked list uses hashing internally; hash map uses sequential search.

C Linked list lookup is faster because it uses pointers; hash map lookup requires scanning all keys.

D Linked list stores elements in a tree structure; hash map stores elements in an array.

💡 Hint

Think about how each data structure finds an element.

Linked lists require checking each node one by one, which takes longer. Hash maps use a hash function to jump directly to the element.

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