Hash Map vs Array vs Linked List for Lookup in DSA Python - 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 numbers. You have three ways to store the books: a list (array), a linked list, and a hash map (dictionary). Each way works differently when you look for a book.

🎯 Goal: You will create three data structures to store book IDs and then write code to find a specific book ID in each structure. This will help you see which way is fastest for looking up books.

📋 What You'll Learn

Create a list called book_list with book IDs 101, 102, 103, 104, 105

Create a linked list with nodes holding book IDs 101, 102, 103, 104, 105

Create a dictionary called book_map with keys as book IDs and values as book names

Write a function find_in_list(book_list, target) to find target in book_list

Write a function find_in_linked_list(head, target) to find target in the linked list

Write a function find_in_map(book_map, target) to find target in book_map

Print the results of looking for book ID 103 in all three data structures

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding how different data structures work for lookup is important for software developers, data engineers, and anyone working with data storage and retrieval.

1

Create the data structures for books

Create a list called book_list with these exact book IDs: 101, 102, 103, 104, 105. Then create a dictionary called book_map with these exact entries: 101: 'Book A', 102: 'Book B', 103: 'Book C', 104: 'Book D', 105: 'Book E'.

DSA Python

# Create book_list and book_map with given values
# Your code here

Hint

Use square brackets [] for the list and curly braces {} for the dictionary.

2

Create a linked list for the books

Define a class called Node with attributes data and next. Then create linked list nodes for book IDs 101, 102, 103, 104, 105 linked in order. Assign the first node to a variable called head.

DSA Python

book_list = [101, 102, 103, 104, 105]
book_map = {101: 'Book A', 102: 'Book B', 103: 'Book C', 104: 'Book D', 105: 'Book E'}

# Define Node class and create linked list with head
# Your code here

Hint

Each node holds a book ID and a link to the next node. Link nodes in order from 101 to 105.

3

Write functions to find a book ID in each data structure

Write a function find_in_list(book_list, target) that returns True if target is in book_list, else False. Write a function find_in_linked_list(head, target) that returns True if target is found in the linked list starting at head, else False. Write a function find_in_map(book_map, target) that returns True if target is a key in book_map, else False.

DSA Python

book_list = [101, 102, 103, 104, 105]
book_map = {101: 'Book A', 102: 'Book B', 103: 'Book C', 104: 'Book D', 105: 'Book E'}

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

head = Node(101)
node2 = Node(102)
node3 = Node(103)
node4 = Node(104)
node5 = Node(105)

head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# Write find_in_list, find_in_linked_list, and find_in_map functions
# Your code here

Hint

Use in keyword for list and dictionary. For linked list, loop through nodes until you find the target or reach the end.

4

Print the lookup results for book ID 103

Print the result of find_in_list(book_list, 103), find_in_linked_list(head, 103), and find_in_map(book_map, 103) each on a separate line.

DSA Python

book_list = [101, 102, 103, 104, 105]
book_map = {101: 'Book A', 102: 'Book B', 103: 'Book C', 104: 'Book D', 105: 'Book E'}

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

head = Node(101)
node2 = Node(102)
node3 = Node(103)
node4 = Node(104)
node5 = Node(105)

head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

def find_in_list(book_list, target):
    return target in book_list

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

def find_in_map(book_map, target):
    return target in book_map

# Print results of looking for 103 in all three
# Your code here

Hint

Use three separate print statements to show the results for the list, linked list, and map.

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