Search for a Value in Linked List in DSA Rust - Build from Scratch

Search for a Value in Linked List

📖 Scenario: Imagine you have a list of tasks to do, and you want to check if a specific task is already in your list.

🎯 Goal: You will build a simple linked list of tasks and write code to search for a specific task in that list.

📋 What You'll Learn

Create a linked list with exact tasks: "Laundry", "Groceries", "Homework", "Exercise"

Add a variable called search_task with the value "Homework"

Write a loop to search for search_task in the linked list

Print Found if the task is in the list, otherwise print Not Found

💡 Why This Matters

🌍 Real World

Searching in linked lists is useful in many programs where data is stored in a chain, like task lists, playlists, or navigation paths.

💼 Career

Understanding linked lists and search algorithms is fundamental for software development roles, especially those involving data structures and memory management.

1

Create the linked list with tasks

Create a linked list called tasks with nodes containing these exact strings in order: "Laundry", "Groceries", "Homework", "Exercise".

DSA Rust

// Define the Node struct and create the linked list with the tasks
// Your code here

Hint

Use Rc and RefCell to create nodes that can be shared and mutated.

Link nodes by setting the next field to Some(node.clone()).

2

Add the search task variable

Add a variable called search_task and set it to the string "Homework".

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: String,
    next: Option>>,
}

fn main() {
    let node4 = Rc::new(RefCell::new(Node { value: String::from("Exercise"), next: None }));
    let node3 = Rc::new(RefCell::new(Node { value: String::from("Homework"), next: Some(node4.clone()) }));
    let node2 = Rc::new(RefCell::new(Node { value: String::from("Groceries"), next: Some(node3.clone()) }));
    let tasks = Rc::new(RefCell::new(Node { value: String::from("Laundry"), next: Some(node2.clone()) }));

    // Create the search_task variable with value "Homework"
    // Your code here

Hint

Just create a variable search_task and assign it the string "Homework".

3

Search for the task in the linked list

Write a while loop to search for search_task in the linked list starting from tasks. Use a variable called current to traverse nodes. Stop when you find the task or reach the end.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: String,
    next: Option>>,
}

fn main() {
    let node4 = Rc::new(RefCell::new(Node { value: String::from("Exercise"), next: None }));
    let node3 = Rc::new(RefCell::new(Node { value: String::from("Homework"), next: Some(node4.clone()) }));
    let node2 = Rc::new(RefCell::new(Node { value: String::from("Groceries"), next: Some(node3.clone()) }));
    let tasks = Rc::new(RefCell::new(Node { value: String::from("Laundry"), next: Some(node2.clone()) }));

    let search_task = "Homework";

    // Use a while loop with variable current to search for search_task
    // Your code here

Hint

Use while let Some(node_rc) = current to loop through nodes.

Use node_rc.borrow() to access the node's value and next.

4

Print the search result

Print Found if the task was found, otherwise print Not Found. Use the found variable from the previous step.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: String,
    next: Option>>,
}

