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

Mental Model

Lookup means finding a value quickly by its key or position. 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 with books in order, a linked list is like a chain of books you must check one by one, and a hash map is like a librarian who instantly tells you where the book is.

Array: [0]1 -> [1]2 -> [2]3 -> null
Linked List: 1 -> 2 -> 3 -> null
Hash Map: {key1: val1, key2: val2, key3: val3}

Dry Run Walkthrough

Input: Data: 1, 2, 3; Lookup value 2

Goal: Show how each structure finds the value 2 and how fast it is

Step 1: Check array index 0 for value 2

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

Why: Start at first position to find value 2

Step 2: Check array index 1 for value 2

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

Why: Found value 2 at index 1, lookup done

Step 3: Start at linked list head node with value 1

1 -> 2 -> 3 -> null ↑

Why: Begin traversal from first node

Step 4: Move to next node with value 2

1 -> [2]2 -> 3 -> null

Why: Found value 2 by checking nodes one by one

Step 5: Use hash function on key '2' to find bucket

{2: val2, ...}

Why: Hash map uses key to jump directly to value

Step 6: Retrieve value 2 directly from hash map bucket

{2: [val2]}

Why: Lookup is instant with hash map

Result:

Array found 2 at index 1
Linked List found 2 after checking 2 nodes
Hash Map found 2 instantly by key

Annotated Code

DSA Go

package main

import "fmt"

// Node for linked list
type Node struct {
	val  int
	next *Node
}

// LinkedList struct
type LinkedList struct {
	head *Node
}

// Insert at end for linked list
func (ll *LinkedList) Insert(val int) {
	newNode := &Node{val: val}
	if ll.head == nil {
		ll.head = newNode
		return
	}
	curr := ll.head
	for curr.next != nil {
		curr = curr.next
	}
	curr.next = newNode
}

// Lookup in linked list
func (ll *LinkedList) Lookup(val int) bool {
	curr := ll.head
	for curr != nil {
		if curr.val == val {
			return true
		}
		curr = curr.next // advance curr to next node
	}
	return false
}

func main() {
	// Array lookup
	arr := []int{1, 2, 3}
	foundInArray := false
	for i := 0; i < len(arr); i++ {
		if arr[i] == 2 {
			foundInArray = true
			fmt.Printf("Array found 2 at index %d\n", i)
			break // stop after finding
		}
	}

	// Linked list lookup
	ll := LinkedList{}
	ll.Insert(1)
	ll.Insert(2)
	ll.Insert(3)
	if ll.Lookup(2) {
		fmt.Println("Linked List found 2 after checking nodes")
	} else {
		fmt.Println("Linked List did not find 2")
	}

	// Hash map lookup
	hm := map[int]string{1: "one", 2: "two", 3: "three"}
	val, ok := hm[2] // direct access by key
	if ok {
		fmt.Printf("Hash Map found 2 instantly with value '%s'\n", val)
	} else {
		fmt.Println("Hash Map did not find 2")
	}
}

curr = curr.next // advance curr to next node

advance curr to next node -- keeps traversing until value found or end

