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

Mental Model

Lookup means finding if a value exists or getting its associated data quickly. Different structures organize data differently, affecting how fast we find things.

Analogy: Imagine looking for a book in a library: an array is like a shelf where you check each book one by one; a linked list is like a chain of books where you follow links from one to the next; a hash map is like a special index that tells you exactly where the book is.

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

Dry Run Walkthrough

Input: list: 1->2->3, lookup value 2

Goal: Compare how fast we find value 2 in array, linked list, and hash map

Step 1: Check first element in array (index 0)

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

Why: We start from the beginning because arrays have no shortcuts

Step 2: Value 1 is not 2, move to index 1

Array: [0]1 -> [1][curr->2] -> [2]3 -> null

Why: We keep checking each element until we find 2

Step 3: Found value 2 at index 1 in array

Array: [0]1 -> [1][found->2] -> [2]3 -> null

Why: Lookup successful after 2 checks

Step 4: Start at head of linked list

Linked List: [head->1] -> 2 -> 3 -> null

Why: Linked list requires traversal from head

Step 5: Value 1 is not 2, move to next node

Linked List: 1 -> [curr->2] -> 3 -> null

Why: We follow links one by one

Step 6: Found value 2 in linked list

Linked List: 1 -> [found->2] -> 3 -> null

Why: Lookup successful after 2 steps

Step 7: Use hash function on key 2 to find bucket

Hash Map: {2: value} (direct access)

Why: Hash map uses key to jump directly to value

Step 8: Found value 2 immediately in hash map

Hash Map: {2: value} (found)

Why: Lookup is very fast, usually one step

Result:

Array: [0]1 -> [1][found->2] -> [2]3 -> null
Linked List: 1 -> [found->2] -> 3 -> null
Hash Map: {2: value} (found immediately)

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        if not self.head:
            self.head = Node(val)
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = Node(val)

    def lookup(self, val):
        curr = self.head
        while curr:
            if curr.val == val:
                return True
            curr = curr.next
        return False

class Array:
    def __init__(self, vals):
        self.arr = vals

    def lookup(self, val):
        for item in self.arr:
            if item == val:
                return True
        return False

class HashMap:
    def __init__(self):
        self.map = {}

    def insert(self, key, value):
        self.map[key] = value

    def lookup(self, key):
        return key in self.map

# Driver code
# Setup array
array = Array([1, 2, 3])
# Setup linked list
ll = LinkedList()
for v in [1, 2, 3]:
    ll.append(v)
# Setup hash map
hm = HashMap()
for v in [1, 2, 3]:
    hm.insert(v, f"Value{v}")

# Lookup value 2
print("Array lookup 2:", array.lookup(2))
print("Linked List lookup 2:", ll.lookup(2))
print("Hash Map lookup 2:", hm.lookup(2))

while curr:

traverse linked list nodes one by one

if curr.val == val:

check if current node value matches lookup value

for item in self.arr:

iterate over array elements sequentially

if item == val:

compare each array element to lookup value

self.map[key] = value

store key-value pair in hash map

return key in self.map

check if key exists in hash map directly

Output

Array lookup 2: True

Linked List lookup 2: True

Hash Map lookup 2: 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 structure

vs Alternative: Hash Map is faster for lookup than Array or Linked List but uses more memory and needs hashing; Array is simple but slow for large data; Linked List is slowest for lookup due to pointer traversal

Edge Cases

Empty data structures

Lookup returns False immediately because no elements exist

DSA Python

while curr:

Value not present in data structures

Lookup traverses all elements and returns False

DSA Python

return False

Single element data structure with matching value

Lookup finds value immediately and returns True

DSA Python

if curr.val == val:

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: Assuming linked list lookup is O(1) like hash map
Fix: Remember linked list lookup requires checking each node sequentially, so it is O(n)

Mistake: Using array index as key in hash map without hashing
Fix: Use a proper hash function or dictionary key to get O(1) lookup

Summary

Compares lookup speed of hash map, array, and linked list data structures.

Use hash maps for fast key-based lookup; arrays or linked lists for simple or ordered data.

Hash maps jump directly to data using 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. Hash Map

B. Array

C. Linked List

D. Stack

