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

Hash Map vs Array vs Linked List for Lookup

📖 Scenario: Imagine you run a small library. You want to find books quickly by their ID number. You have three ways to store books: a list (array), a linked list, and a hash map. Each way stores book IDs and their titles.You will learn how to look up a book title by its ID using each method and see which one is fastest and easiest.

🎯 Goal: Build three data structures in Rust: an array, a linked list, and a hash map, each holding the same books. Then write code to find a book title by its ID in each structure.

📋 What You'll Learn

Create an array of tuples with book IDs and titles

Create a linked list of books with IDs and titles

Create a hash map with book IDs as keys and titles as values

Write lookup code to find a book title by ID in each data structure

Print the found book title or a message if not found

💡 Why This Matters

🌍 Real World

Libraries, stores, and apps often need to find items quickly by ID. Choosing the right data structure helps make searches fast and efficient.

💼 Career

Understanding arrays, linked lists, and hash maps is key for software developers to write efficient code for data storage and retrieval.

1

Create an array of books

Create a variable called books_array as an array of tuples with these exact entries: (101, "The Rust Book"), (102, "Programming Basics"), (103, "Data Structures").

DSA Rust

# Create books_array as an array of tuples with book ID and title
# Your code here

Hint

Use square brackets [] to create an array. Each element is a tuple with an integer and a string.

2

Create a linked list of books

Add a linked list called books_list using std::collections::LinkedList. Insert the same books with IDs and titles in the order: 101, 102, 103.

DSA Rust

fn main() {
    let books_array = [
        (101, "The Rust Book"),
        (102, "Programming Basics"),
        (103, "Data Structures"),
    ];

    // Create books_list as a LinkedList and add the books
    // Your code here
}

Hint

Use LinkedList::new() to create the list and push_back to add items.

3

Create a hash map of books

Add a hash map called books_map using std::collections::HashMap. Insert the same books with IDs as keys and titles as values: 101, 102, 103.

DSA Rust

use std::collections::LinkedList;
use std::collections::HashMap;

fn main() {
    let books_array = [
        (101, "The Rust Book"),
        (102, "Programming Basics"),
        (103, "Data Structures"),
    ];

    let mut books_list: LinkedList = LinkedList::new();
    books_list.push_back((101, "The Rust Book"));
    books_list.push_back((102, "Programming Basics"));
    books_list.push_back((103, "Data Structures"));

    // Create books_map as a HashMap and add the books
    // Your code here
}

Hint

Use HashMap::new() to create the map and insert to add key-value pairs.

4

Lookup book title by ID in all structures and print

Write code to find the book title with ID 102 in books_array, books_list, and books_map. Print the found titles with these exact lines:
println!("Array lookup: {}", title);
println!("LinkedList lookup: {}", title);
println!("HashMap lookup: {}", title);
If not found, print "Not found" instead of the title.

DSA Rust

use std::collections::LinkedList;
use std::collections::HashMap;

fn main() {
    let books_array = [
        (101, "The Rust Book"),
        (102, "Programming Basics"),
        (103, "Data Structures"),
    ];

    let mut books_list: LinkedList = LinkedList::new();
    books_list.push_back((101, "The Rust Book"));
    books_list.push_back((102, "Programming Basics"));
    books_list.push_back((103, "Data Structures"));

    let mut books_map: HashMap = HashMap::new();
    books_map.insert(101, "The Rust Book");
    books_map.insert(102, "Programming Basics");
    books_map.insert(103, "Data Structures");

    // Lookup book ID 102 in books_array, books_list, and books_map
    // Print results as instructed
    // Your code here
}

Hint

Use a for loop to find the book in the array and linked list. Use HashMap::get for the hash map. Print exactly as shown.

Practice

1. Which data structure provides the fastest average lookup time for a key-value pair in Rust?

easy

A. Array

B. Vector

C. Linked List

D. Hash Map

Solution

1. Step 1: Understand lookup times for data structures

   Hash Map uses hashing to find keys quickly, usually in constant time O(1).

2. Step 2: Compare with Array and Linked List

   Array and Linked List require searching elements linearly, which is slower (O(n)).

3. Final Answer:

   Hash Map -> Option D

4. Quick Check:

   Fastest lookup = Hash Map [OK]

Hint: Hash Map uses hashing for O(1) lookup, arrays and lists are slower [OK]

