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

Mental Model

Lookup means finding a value quickly. Different structures find values in different speeds.

Analogy: Imagine looking for a book in a library: an array is like checking every book shelf in order, a linked list is like following a chain of people each holding one book, and a hash map is like using a special code to jump directly to the book's shelf.

Array: [1] -> [2] -> [3] -> [4] -> null
Linked List: 1 -> 2 -> 3 -> 4 -> null
Hash Map: {key1: val1, key2: val2, key3: val3}

Dry Run Walkthrough

Input: Find value 3 in structures: Array [1,2,3,4], Linked List 1->2->3->4, Hash Map {1:1, 2:2, 3:3, 4:4}

Goal: Show how each structure finds value 3 and how many steps it takes

Step 1: Check first element in array

Array: [1] -> [2] -> [3] -> [4] -> null

Why: Start from beginning to find 3

Step 2: Check second element in array

Array: [1] -> [2] -> [3] -> [4] -> null

Why: 3 not found yet, move to next

Step 3: Check third element in array, found 3

Array: [1] -> [2] -> [3] -> [4] -> null

Why: Found value 3 at index 2

Step 4: Start at head of linked list

Linked List: 1 -> 2 -> 3 -> 4 -> null ↑

Why: Begin search from first node

Step 5: Move to second node, value 2

Linked List: 1 -> 2 -> 3 -> 4 -> null ↑

Why: 3 not found, move forward

Step 6: Move to third node, found 3

Linked List: 1 -> 2 -> 3 -> 4 -> null ↑

Why: Found value 3 at third node

Step 7: Use hash function to find key 3 directly

Hash Map: {1:1, 2:2, 3:3, 4:4}

Why: Hash map jumps directly to value 3

Result:

Array: found 3 after checking 3 elements
Linked List: found 3 after visiting 3 nodes
Hash Map: found 3 immediately using key

Annotated Code

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let curr = this.head;
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = newNode;
  }

  lookup(value: number): boolean {
    let curr = this.head;
    while (curr) {
      if (curr.value === value) {
        return true;
      }
      curr = curr.next; // advance curr to next node
    }
    return false;
  }
}

function arrayLookup(arr: number[], value: number): boolean {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return true;
    }
  }
  return false;
}

function hashMapLookup(map: Map<number, number>, key: number): boolean {
  return map.has(key); // direct key check
}

// Driver code
const arr = [1, 2, 3, 4];
const list = new LinkedList();
arr.forEach(v => list.append(v));
const map = new Map<number, number>();
arr.forEach(v => map.set(v, v));

const valueToFind = 3;
console.log('Array lookup:', arrayLookup(arr, valueToFind));
console.log('Linked List lookup:', list.lookup(valueToFind));
console.log('Hash Map lookup:', hashMapLookup(map, valueToFind));

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

advance curr to next node -- keeps traversing until value found or end

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

check each array element for value

return map.has(key); // direct key check

directly check if key exists in hash map

Output

Array lookup: true

Linked List lookup: true

Hash Map lookup: true

Complexity Analysis

Time: Array and Linked List lookup: O(n) because they check elements one by one; Hash Map lookup: O(1) average because it jumps directly to the key

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

vs Alternative: Hash Map is faster for lookup than Array or Linked List but uses more memory and needs hashing; Array is simple and fast for index access but slow for lookup; Linked List is slowest for lookup because it must check nodes one by one

Edge Cases

Empty array, linked list, and hash map

Lookup returns false immediately because no elements exist

DSA Typescript

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

Value not present in structures

Lookup returns false after checking all elements or keys

DSA Typescript

return false at end of arrayLookup and LinkedList.lookup functions

Single element structures

Lookup returns true if value matches the single element, else false

DSA Typescript

if (arr[i] === value) and if (curr.value === value) handle single element check

When to Use This Pattern

When a problem asks for fast lookup by key or value, consider hash maps for O(1) average time; if order matters or memory is tight, arrays or linked lists may be used but with slower lookup.

Common Mistakes

Mistake: Trying to find a value in a linked list by index instead of by traversing nodes
Fix: Traverse nodes one by one checking each node's value until found or end

Mistake: Assuming array lookup by value is O(1) like index access
Fix: Remember array lookup by value requires scanning elements, so O(n)

Mistake: Using hash map without checking if key exists before accessing
Fix: Use map.has(key) to check existence before accessing value

Summary

Compares how fast we can find a value in hash maps, arrays, and linked lists.

Use hash maps for fast lookup by key; arrays or linked lists when order or simple structure is needed.

Hash maps jump directly to keys, arrays and linked lists check elements one by one.

Practice

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

easy

A. Stack

B. Hash Map

C. Linked List

