Delete Node at Specific Position in DSA Rust - Execution Trace

Concept Flow - Delete Node at Specific Position

Start at head

↓

Check if position is 0

|Yes↓

Delete head node

No↓

Traverse to node before position

↓

Check if next node exists

|No↓

Position out of range, stop

Yes↓

Change next pointer to skip node

Start from the head, if position is zero delete head. Otherwise, move to node before position, then skip the node at position by changing pointers.

Execution Sample

DSA Rust

fn delete_at_position(head: &mut Option<Box<Node>>, 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 {
        current = current.and_then(|node| node.next.as_mut());
    }
    if let Some(node) = current {
        node.next = node.next.take().and_then(|next_node| next_node.next);
    }
}

Deletes the node at the given position in a singly linked list by adjusting pointers.

Execution Table

Step	pos	current position	Action	List State
1	2	start at head (pos 0)	Check if pos == 0 (No)	1 -> 2 -> 3 -> 4 -> null
2	2	move to pos 0 node	current points to node with value 1	1 -> 2 -> 3 -> 4 -> null
3	2	move to pos 1 node	current points to node with value 2	1 -> 2 -> 3 -> 4 -> null
4	2	at node before pos 2	Check if next node exists (Yes)	1 -> 2 -> 3 -> 4 -> null
5	2	at node before pos 2	Skip node at pos 2 by linking node 2 to node 4	1 -> 2 -> 4 -> null
6	2	end	Deletion complete	1 -> 2 -> 4 -> null

💡 Reached node before position, skipped node at position, list updated

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	Final
pos	2	2	2	2	2
current	head (node 1)	node 1	node 2	node 2	node 2
list	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 4 -> null	1 -> 2 -> 4 -> null

Key Moments - 3 Insights

Why do we stop at the node before the position instead of the node at the position?

Because to delete a node, we need to change the previous node's next pointer to skip the node at the position. This is shown in step 4 and 5 of the execution_table.

What happens if the position is 0?

If position is 0, we delete the head node by making head point to the next node. This is handled at step 1 in the concept_flow and code.

What if the position is out of range?

If the next node does not exist when we try to skip, we do nothing because the position is invalid. This is checked in step 4 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the list state after step 5?

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

B 1 -> 2 -> 4 -> null

C 2 -> 3 -> 4 -> null

D 1 -> 3 -> 4 -> null

💡 Hint

Check the 'List State' column at step 5 in the execution_table.

At which step does the current pointer move to the node with value 2?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'current position' column in the execution_table to see when current points to node 2.

If pos was 0, what would be the list state after deletion?

A 1 -> 3 -> 4 -> null

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

C 2 -> 3 -> 4 -> null

D 3 -> 4 -> null

💡 Hint

Refer to the concept_flow and code where pos == 0 deletes the head node.

Concept Snapshot

Delete Node at Specific Position:
- If position is 0, remove head by pointing head to next node.
- Else, move to node before position.
- Change its next pointer to skip the node at position.
- If position out of range, do nothing.
- Works on singly linked lists by pointer adjustment.

Full Transcript

To delete a node at a specific position in a singly linked list, first check if the position is zero. If yes, remove the head node by making the head point to the next node. Otherwise, traverse the list to reach the node just before the target position. Then, adjust its next pointer to skip the node at the position, effectively deleting it. If the position is beyond the list length, no changes are made. This process ensures the list remains connected without the deleted 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