fn main() {
    let node4 = Rc::new(RefCell::new(Node { value: String::from("Exercise"), next: None }));
    let node3 = Rc::new(RefCell::new(Node { value: String::from("Homework"), next: Some(node4.clone()) }));
    let node2 = Rc::new(RefCell::new(Node { value: String::from("Groceries"), next: Some(node3.clone()) }));
    let tasks = Rc::new(RefCell::new(Node { value: String::from("Laundry"), next: Some(node2.clone()) }));

    let search_task = "Homework";

    let mut current = Some(tasks.clone());
    let mut found = false;
    while let Some(node_rc) = current {
        let node = node_rc.borrow();
        if node.value == search_task {
            found = true;
            break;
        }
        current = node.next.clone();
    }

    // Print "Found" if found is true, else print "Not Found"
    // Your code here

Hint

Use if found { println!("Found"); } else { println!("Not Found"); } to print the result.

Practice

1. What is the main purpose of searching for a value in a linked list?

easy

A. To find if a specific value exists in the list

B. To add a new node at the end of the list

C. To delete the first node of the list

D. To reverse the order of nodes in the list

Solution

1. Step 1: Understand the search operation

   Searching in a linked list means checking each node to see if it contains the value we want.

2. Step 2: Identify the goal of searching

   The goal is to find whether the value exists anywhere in the list, not to modify the list.

3. Final Answer:

   To find if a specific value exists in the list -> Option A

4. Quick Check:

   Search means find value [OK]

Hint: Search means check each node for the value [OK]

Common Mistakes:

• Confusing search with insertion or deletion
• Thinking search changes the list
• Assuming search reverses the list

2. Which Rust code snippet correctly starts a search for a value in a linked list node called head?

easy

A. let current = head.as_mut();

B. let current = head.unwrap();

C. let mut current = head.unwrap();

D. let mut current = head.as_ref();

Solution

1. Step 1: Understand linked list node type in Rust

   Linked list nodes are often wrapped in Option and Box, so head is Option.

2. Step 2: Choose safe way to start traversal

   Using head.as_ref() gives an Option reference to the node without moving ownership, allowing safe traversal.

3. Final Answer:

   let mut current = head.as_ref(); -> Option D

4. Quick Check:

   Use as_ref() to borrow node safely [OK]

Hint: Use as_ref() to get a reference without moving ownership [OK]

Common Mistakes:

• Using unwrap() which can panic if list is empty
• Using as_mut() when only reading values
• Not using mut when needing to traverse

3. What will be the output of this Rust code searching for value 5 in the linked list 1 -> 3 -> 5 -> 7?

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

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

fn main() {
    let list = Some(Box::new(Node { value: 1, next: Some(Box::new(Node { value: 3, next: Some(Box::new(Node { value: 5, next: Some(Box::new(Node { value: 7, next: None })) })) })) }));
    println!("{}", search(&list, 5));
}

medium

A. false

B. true

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace the search function

   The function starts at head (value 1), checks 1 != 5, moves to 3, checks 3 != 5, moves to 5, finds 5 == 5, returns true.

2. Step 2: Confirm output of main

   Main prints the boolean returned by search, which is true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Value found in list = true [OK]

Hint: Follow nodes until value matches or list ends [OK]

Common Mistakes:

• Assuming search returns false without checking all nodes
• Confusing Option types causing compile errors
• Forgetting to use as_ref() when traversing

4. Identify the bug in this Rust function that searches for a value in a linked list:

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

medium

A. Incorrect comparison operator used

B. Missing mut keyword for current variable

C. Using unwrap() on Option without checking can cause panic

D. Function does not return a boolean

Solution

1. Step 1: Analyze unwrap() usage

   Calling unwrap() on Option without checking if it is Some can cause the program to panic if the list is empty or next is None.

2. Step 2: Explain safe alternative

   Using as_ref() and pattern matching with while let Some(node) = current avoids panics by safely handling None cases.

3. Final Answer:

   Using unwrap() on Option without checking can cause panic -> Option C

4. Quick Check:

   Unsafe unwrap causes panic [OK]

Hint: Never unwrap Option without checking Some first [OK]

Common Mistakes:

• Ignoring possibility of None causing panic
• Not using while let for safe traversal
• Assuming unwrap always safe

5. Given a linked list where each node contains an integer, how would you modify the search function to return the position (0-based index) of the first occurrence of a target value, or -1 if not found? Choose the correct Rust code snippet.

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

fn search_position(head: &Option, target: i32) -> i32 {
    // Fill in the code
}

hard

A. let mut current = head.as_ref(); let mut index = 0; while let Some(node) = current { if node.value == target { return index; } current = node.next.as_ref(); index += 1; } -1

B. let mut current = head.unwrap(); let mut index = 0; while current.is_some() { if current.value == target { return index; } current = current.next.unwrap(); index += 1; } -1

C. let mut current = head.as_ref(); let mut index = 1; while let Some(node) = current { if node.value == target { return index; } current = node.next.as_ref(); index += 1; } 0

D. let mut current = head.as_ref(); let mut index = 0; while let Some(node) = current { if node.value != target { return index; } current = node.next.as_ref(); index += 1; } -1

Solution

1. Step 1: Initialize traversal and index

   Start with current as a reference to head and index at 0 to count positions from start.

2. Step 2: Traverse nodes checking values

   Use while let Some(node) to safely traverse. If node.value equals target, return current index. Otherwise, move to next node and increment index.

3. Step 3: Return -1 if not found

   If loop ends without finding target, return -1 to indicate absence.

4. Final Answer:

   let mut current = head.as_ref(); let mut index = 0; while let Some(node) = current { if node.value == target { return index; } current = node.next.as_ref(); index += 1; } -1 -> Option A

5. Quick Check:

   Return index if found, else -1 [OK]

Hint: Return index on match, else -1 after full traversal [OK]

Common Mistakes:

• Starting index at 1 instead of 0
• Returning index when value does not match
• Using unwrap() causing panic on empty list