Hash Map vs Array vs Linked List for Lookup in DSA Go - Build Both Approaches

Hash Map vs Array vs Linked List for Lookup

📖 Scenario: Imagine you have a small library with books identified by unique IDs. You want to find if a book is available quickly. You will compare three ways to store and look up books: an array, a linked list, and a hash map.

🎯 Goal: Build three data structures: an array, a linked list, and a hash map to store book IDs. Then, write code to check if a specific book ID exists in each structure. Finally, print the results to see which method finds the book fastest.

📋 What You'll Learn

Create an array with exact book IDs: 101, 102, 103, 104, 105

Create a linked list with the same book IDs in order

Create a hash map with book IDs as keys and boolean true as values

Write lookup code to check if book ID 103 exists in each data structure

Print the lookup results for each data structure

💡 Why This Matters

🌍 Real World

Libraries, inventories, and many apps need to store and find items quickly. Choosing the right data structure helps make searches fast and efficient.

💼 Career

Understanding arrays, linked lists, and hash maps is essential for software developers to write efficient code and optimize performance.

1

Create an array of book IDs

Create a variable called booksArray as an array of integers with these exact values: 101, 102, 103, 104, 105.

DSA Go

# Create the array booksArray with the given book IDs
# Your code here

Hint

Use a slice literal to create booksArray with the exact book IDs.

2

Create a linked list of book IDs

Define a linked list node type called Node with fields value int and next *Node. Then create a linked list called booksList with nodes holding the book IDs 101, 102, 103, 104, 105 in order.

DSA Go

package main

type Node struct {
    value int
    next  *Node
}

func main() {
    booksArray := []int{101, 102, 103, 104, 105}

    // Create linked list booksList with nodes for 101, 102, 103, 104, 105
    // Your code here
}

Hint

Create nodes one by one and link them using the next pointer.

3

Create a hash map of book IDs

Create a variable called booksMap as a map from int to bool. Add entries for the book IDs 101, 102, 103, 104, 105 with value true for each key.

DSA Go

package main

type Node struct {
    value int
    next  *Node
}

func main() {
    booksArray := []int{101, 102, 103, 104, 105}

    booksList := &Node{value: 101}
    booksList.next = &Node{value: 102}
    booksList.next.next = &Node{value: 103}
    booksList.next.next.next = &Node{value: 104}
    booksList.next.next.next.next = &Node{value: 105}

    // Create booksMap with keys 101, 102, 103, 104, 105 and value true
    // Your code here
}

Hint

Use a map literal to add all book IDs as keys with value true.

4

Lookup book ID 103 in all data structures and print results

Write code to check if the book ID 103 exists in booksArray, booksList, and booksMap. For booksArray, use a for loop to find 103. For booksList, traverse nodes to find 103. For booksMap, check if key 103 exists. Then print three lines exactly as follows: Array: true or Array: false, LinkedList: true or LinkedList: false, and HashMap: true or HashMap: false depending on whether 103 was found.

DSA Go

package main

type Node struct {
    value int
    next  *Node
}

func main() {
    booksArray := []int{101, 102, 103, 104, 105}

    booksList := &Node{value: 101}
    booksList.next = &Node{value: 102}
    booksList.next.next = &Node{value: 103}
    booksList.next.next.next = &Node{value: 104}
    booksList.next.next.next.next = &Node{value: 105}

    booksMap := map[int]bool{
        101: true,
        102: true,
        103: true,
        104: true,
        105: true,
    }

    // Check if 103 is in booksArray, booksList, and booksMap
    // Print results as shown
    // Your code here
}

Hint

Use loops to search in array and linked list. Use map key check for hash map. Print results exactly as shown.

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