Common Mistakes:

• Thinking arrays have O(1) lookup for keys (only for indices)
• Confusing linked list traversal with direct access
• Assuming vector is same as hash map for lookup

2. Which Rust syntax correctly declares a mutable HashMap named map with String keys and i32 values?

easy

A. let map: HashMap = HashMap::new();

B. let mut map: HashMap = HashMap::new();

C. let mut map = HashMap::new();

D. let map = HashMap::new();

Solution

1. Step 1: Check correct syntax for mutable HashMap declaration

   In Rust, let mut declares a mutable variable. The type is HashMap<String, i32>. The constructor is HashMap::new().

2. Step 2: Identify errors in other options

   let map = HashMap::new(); misses mut. let mut map = HashMap::new(); has wrong generic syntax. let map: HashMap = HashMap::new(); swaps key and value types.

3. Final Answer:

   let mut map: HashMap = HashMap::new(); -> Option B

4. Quick Check:

   Mutable HashMap syntax = let mut map: HashMap = HashMap::new(); [OK]

Hint: Use let mut with HashMap::new() and correct generics [OK]

Common Mistakes:

• Forgetting mut keyword for mutable map
• Wrong generic syntax with new()
• Swapping key and value types

3. What is the output of this Rust code snippet?

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("orange", 5);

    let lookup = map.get("banana");
    println!("{:?}", lookup);
}

medium

A. None

B. 2

C. Some(2)

D. banana

Solution

1. Step 1: Understand HashMap get method return type

   The get method returns an Option type: Some(&value) if key exists, else None.

2. Step 2: Check if key "banana" exists and its value

   Key "banana" exists with value 2, so get("banana") returns Some(&2). Printing with {:?} shows Some(2).

3. Final Answer:

   Some(2) -> Option C

4. Quick Check:

   HashMap get returns Option = Some(2) [OK]

Hint: HashMap get returns Option; Some(value) if found, else None [OK]

Common Mistakes:

• Expecting direct value instead of Option
• Confusing None with Some
• Printing key instead of value

4. Identify the error in this Rust code that tries to find a value in a linked list:

struct Node {
    value: i32,
    next: Option,
}

fn find(head: &Option, target: i32) -> bool {
    let mut current = head;
    while current.is_some() {
        if current.as_ref().unwrap().value == target {
            return true;
        }
        current = current.unwrap().next;
    }
    false
}

medium

A. Using unwrap() twice causes ownership error

B. Missing mutable keyword for current

C. Incorrect comparison operator in if statement

D. next field should be a reference, not Box

Solution

1. Step 1: Analyze ownership in while loop

   Calling unwrap() on current moves ownership, so current cannot be used again.

2. Step 2: Identify why unwrap() causes error

   Using unwrap() twice consumes current, causing ownership error. Instead, use references or pattern matching.

3. Final Answer:

   Using unwrap() twice causes ownership error -> Option A

4. Quick Check:

   Ownership error due to unwrap() usage [OK]

Hint: unwrap() moves ownership; use references to avoid errors [OK]

Common Mistakes:

• Ignoring ownership rules with unwrap()
• Thinking mutable needed for current here
• Confusing Box with reference types

5. You need to store a large collection of user IDs (integers) and quickly check if a user ID exists. Which data structure is best and why? Choose the best option considering lookup speed and memory efficiency.

hard

A. Hash Map, because it offers average constant time lookup for keys

B. Array, because it provides constant time lookup for any integer key

C. Linked List, because it uses less memory and is easy to implement

D. Vector, because it automatically resizes and supports fast lookup

Solution

1. Step 1: Consider lookup speed for large collections

   Linked List has O(n) lookup, which is slow. Array lookup by index is O(1), but only if keys are indices, not arbitrary integers.

2. Step 2: Evaluate Hash Map and Vector

   Hash Map provides average O(1) lookup for arbitrary keys like user IDs. Vector lookup by index is O(1), but user IDs may not be continuous indices.

3. Final Answer:

   Hash Map, because it offers average constant time lookup for keys -> Option A

4. Quick Check:

   Best lookup for arbitrary keys = Hash Map [OK]

Hint: Use Hash Map for fast lookup of arbitrary keys like user IDs [OK]

Common Mistakes:

• Assuming array lookup works for arbitrary keys
• Choosing linked list for speed
• Confusing vector with hash map for key lookup