Delete Node at Specific Position in DSA Rust - Build from Scratch

Delete Node at Specific Position

📖 Scenario: Imagine you have a list of tasks to do today. Sometimes, you finish a task and want to remove it from your list. You want to remove a task at a specific position in your list.

🎯 Goal: You will create a linked list of tasks, then remove a task at a given position, and finally print the updated list.

📋 What You'll Learn

Create a linked list with exactly these tasks in order: "Wake up", "Brush teeth", "Have breakfast", "Go to work", "Read book"

Create a variable called position and set it to 2 (to remove the third task, counting from zero)

Write a function called delete_at_position that removes the node at the given position from the linked list

Print the linked list after deletion in the format: task1 -> task2 -> ... -> null

💡 Why This Matters

🌍 Real World

Linked lists are used in many applications like task scheduling, undo functionality, and managing playlists where items are added or removed dynamically.

💼 Career

Understanding linked list operations like deletion is fundamental for software engineers working with low-level data structures, memory management, and performance optimization.

1

Create the linked list of tasks

Create a singly linked list called tasks with nodes containing these exact strings in order: "Wake up", "Brush teeth", "Have breakfast", "Go to work", "Read book". Use the provided Node struct and Option for links.

DSA Rust

struct Node {
    data: String,
    next: Option>,
}

impl Node {
    fn new(data: String) -> Self {
        Node { data, next: None }
    }
}

fn main() {
    // Create the linked list tasks here
    // Your code here
}

Hint

Start by creating the first node with "Wake up". Then link each next node using next and Some(Box::new(Node::new(...))).

2

Set the position to delete

Create a variable called position and set it to 2. This means you want to delete the node at index 2 (third node) in the linked list.

DSA Rust

struct Node {
    data: String,
    next: Option>,
}

impl Node {
    fn new(data: String) -> Self {
        Node { data, next: None }
    }
}

fn main() {
    let mut tasks = Box::new(Node::new("Wake up".to_string()));
    tasks.next = Some(Box::new(Node::new("Brush teeth".to_string())));
    tasks.next.as_mut().unwrap().next = Some(Box::new(Node::new("Have breakfast".to_string())));
    tasks.next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new("Go to work".to_string())));
    tasks.next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new("Read book".to_string())));
    // Create position variable here
    // Your code here
}

Hint

Just create a variable position and assign it the value 2.

3

Write the function to delete node at position

Write a function called delete_at_position that takes head: Option> and position: usize as parameters and returns Option>. This function should remove the node at the given position from the linked list and return the new head. Use this function to update tasks by calling tasks = delete_at_position(Some(tasks), position).unwrap().

DSA Rust

struct Node {
    data: String,
    next: Option>,
}

impl Node {
    fn new(data: String) -> Self {
        Node { data, next: None }
    }
}

fn delete_at_position(head: Option>, position: usize) -> Option> {
    // Implement deletion logic here
    // Your code here
}

fn main() {
    let mut tasks = Box::new(Node::new("Wake up".to_string()));
    tasks.next = Some(Box::new(Node::new("Brush teeth".to_string())));
    tasks.next.as_mut().unwrap().next = Some(Box::new(Node::new("Have breakfast".to_string())));
    tasks.next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new("Go to work".to_string())));
    tasks.next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new("Read book".to_string())));
    let position = 2;
    // Call delete_at_position and update tasks
    // Your code here
}

Hint

To delete the first node, return the next node. Otherwise, walk through the list until the node before the position, then change its next to skip the node at position.

4

Print the updated linked list

Write code to print the linked list tasks after deletion. Print each node's data followed by ->, ending with null. Use a while loop with a variable current to traverse the list.

DSA Rust

struct Node {
    data: String,
    next: Option>,
}

impl Node {
    fn new(data: String) -> Self {
        Node { data, next: None }
    }
}

fn delete_at_position(head: Option>, position: usize) -> Option> {
    if position == 0 {
        return head.and_then(|node| node.next);
    }
    let mut head = head;
    let mut current = head.as_mut();
    let mut index = 0;
    while let Some(node) = current {
        if index + 1 == position {
            if let Some(next_node) = node.next.as_mut() {
                node.next = next_node.next.take();
            } else {
                node.next = None;
            }
            break;
        }
        current = node.next.as_mut();
        index += 1;
    }
    head
}

fn main() {
    let mut tasks = Box::new(Node::new("Wake up".to_string()));
    tasks.next = Some(Box::new(Node::new("Brush teeth".to_string())));
    tasks.next.as_mut().unwrap().next = Some(Box::new(Node::new("Have breakfast".to_string())));
    tasks.next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new("Go to work".to_string())));
    tasks.next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new("Read book".to_string())));
    let position = 2;
    tasks = delete_at_position(Some(tasks), position).unwrap();
    // Print the linked list here
    // Your code here
}

Hint

Use a while loop with a variable current starting at Some(&tasks). Print node.data followed by ->. Move current to node.next.as_deref() until None. Finally, print null.

Practice

1. What does deleting a node at a specific position in a linked list mean?

easy

A. Removing the node located at that position and linking its neighbors

B. Adding a new node at that position

C. Swapping two nodes in the list

D. Counting the number of nodes up to that position

Solution

1. Step 1: Understand node deletion

   Deleting a node means removing it from the list and connecting the previous node to the next node.

2. Step 2: Apply to specific position

   At a specific position, the node at that index is removed and neighbors are linked to maintain the list.

