Hash Map vs Array vs Linked List for Lookup in DSA Go - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Lookup time comparison: Array vs Linked List

What is the output of the following Go code that searches for the value 5 in an array and a linked list?

DSA Go

package main
import "fmt"

type Node struct {
    val  int
    next *Node
}

func searchArray(arr []int, target int) bool {
    for _, v := range arr {
        if v == target {
            return true
        }
    }
    return false
}

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

func main() {
    arr := []int{1, 3, 5, 7, 9}
    head := &Node{1, &Node{3, &Node{5, &Node{7, &Node{9, nil}}}}}
    fmt.Println(searchArray(arr, 5))
    fmt.Println(searchLinkedList(head, 5))
}

A

true
true

B

false
true

C

true
false

D

false
false

💡 Hint

Both array and linked list contain the value 5, so searching should find it.

The searchArray function iterates over the array and finds 5, returning true. The searchLinkedList function traverses the linked list nodes and finds 5, returning true as well.

❓ Predict Output

intermediate

Hash Map lookup result

What is the output of this Go code that looks up a key in a hash map?

DSA Go

package main
import "fmt"

func main() {
    m := map[string]int{"apple": 5, "banana": 3}
    val, ok := m["banana"]
    fmt.Println(val, ok)
}

A 3 false

B 0 false

C 3 true

D 0 true

💡 Hint

The key "banana" exists in the map with value 3.

The map contains "banana" with value 3, so val is 3 and ok is true indicating the key exists.

🧠 Conceptual

advanced

Time complexity of lookup in data structures

Which data structure provides the fastest average lookup time for searching an element by key?

A Hash map with average constant time

B Linked list with linear search

C Array with linear search

D Binary tree with linear search

💡 Hint

Think about how many elements you check on average in each structure.

Hash maps provide average O(1) lookup time by using a hash function to directly access the bucket. Arrays and linked lists require checking elements one by one (O(n)). Binary trees can provide O(log n) if balanced, but linear search is O(n).

🔧 Debug

advanced

Why does this linked list lookup fail?

Given this Go code to search a linked list, what is the reason it always returns false?

DSA Go

package main
import "fmt"

type Node struct {
    val  int
    next *Node
}

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

func main() {
    head := &Node{1, &Node{2, &Node{3, nil}}}
    fmt.Println(search(head, 3))
}

A The function does not traverse the list at all

B The target value is not in the list

C The linked list is empty

D The loop condition skips checking the last node

💡 Hint

Check the loop condition carefully and what nodes it visits.

The loop condition 'current.next != nil' stops before the last node, so the last node's value is never checked. This causes the function to miss the target if it is in the last node.

🚀 Application

expert

Choosing the best data structure for frequent lookups and insertions

You need a data structure to store user IDs and quickly check if a user exists. You also need to add new users frequently. Which data structure is best?

A Array, because it is simple and fast to insert at the end

B Hash map, because it provides fast average lookup and insertion

C Linked list, because it allows fast insertion anywhere

D Binary search tree, because it keeps elements sorted

💡 Hint

Consider both lookup and insertion speed for large data.

Hash maps provide average O(1) time for both lookup and insertion, making them ideal for frequent existence checks and additions. Arrays and linked lists have slower lookups (O(n)). Binary search trees have O(log n) but are more complex.

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