D. Array

Solution

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

   Hash Map uses hashing to find keys quickly, usually in constant time O(1). Arrays require scanning or index access, O(1) if index known but O(n) if searching by value. Linked Lists require scanning nodes, O(n).

2. Step 2: Compare average lookup times

   Hash Map is fastest on average for key lookup, Arrays and Linked Lists are slower for searching by value.

3. Final Answer:

   Hash Map -> Option B

4. Quick Check:

   Hash Map lookup = fastest [OK]

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

Common Mistakes:

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

2. Which of the following is the correct TypeScript syntax to declare a Hash Map with string keys and number values?

easy

A. const map: Array = [];

B. const map: Object = new Object();

C. const map: LinkedList = new LinkedList();

D. const map: Map = new Map();

Solution

1. Step 1: Identify correct TypeScript Map syntax

   TypeScript uses Map to declare a hash map with key type K and value type V.

2. Step 2: Check each option

   const map: Map = new Map(); correctly declares a Map with string keys and number values. const map: Array = []; uses Array incorrectly. const map: LinkedList = new LinkedList(); uses LinkedList which is not a built-in type. const map: Object = new Object(); uses Object but without type parameters.

3. Final Answer:

   const map: Map = new Map(); -> Option D

4. Quick Check:

   Map syntax = correct [OK]

Hint: Use Map for hash maps in TypeScript [OK]

Common Mistakes:

• Using Array syntax for key-value pairs
• Assuming Object is typed like Map
• Confusing LinkedList with Map

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

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

console.log(arr.includes(20));
console.log(map.has(2));
console.log(map.get(3));

medium

A. true\nfalse\nundefined

B. false\ntrue\nnull

C. true\ntrue\nundefined

D. false\nfalse\nnull

Solution

1. Step 1: Evaluate arr.includes(20)

   Array contains 20, so arr.includes(20) returns true.

2. Step 2: Evaluate map.has(2) and map.get(3)

   map.has(2) is true because key 2 exists. map.get(3) returns undefined because key 3 does not exist.

3. Final Answer:

   true\ntrue\nundefined -> Option C

4. Quick Check:

   Array includes 20 = true, Map has 2 = true, Map get 3 = undefined [OK]

Hint: Array.includes checks values, Map.has checks keys [OK]

Common Mistakes:

• Confusing Map.get missing key return value
• Assuming Array.includes returns index
• Mixing up true/false for Map.has

4. Identify the bug in this TypeScript code that tries to find a value in a linked list:

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

class LinkedList {
  head: Node | null = null;
  find(value: number): boolean {
    let current = this.head;
    while (current !== null) {
      if (current.value === value) {
        return true;
      }
      current = this.head;
    }
    return false;
  }
}

medium

A. Inside the loop, current is reset to head instead of moving to next node

B. The constructor does not initialize next properly

C. The find method should return the node, not boolean

D. The head property should be private

Solution

1. Step 1: Analyze the while loop in find method

   The loop sets current = this.head every iteration, causing an infinite loop at the head node.

2. Step 2: Identify correct pointer update

   Instead of resetting to head, current should move to current.next to traverse the list.

3. Final Answer:

   Inside the loop, current is reset to head instead of moving to next node -> Option A

4. Quick Check:

   Loop must advance current = current.next [OK]

Hint: In linked list traversal, always move to current.next [OK]

Common Mistakes:

• Resetting current to head inside loop
• Not updating current pointer
• Confusing return types

5. You need to store a large collection of user IDs and quickly check if a user ID exists. Which data structure is best and why?

Consider:
- Array of user IDs
- Linked List of user IDs
- Hash Map with user ID keys and boolean values

hard

A. Hash Map, because it provides average O(1) lookup time for existence checks

B. Linked List, because it allows easy insertion and deletion

C. Array, because it uses less memory and lookup is fast with index

D. Linked List, because it preserves insertion order

Solution

1. Step 1: Evaluate lookup efficiency for existence check

   Array and Linked List require scanning elements, O(n) time. Hash Map uses hashing for O(1) average lookup.

2. Step 2: Consider memory and operation needs

   Hash Map uses more memory but is best for fast existence checks. Arrays and lists are slower for lookup.

3. Step 3: Choose best data structure for fast lookup

   Hash Map is best for quick user ID existence checks due to constant time lookup.

4. Final Answer:

   Hash Map, because it provides average O(1) lookup time for existence checks -> Option A

5. Quick Check:

   Fast existence check = Hash Map [OK]

Hint: For fast existence checks, use Hash Map O(1) lookup [OK]

Common Mistakes:

• Choosing array for fast lookup without index
• Ignoring lookup time complexity
• Confusing insertion order with lookup speed