Hash Map vs Array vs Linked List for Lookup in DSA Javascript - Trade-offs & Analysis

Mental Model

We want to find a value quickly by searching through different data structures. Each structure organizes data differently, affecting how fast we find things.

Analogy: Imagine looking for a book in a library: an array is like a shelf with books in order, a linked list is like a chain of books you check one by one, and a hash map is like a librarian who knows exactly where each book is.

Array: [1] -> [2] -> [3] -> [4] -> null
Linked List: 1 -> 2 -> 3 -> 4 -> null
Hash Map: {key1: value1, key2: value2, key3: value3}

Dry Run Walkthrough

Input: Data: [10, 20, 30, 40], Search for 30

Goal: Compare how each structure finds the value 30

Step 1: Start searching in Array from index 0

[10] -> [20] -> [30] -> [40] -> null, current index = 0

Why: We check each element in order to find 30

Step 2: Check index 0: value 10 is not 30, move to index 1

[10] -> [20] -> [30] -> [40] -> null, current index = 1

Why: Keep searching until we find 30

Step 3: Check index 1: value 20 is not 30, move to index 2

[10] -> [20] -> [30] -> [40] -> null, current index = 2

Why: Keep searching until we find 30

Step 4: Check index 2: value 30 found, stop search

[10] -> [20] -> [30] -> [40] -> null, current index = 2

Why: Found the value 30

Step 5: Start searching in Linked List from head node

10 -> 20 -> 30 -> 40 -> null, current node = 10

Why: We check nodes one by one to find 30

Step 6: Check node 10: not 30, move to next node 20

10 -> 20 -> 30 -> 40 -> null, current node = 20

Why: Keep searching until we find 30

Step 7: Check node 20: not 30, move to next node 30

10 -> 20 -> 30 -> 40 -> null, current node = 30

Why: Keep searching until we find 30

Step 8: Check node 30: found 30, stop search

10 -> 20 -> 30 -> 40 -> null, current node = 30

Why: Found the value 30

Step 9: Search in Hash Map using key '30'

{10: true, 20: true, 30: true, 40: true}, lookup key = 30

Why: Hash map directly finds value by key

Step 10: Value 30 found immediately by hash map

{10: true, 20: true, 30: true, 40: true}, lookup key = 30

Why: Hash map gives direct access without searching

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: {10: true, 20: true, 30: true, 40: true}, found 30 immediately

Annotated Code

DSA Javascript

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

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let curr = this.head;
    while (curr.next) {
      curr = curr.next; // advance curr to next node
    }
    curr.next = newNode; // add new node at end
  }

  search(value) {
    let curr = this.head;
    while (curr) {
      if (curr.value === value) {
        return true; // found value
      }
      curr = curr.next; // move to next node
    }
    return false; // not found
  }
}

function arraySearch(arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return true; // found value
    }
  }
  return false; // not found
}

function hashMapSearch(map, key) {
  return Object.prototype.hasOwnProperty.call(map, key); // direct lookup
}

// Driver code
const arr = [10, 20, 30, 40];
const list = new LinkedList();
for (const val of arr) {
  list.append(val);
}
const map = {10: true, 20: true, 30: true, 40: true};

console.log('Array search for 30:', arraySearch(arr, 30));
console.log('Linked List search for 30:', list.search(30));
console.log('Hash Map search for 30:', hashMapSearch(map, 30));

curr = curr.next; // advance curr to next node

advance curr to next node -- keeps traversing until we reach tail

curr.next = newNode; // add new node at end

attach new node at the end of linked list

if (curr.value === value) { return true; }

check if current node has the searched value

for (let i = 0; i < arr.length; i++) { if (arr[i] === value) { return true; } }

iterate array elements to find the value

return Object.prototype.hasOwnProperty.call(map, key);

directly check if key exists in hash map

Output

Array search for 30: true

Linked List search for 30: true

Hash Map search for 30: true

Complexity Analysis

Time: Array and Linked List search: O(n) because they check elements one by one; Hash Map search: O(1) because it directly accesses the value by key

Space: Array and Linked List use O(n) space to store n elements; Hash Map uses O(n) space plus extra for hashing

vs Alternative: Hash Map is faster for lookup than Array or Linked List but uses more memory and needs hashing; Array is simple but slower; Linked List is slowest for lookup

Edge Cases

Empty array, linked list, or hash map

Search returns false immediately as no elements exist

DSA Javascript

while (curr) { ... } in LinkedList.search handles empty list by skipping loop

Value not present in data structure

Search completes full traversal or lookup and returns false

DSA Javascript

return false after loop in arraySearch and LinkedList.search

Duplicate values in array or linked list

Search returns true on first found occurrence

DSA Javascript

if (arr[i] === value) { return true; } and if (curr.value === value) { return true; }

When to Use This Pattern

When you need to find if a value exists quickly, consider if direct access (hash map) is possible; if not, linear search in array or linked list is needed.

Common Mistakes

Mistake: Assuming linked list lookup is as fast as hash map
Fix: Remember linked list lookup is linear time, hash map is constant time

Mistake: Using array search without stopping after finding the value
Fix: Return immediately when value is found to avoid unnecessary checks

Summary

Compares how fast we can find a value in hash map, array, and linked list.

Use hash map for fastest lookup if keys are known; use array or linked list when order or simple structure is needed.

Hash map gives direct access by key, arrays and linked lists require checking elements one by one.

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