Hash Map vs Array vs Linked List for Lookup in DSA Python - Complexity Comparison

Time Complexity: Hash Map vs Array vs Linked List for Lookup

O(n) for array and linked list, O(1) for hash map

Understanding Time Complexity

We want to understand how fast we can find a value in different data structures.

How does the time to look up a value change as the data grows?

Scenario Under Consideration

Analyze the time it takes to find a value in each data structure.

def lookup_array(arr, target):
    for item in arr:
        if item == target:
            return True
    return False


def lookup_linked_list(head, target):
    current = head
    while current:
        if current.value == target:
            return True
        current = current.next
    return False


def lookup_hash_map(hmap, target):
    return target in hmap

This code shows how to find a value in an array, a linked list, and a hash map.

Identify Repeating Operations

Look at what repeats when searching:

• Array and Linked List: Loop through each item one by one.
• Hash Map: Directly check if the key exists using a special method.
• Primary operation: Checking each element one by one for array and linked list; direct key check for hash map.
• How many times: Up to all elements for array and linked list; usually once for hash map.

How Execution Grows With Input

As the number of items grows, the time to find a value changes differently:

Input Size (n)	Array/Linked List Operations	Hash Map Operations
10	Up to 10 checks	About 1 check
100	Up to 100 checks	About 1 check
1000	Up to 1000 checks	About 1 check

Pattern observation: Array and linked list grow linearly with input size; hash map stays almost constant.

Final Time Complexity

Time Complexity: O(n) for array and linked list, O(1) for hash map

This means looking up in an array or linked list takes longer as data grows, but hash map lookup stays fast.

Common Mistake

[X] Wrong: "All data structures find values equally fast."

[OK] Correct: Arrays and linked lists check items one by one, so they get slower with more data. Hash maps use a special way to jump directly to the value.

Interview Connect

Knowing these differences helps you pick the right data structure for fast lookups, a key skill in many coding challenges and real projects.

Self-Check

"What if the hash map has many collisions? How would that affect lookup time complexity?"