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.