Hash Map vs Array vs Linked List for Lookup in DSA Javascript - Build Both Approaches

Hash Map vs Array vs Linked List for Lookup

📖 Scenario: Imagine you run a small library. You want to find books quickly by their ID number. You have three ways to store books: an array, a linked list, and a hash map. Each way lets you look up a book by its ID, but some are faster than others.

🎯 Goal: You will create three data structures: an array, a linked list, and a hash map, each holding the same books. Then you will write code to find a book by its ID in each structure and print the found book's title. This will help you see which way is faster and easier for lookup.

📋 What You'll Learn

Create an array called booksArray with 3 book objects having id and title.

Create a linked list called booksLinkedList with the same 3 books as nodes.

Create a hash map called booksHashMap with book IDs as keys and titles as values.

Create a variable searchId set to 2 to find the book with ID 2.

Write code to find the book with searchId in each data structure.

Print the found book's title from each data structure.

💡 Why This Matters

🌍 Real World

Libraries, stores, and apps often need to find items quickly by ID. Choosing the right data structure helps make searches fast and efficient.

💼 Career

Understanding arrays, linked lists, and hash maps is key for software developers to write efficient code for data storage and retrieval.

1

Create the books array

Create an array called booksArray with these exact book objects: {id: 1, title: 'The Hobbit'}, {id: 2, title: '1984'}, {id: 3, title: 'Brave New World'}.

DSA Javascript

// Create the booksArray with 3 book objects
// Your code here

Hint

Use square brackets [] to create an array. Each book is an object with id and title.

2

Create the linked list for books

Create a linked list called booksLinkedList with nodes holding the same 3 books. Define a Node class with data and next. Then create nodes for each book and link them in order.

DSA Javascript

const booksArray = [
  {id: 1, title: 'The Hobbit'},
  {id: 2, title: '1984'},
  {id: 3, title: 'Brave New World'}
];

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

let booksLinkedList = null;
// Create nodes for each book and link them
// Your code here

Hint

Create a Node class. Then create the first node as head and link the next nodes using next.

3

Create the books hash map

Create a hash map called booksHashMap where keys are book IDs and values are book titles. Use these exact entries: 1: 'The Hobbit', 2: '1984', 3: 'Brave New World'.

DSA Javascript

const booksArray = [
  {id: 1, title: 'The Hobbit'},
  {id: 2, title: '1984'},
  {id: 3, title: 'Brave New World'}
];

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

let booksLinkedList = new Node({id: 1, title: 'The Hobbit'});
booksLinkedList.next = new Node({id: 2, title: '1984'});
booksLinkedList.next.next = new Node({id: 3, title: 'Brave New World'});

// Create booksHashMap with IDs as keys and titles as values
// Your code here

Hint

Use curly braces {} to create an object. Keys are numbers and values are strings.

4

Find and print book titles by ID in all structures

Create a variable searchId set to 2. Then find the book with searchId in booksArray using a for loop, in booksLinkedList by traversing nodes, and in booksHashMap by key lookup. Print the found book titles from each data structure exactly as shown.

DSA Javascript

const booksArray = [
  {id: 1, title: 'The Hobbit'},
  {id: 2, title: '1984'},
  {id: 3, title: 'Brave New World'}
];

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

let booksLinkedList = new Node({id: 1, title: 'The Hobbit'});
booksLinkedList.next = new Node({id: 2, title: '1984'});
booksLinkedList.next.next = new Node({id: 3, title: 'Brave New World'});

const booksHashMap = {
  1: 'The Hobbit',
  2: '1984',
  3: 'Brave New World'
};

// Find and print book titles by searchId in all structures
// Your code here

Hint

Use a for loop to find the book in the array. Use a while loop to traverse the linked list. Use direct key access for the hash map. Print results with console.log.

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