if arr[i] == 2 { ... break

check each array element until value found, then stop

val, ok := hm[2]

directly access hash map by key for instant lookup

Output

Array found 2 at index 1

Linked List found 2 after checking nodes

Hash Map found 2 instantly with value 'two'

Complexity Analysis

Time: O(n) for array and linked list because they may check each element; O(1) for hash map because it jumps directly to the key

Space: O(n) for all because they store n elements; hash map uses extra space for buckets

vs Alternative: Hash map is faster for lookup than array or linked list but uses more memory; array is faster than linked list for lookup because of direct indexing

Edge Cases

Empty data structures

Lookup returns not found immediately

DSA Go

if ll.head == nil { return false }

Value not present

Lookup scans all elements and returns false

DSA Go

for curr != nil { if curr.val == val { return true } curr = curr.next }

Single element structure

Lookup checks only one element and returns result

DSA Go

if arr[i] == 2 { ... }

When to Use This Pattern

When you need fast lookup by key, think hash map; when data is small or ordered, array is simple; when you need easy insertion and order, linked list is useful.

Common Mistakes

Mistake: Assuming linked list lookup is as fast as array or hash map
Fix: Remember linked list requires checking nodes one by one, so it's slower for lookup

Mistake: Using hash map without checking if key exists
Fix: Always check if key is present before using the value to avoid errors

Summary

Compares how fast lookup is in hash map, array, and linked list.

Use hash map for fastest key-based lookup, array for indexed data, linked list for flexible insertion.

Hash map jumps directly to data, array checks by index, linked list checks nodes one by one.

Practice

1. Which data structure provides the fastest average lookup time for finding an element by key?

easy

A. Stack

B. Hash Map

C. Linked List

D. Array

Solution

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

   Hash Map uses hashing 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 all nodes, O(n).

2. Step 2: Compare average lookup times

   Hash Map is fastest on average for key lookup because it directly computes the position. Arrays and Linked Lists are slower for searching by value.

3. Final Answer:

   Hash Map -> Option B

4. Quick Check:

   Fastest lookup by key = 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 searching by value
• Assuming linked list lookup is fast
• Thinking stack is a lookup structure

2. Which of the following is the correct way to declare a hash map in Go for string keys and integer values?

easy

A. var m map[string]int = make(map[string]int)

B. var m = [string]int{}

C. var m = []int{}

D. var m map[int]string = make(map[int]string)

Solution

1. Step 1: Identify correct Go syntax for hash map declaration

   In Go, maps are declared with 'map[keyType]valueType' and initialized with make(). var m map[string]int = make(map[string]int) uses 'map[string]int' and make(), which is correct.

2. Step 2: Check other options for errors

   var m = [string]int{} uses array syntax incorrectly. var m = []int{} is a slice, not a map. var m map[int]string = make(map[int]string) has reversed key and value types compared to question.

3. Final Answer:

   var m map[string]int = make(map[string]int) -> Option A

4. Quick Check:

   Go map syntax = var m map[string]int = make(map[string]int) [OK]

Hint: Use make(map[keyType]valueType) to create Go maps [OK]

Common Mistakes:

• Using array or slice syntax instead of map
• Not initializing map with make()
• Swapping key and value types

3. You have a large dataset of unique user IDs and want to check membership efficiently. Which data structure should you choose and why? A hash map, an array, or a linked list?

easy

A. Array, because it stores elements contiguously for fast access

B. Linked List, because it uses less memory and is easy to insert

C. None, use a stack for membership checking

D. Hash Map, because it provides average O(1) lookup time for membership checks

Solution

1. Step 1: Understand membership check requirements

   Membership check means quickly finding if an element exists. For large datasets, speed matters.

2. Step 2: Compare data structures for membership check

   Array requires scanning O(n), linked list also O(n). Hash Map uses hashing for average O(1) lookup, best for membership.

3. Final Answer:

   Hash Map, because it provides average O(1) lookup time for membership checks -> Option D

4. Quick Check:

   Membership check fastest = Hash Map [OK]

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

Common Mistakes:

• Choosing array or list for fast membership
• Ignoring hash map average O(1) lookup
• Confusing stack with membership structure

4. What will be the output of the following Go code snippet?

package main
import "fmt"
func main() {
  arr := []int{10, 20, 30, 40}
  m := make(map[int]int)
  for i, v := range arr {
    m[v] = i
  }
  fmt.Println(m[30])
}

medium

A. 2

B. 30

C. 0

D. Compilation error

Solution

1. Step 1: Understand the loop and map assignment

   The loop iterates over array elements with index i and value v. It sets m[v] = i, so key is element value, value is index.

2. Step 2: Find the value for key 30 in map

   For element 30, index is 2, so m[30] = 2. Printing m[30] outputs 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   m[30] = index 2 [OK]

Hint: Map keys are array values, values are indices [OK]

Common Mistakes:

• Confusing key and value in map
• Expecting output 30 instead of index
• Thinking code has error

5. Identify the error in the following Go code that tries to find if a value exists in a linked list:

package main
import "fmt"

type Node struct {
  val int
  next *Node
}

func contains(head *Node, target int) bool {
  for head != nil {
    if head.val == target {
      return true
    }
    head = head.next
  }
  return false
}

func main() {
  var head *Node
  head.val = 10
  head.next = nil
  fmt.Println(contains(head, 10))
}

medium

A. Loop condition should be head.next != nil

B. Function contains has wrong return type

C. head is nil, so accessing head.val causes runtime panic

D. Missing import for fmt package

Solution

1. Step 1: Analyze initialization of head pointer

   head is declared as nil pointer. Accessing head.val without allocating Node causes runtime panic (nil pointer dereference).

2. Step 2: Check function and loop correctness

   Function contains is correct. Loop condition is correct.

3. Final Answer:

   head is nil, so accessing head.val causes runtime panic -> Option C

4. Quick Check:

   Nil pointer access causes panic [OK]

Hint: Initialize nodes before accessing fields to avoid nil panic [OK]

Common Mistakes:

• Ignoring nil pointer dereference
• Thinking loop condition is wrong
• Missing import is not main error