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.