3. Final Answer:

   Removing the node located at that position and linking its neighbors -> Option A

4. Quick Check:

   Delete node = Remove and link neighbors [OK]

Hint: Delete means remove node and link neighbors [OK]

Common Mistakes:

• Confusing deletion with insertion
• Thinking deletion swaps nodes
• Ignoring neighbor linking after deletion

2. Which Rust syntax correctly declares a mutable linked list node struct?

easy

A. struct Node { data: i32, mut next: Option }

B. struct Node { data: i32, next: Option }

C. struct Node { data: i32, next: Box<Node> }

D. struct Node { data: i32, next: &Node }

Solution

1. Step 1: Check struct fields

   Rust linked list nodes use Option for next to allow null and ownership.

2. Step 2: Validate mutability

   Mutability is controlled outside struct fields; 'mut' keyword inside struct is invalid.

3. Final Answer:

   struct Node { data: i32, next: Option } -> Option B

4. Quick Check:

   Option for next pointer [OK]

Hint: Use Option for next pointer [OK]

Common Mistakes:

• Adding 'mut' inside struct fields
• Using Box<Node> without Option causing no null
• Using references (&Node) causing lifetime issues

3. What is the output linked list after deleting the node at position 2 (0-based) from this list: 10 -> 20 -> 30 -> 40 -> null?

fn main() {
    let mut head = Some(Box::new(Node { data: 10, next: Some(Box::new(Node { data: 20, next: Some(Box::new(Node { data: 30, next: Some(Box::new(Node { data: 40, next: None })) })) })) }));
    delete_at_position(&mut head, 2);
    print_list(&head);
}

fn delete_at_position(head: &mut Option, pos: usize) {
    if pos == 0 {
        *head = head.as_mut().and_then(|node| node.next.take());
        return;
    }
    let mut current = head.as_mut();
    for _ in 0..pos-1 {
        if let Some(node) = current {
            current = node.next.as_mut();
        }
    }
    if let Some(node) = current {
        node.next = node.next.as_mut().and_then(|next_node| next_node.next.take());
    }
}

fn print_list(head: &Option) {
    let mut current = head;
    while let Some(node) = current {
        print!("{} -> ", node.data);
        current = &node.next;
    }
    println!("null");
}

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

medium

A. 10 -> 20 -> 30 -> null

B. 10 -> 30 -> 40 -> null

C. 10 -> 20 -> 40 -> null

D. 20 -> 30 -> 40 -> null

Solution

1. Step 1: Identify node to delete at position 2

   Position 2 node has data 30 in list 10 -> 20 -> 30 -> 40 -> null.

2. Step 2: Remove node 30 and link 20 to 40

   After deletion, list becomes 10 -> 20 -> 40 -> null.

3. Final Answer:

   10 -> 20 -> 40 -> null -> Option C

4. Quick Check:

   Deleted node 30 at pos 2 [OK]

Hint: Delete node at pos links previous to next [OK]

Common Mistakes:

• Deleting wrong node index
• Not linking neighbors correctly
• Confusing 0-based and 1-based positions

4. Identify the bug in this Rust function that deletes a node at a given position in a linked list:

fn delete_at_position(head: &mut Option, pos: usize) {
    let mut current = head.as_mut();
    for _ in 0..pos {
        if let Some(node) = current {
            current = node.next.as_mut();
        }
    }
    if let Some(node) = current {
        node.next = node.next.as_mut().and_then(|next_node| next_node.next.take());
    }
}

medium

A. All of the above

B. Loop runs one time too many, skipping the previous node

C. Does not update head pointer when deleting first node

D. Function does not handle deleting head node (pos 0)

Solution

1. Step 1: Analyze loop range for traversal

   The loop runs from 0 to pos, moving current to node at pos, not previous node needed for deletion.

2. Step 2: Check head deletion handling

   Function does not handle pos 0 case, so head pointer is never updated if first node is deleted.

3. Step 3: Summarize all issues

   Loop skips previous node, no head update on pos 0, so all listed bugs exist.

4. Final Answer:

   All of the above -> Option A

5. Quick Check:

   Loop and head update bugs = All above [OK]

Hint: Check loop range and head update for deletion [OK]

Common Mistakes:

• Looping to node instead of previous node
• Ignoring deletion of head node
• Not updating head pointer on deletion

5. Given a singly linked list with nodes: 5 -> 15 -> 25 -> 35 -> 45 -> null, write a Rust function to delete the node at position 3 (0-based). What will be the final list after deletion? Choose the correct final list output.

medium

A. 5 -> 15 -> 35 -> 45 -> null

B. 5 -> 15 -> 25 -> 35 -> null

C. 15 -> 25 -> 35 -> 45 -> null

D. 5 -> 15 -> 25 -> 45 -> null

Solution

1. Step 1: Identify node at position 3

   Position 3 node has value 35 in list 5 -> 15 -> 25 -> 35 -> 45 -> null.

2. Step 2: Delete node 35 and link 25 to 45

   After deletion, list becomes 5 -> 15 -> 25 -> 45 -> null.

3. Final Answer:

   5 -> 15 -> 25 -> 45 -> null -> Option D

4. Quick Check:

   Deleted node 35 at pos 3 [OK]

Hint: Delete node at pos and link neighbors [OK]

Common Mistakes:

• Deleting wrong position node
• Not linking previous node to next
• Confusing 0-based indexing