Delete Node at Specific Position in DSA Rust

Mental Model

We remove a node from a linked list by changing the pointer of the node before it to skip over the node to delete.

Analogy: Imagine a chain of paper clips linked together. To remove one clip in the middle, you unhook the clip before it and connect it directly to the clip after it, skipping the one you want to remove.

head -> 1 -> 2 -> 3 -> 4 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> null, delete node at position 2 (0-based)

Goal: Remove the node at position 2 so the list becomes 1 -> 2 -> 4 -> null

Step 1: Check if position is 0, if yes remove head; here position is 2, so continue

head -> 1 -> 2 -> 3 -> 4 -> null

Why: We handle removing the first node differently because it changes the head

Step 2: Start at head (node 1), move to node before target (position 1, node 2)

head -> 1 -> [curr->2] -> 3 -> 4 -> null

Why: We need the node before the one to delete to change its pointer

Step 3: Change curr.next from node 3 to node 4, skipping node 3

head -> 1 -> 2 -> 4 -> null

Why: By skipping node 3, it is removed from the list

Result:

head -> 1 -> 2 -> 4 -> null

Annotated Code

DSA Rust

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

#[derive(Debug, Clone)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

fn print_list(head: &Option<Rc<RefCell<Node>>>) {
    let mut curr = head.clone();
    while let Some(node) = curr {
        print!("{} -> ", node.borrow().val);
        curr = node.borrow().next.clone();
    }
    println!("null");
}

fn delete_at_position(head: &mut Option<Rc<RefCell<Node>>>, pos: usize) {
    if head.is_none() {
        return; // empty list, nothing to delete
    }

    if pos == 0 {
        // remove head
        let next = head.as_ref().unwrap().borrow().next.clone();
        *head = next;
        return;
    }

    let mut curr = head.clone();
    let mut index = 0;

    // move to node before the one to delete
    while index < pos - 1 {
        if let Some(node) = curr.clone() {
            let next = node.borrow().next.clone();
            if next.is_none() {
                return; // position out of bounds
            }
            curr = next;
        } else {
            return; // position out of bounds
        }
        index += 1;
    }

    if let Some(node) = curr {
        let next = node.borrow().next.clone();
        if let Some(next_node) = next {
            let next_next = next_node.borrow().next.clone();
            node.borrow_mut().next = next_next;
        }
    }
}

fn main() {
    // Create list 1 -> 2 -> 3 -> 4 -> null
    let n1 = Node::new(1);
    let n2 = Node::new(2);
    let n3 = Node::new(3);
    let n4 = Node::new(4);

    n1.borrow_mut().next = Some(n2.clone());
    n2.borrow_mut().next = Some(n3.clone());
    n3.borrow_mut().next = Some(n4.clone());

    let mut head = Some(n1.clone());

    println!("Original list:");
    print_list(&head);

    delete_at_position(&mut head, 2);

    println!("After deleting node at position 2:");
    print_list(&head);
}

if pos == 0 { // remove head let next = head.as_ref().unwrap().borrow().next.clone(); *head = next; return; }

handle removing the first node by updating head pointer

while index < pos - 1 { if let Some(node) = curr.clone() { let next = node.borrow().next.clone(); if next.is_none() { return; // position out of bounds } curr = next; } else { return; // position out of bounds } index += 1; }

move curr to node before the one to delete, checking bounds

if let Some(node) = curr { let next = node.borrow().next.clone(); if let Some(next_node) = next { let next_next = next_node.borrow().next.clone(); node.borrow_mut().next = next_next; } }

skip the node at position by linking curr.next to curr.next.next

Output

Original list:

1 -> 2 -> 3 -> 4 -> null

After deleting node at position 2:

1 -> 2 -> 4 -> null

Complexity Analysis

Time: O(n) because we may need to traverse up to n nodes to reach the position

Space: O(1) because we only use a few pointers and no extra data structures

vs Alternative: Compared to rebuilding the list or copying nodes, this approach changes pointers directly for efficient deletion

Edge Cases

empty list

function returns immediately, no deletion

DSA Rust

if head.is_none() { return; }

delete head node (position 0)

head pointer updated to next node

DSA Rust

if pos == 0 { ... *head = next; return; }

position out of bounds (greater than list length)

function returns without changes

DSA Rust

if next.is_none() { return; }

When to Use This Pattern

When you need to remove a node from a linked list at a given position, use pointer updates to skip the node, because linked lists allow efficient removal without shifting elements.

Common Mistakes

Mistake: Trying to delete the node by copying values instead of changing pointers
Fix: Change the previous node's next pointer to skip the node to delete

Mistake: Not handling deletion of the head node separately
Fix: Check if position is zero and update head pointer accordingly

Mistake: Not checking if position is out of bounds causing runtime errors
Fix: Add checks to return early if position is invalid

Summary

Deletes a node at a specific position in a singly linked list by changing pointers.

Use when you want to remove an element from anywhere in a linked list efficiently.

The key is to find the node before the target and link it to the node after the target, skipping the target node.

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