Solution

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

   Hash Map uses a hash function 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 due to direct hashing. Arrays and Linked Lists are slower for searching by value.

3. Final Answer:

   Hash Map -> Option A

4. Quick Check:

   Fastest lookup = Hash Map [OK]

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

Common Mistakes:

• Confusing array index access with value lookup
• Thinking linked list lookup is fast
• Assuming stack is a lookup structure

2. Which of the following is the correct syntax to create an empty hash map (dictionary) in Python?

easy

A. hash_map = {}

B. hash_map = ()

C. hash_map = []

D. hash_map = set()

Solution

1. Step 1: Recall Python syntax for empty data structures

   Empty list uses [], empty tuple uses (), empty dictionary uses {}, and empty set uses set().

2. Step 2: Identify the hash map syntax

   Hash map in Python is a dictionary, created with {}.

3. Final Answer:

   hash_map = {} -> Option A

4. Quick Check:

   Empty dict = {} [OK]

Hint: Use curly braces {} for empty dictionary in Python [OK]

Common Mistakes:

• Using [] which creates a list, not a dictionary
• Using () which creates a tuple
• Using set() which creates a set, not a dictionary

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

arr = [10, 20, 30, 40]
lookup = {val: idx for idx, val in enumerate(arr)}
print(lookup.get(30))
print(lookup.get(50, -1))

medium

A. 30\n50

B. 3\n-1

C. 2\n-1

D. null\n-1

Solution

1. Step 1: Understand dictionary comprehension and get method

   The dictionary 'lookup' maps values to their indices: {10:0, 20:1, 30:2, 40:3}. lookup.get(30) returns the index for 30, which is 2. lookup.get(50, -1) looks for 50, not found, returns default -1.

2. Step 2: Determine printed output

   First print outputs 2. Second print outputs -1.

3. Final Answer:

   2 -1 -> Option C

4. Quick Check:

   lookup[30] = 2, missing key returns -1 [OK]

Hint: Dictionary get returns default if key missing [OK]

Common Mistakes:

• Confusing keys and values in dictionary
• Expecting get to raise error if key missing
• Mixing index and value in output

4. The following code tries to find if a value exists in a linked list. What is the bug?

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def find(head, target):
    current = head
    while current.next is not None:
        if current.val == target:
            return True
        current = current.next
    return False

medium

A. The function should use recursion instead of a loop

B. The loop condition should be 'while current is not None' to check last node

C. The Node class is missing a previous pointer

D. The function should return false inside the loop

Solution

1. Step 1: Analyze loop condition in linked list traversal

   The loop uses 'while current.next is not None', so it stops before last node. This means the last node's value is never checked.

2. Step 2: Correct loop condition to include last node

   Changing to 'while current is not None' ensures all nodes, including last, are checked for target value.

3. Final Answer:

   The loop condition should be 'while current is not None' to check last node -> Option B

4. Quick Check:

   Loop must check all nodes including last [OK]

Hint: Check loop condition includes last node (current is not None) [OK]

Common Mistakes:

• Stopping loop early missing last node
• Adding unnecessary previous pointer
• Thinking recursion is required

5. You have a large dataset of unique user IDs and want to check membership quickly. Which data structure is best and why? A) Array because it stores elements sequentially B) Linked List because it allows easy insertion C) Hash Map because it provides average O(1) lookup D) Stack because it supports last-in-first-out access

hard

A. Array because it stores elements sequentially

B. Linked List because it allows easy insertion

C. Stack because it supports last-in-first-out access

D. Hash Map because it provides average O(1) lookup

Solution

1. Step 1: Understand lookup needs for large dataset

   Checking membership means quickly finding if an element exists. Arrays and linked lists require scanning, O(n) time. Stacks are not designed for membership lookup.

2. Step 2: Identify best data structure for fast membership

   Hash Map uses hashing to find elements in average O(1) time, ideal for large datasets and membership checks.

3. Final Answer:

   Hash Map because it provides average O(1) lookup -> Option D

4. Quick Check:

   Fast membership = Hash Map [OK]

Hint: Use hash map for fast membership checks in large data [OK]

Common Mistakes:

• Choosing array or list for fast lookup
• Confusing insertion speed with lookup speed
• Thinking stack supports membership lookup