Search for a Value in Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of searching for value 3 in the linked list?

Consider the linked list created by inserting values 1, 2, 3, 4 in order. What will be the output of searching for the value 3?

DSA Rust

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn append(&mut self, val: i32) {
        let new_node = Box::new(Node { value: val, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut node) => {
                while let Some(ref mut next_node) = node.next {
                    node = next_node;
                }
                node.next = Some(new_node);
            }
        }
    }

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

fn main() {
    let mut list = LinkedList::new();
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    println!("{}", list.search(3));
}

A true

B false

C 3

D Compilation error

💡 Hint

Think about whether the value 3 exists in the linked list nodes.

The search function traverses the linked list and returns true if it finds the value 3. Since 3 was appended, the output is true.

❓ Predict Output

intermediate

What is the output when searching for a value not in the list?

Given the linked list with values 5, 10, 15, what is the output of searching for the value 7?

DSA Rust

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn append(&mut self, val: i32) {
        let new_node = Box::new(Node { value: val, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut node) => {
                while let Some(ref mut next_node) = node.next {
                    node = next_node;
                }
                node.next = Some(new_node);
            }
        }
    }

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

fn main() {
    let mut list = LinkedList::new();
    list.append(5);
    list.append(10);
    list.append(15);
    println!("{}", list.search(7));
}

A 7

B true

C Runtime panic

D false

💡 Hint

Check if the value 7 is in the list nodes.

The search function returns false because 7 is not found in the linked list.

🔧 Debug

advanced

What error does this code produce when searching in an empty list?

Analyze the code below. What error will occur when searching for any value in an empty linked list?

DSA Rust

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

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

fn main() {
    let list = LinkedList::new();
    println!("{}", list.search(1));
}

A Runtime panic due to null pointer dereference

B No error, prints false

C Compilation error due to missing lifetime annotations

D Infinite loop

💡 Hint

Consider how the search function handles None head.

The search function safely handles an empty list by checking if head is None and returns false without error.

🧠 Conceptual

advanced

How many nodes are traversed when searching for value 4 in the list 1->2->3->4->5?

Given a linked list with nodes containing values 1, 2, 3, 4, 5 in order, how many nodes does the search function visit when searching for the value 4?

A 4

B 5

C 3

D 1

💡 Hint

Search visits nodes until it finds the value or reaches the end.

The search visits nodes with values 1, 2, 3, and 4 before finding the target, so 4 nodes are visited.

🚀 Application

expert

What is the output after searching for value 10 in a reversed linked list?

A linked list is created by appending 5, 10, 15, then reversed to 15->10->5. What is the output of searching for value 10 after reversal?

DSA Rust

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn append(&mut self, val: i32) {
        let new_node = Box::new(Node { value: val, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut node) => {
                while let Some(ref mut next_node) = node.next {
                    node = next_node;
                }
                node.next = Some(new_node);
            }
        }
    }

    fn reverse(&mut self) {
        let mut prev = None;
        let mut current = self.head.take();
        while let Some(mut boxed_node) = current {
            let next = boxed_node.next.take();
            boxed_node.next = prev;
            prev = Some(boxed_node);
            current = next;
        }
        self.head = prev;
    }

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

fn main() {
    let mut list = LinkedList::new();
    list.append(5);
    list.append(10);
    list.append(15);
    list.reverse();
    println!("{}", list.search(10));
}

A Compilation error

B false

C true

D Runtime panic

💡 Hint

Reversing the list does not remove any nodes, so searching for 10 should still succeed.

The reverse function reverses the list but keeps all nodes. Searching for 10 returns true.

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