Insert at Specific Position in Doubly Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting at position 2 in a doubly linked list

What is the printed state of the doubly linked list after inserting the value 99 at position 2?

DSA Rust

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

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

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

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

    fn insert_at(&mut self, data: i32, position: usize) {
        if position == 0 {
            let mut new_node = Box::new(Node { data, prev: None, next: self.head.take() });
            self.head = Some(new_node);
            return;
        }

        let mut current = self.head.as_mut();
        let mut index = 0;

        while let Some(node) = current {
            if index + 1 == position {
                let next = node.next.take();
                let mut new_node = Box::new(Node { data, prev: None, next });
                node.next = Some(new_node);
                break;
            }
            current = node.next.as_mut();
            index += 1;
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        let mut result = String::new();
        while let Some(node) = current {
            result.push_str(&format!("{} <-> ", node.data));
            current = node.next.as_ref();
        }
        result.push_str("null");
        println!("{}", result);
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.append(10);
    dll.append(20);
    dll.append(30);
    dll.insert_at(99, 2);
    dll.print_list();
}

A 10 <-> 99 <-> 20 <-> 30 <-> null

B 10 <-> 20 <-> 99 <-> 30 <-> null

C 99 <-> 10 <-> 20 <-> 30 <-> null

D 10 <-> 20 <-> 30 <-> 99 <-> null

💡 Hint

Remember that position 2 means after the second element (0-based indexing).

Inserting at position 2 places the new node after the second node (which has value 20). So the list becomes 10 <-> 20 <-> 99 <-> 30 <-> null.

❓ Predict Output

intermediate

Output after inserting at head (position 0) in doubly linked list

What is the printed state of the doubly linked list after inserting the value 5 at position 0?

DSA Rust

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

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

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

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

    fn insert_at(&mut self, data: i32, position: usize) {
        if position == 0 {
            let mut new_node = Box::new(Node { data, prev: None, next: self.head.take() });
            self.head = Some(new_node);
            return;
        }

        let mut current = self.head.as_mut();
        let mut index = 0;

        while let Some(node) = current {
            if index + 1 == position {
                let next = node.next.take();
                let mut new_node = Box::new(Node { data, prev: None, next });
                node.next = Some(new_node);
                break;
            }
            current = node.next.as_mut();
            index += 1;
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        let mut result = String::new();
        while let Some(node) = current {
            result.push_str(&format!("{} <-> ", node.data));
            current = node.next.as_ref();
        }
        result.push_str("null");
        println!("{}", result);
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.append(10);
    dll.append(20);
    dll.append(30);
    dll.insert_at(5, 0);
    dll.print_list();
}

A 5 <-> 20 <-> 10 <-> 30 <-> null

B 10 <-> 20 <-> 30 <-> 5 <-> null

C 5 <-> 10 <-> 20 <-> 30 <-> null

D 10 <-> 5 <-> 20 <-> 30 <-> null

💡 Hint

Inserting at position 0 means adding at the start of the list.

The new node with value 5 becomes the head, so the list is 5 <-> 10 <-> 20 <-> 30 <-> null.

🔧 Debug

advanced

Identify the error in insert_at method for doubly linked list

What error will occur when running this insert_at method if we try to insert at position 1 in a list with one element?

DSA Rust

fn insert_at(&mut self, data: i32, position: usize) {
    if position == 0 {
        let mut new_node = Box::new(Node { data, prev: None, next: self.head.take() });
        if let Some(ref mut next_node) = new_node.next {
            next_node.prev = Some(new_node.clone());
        }
        self.head = Some(new_node);
        return;
    }

    let mut current = self.head.as_mut();
    let mut index = 0;

    while let Some(node) = current {
        if index + 1 == position {
            let next = node.next.take();
            let mut new_node = Box::new(Node { data, prev: None, next });
            if let Some(ref mut next_node) = new_node.next {
                next_node.prev = Some(new_node.clone());
            }
            node.next = Some(new_node);
            break;
        }
        current = node.next.as_mut();
        index += 1;
    }
}

A Logic error: new_node.prev is never set to point to current node

B Runtime error due to cloning Box<Node> which is not allowed

C Syntax error: missing semicolon after node.next = Some(new_node)

D No error; code runs correctly

💡 Hint

Check if the prev pointer of the new node is assigned properly.

The new node's prev pointer is never set to the current node, so the backward link is broken causing incorrect doubly linked list structure.

🧠 Conceptual

advanced

Effect of inserting at position greater than list length

What happens if you try to insert a node at position 10 in a doubly linked list that currently has 3 nodes?

A No insertion happens; the list remains unchanged

B The node is appended at the end of the list

C The node is inserted at position 3 (end) silently

D Runtime error due to out-of-bounds position

💡 Hint

Consider how the insert_at method traverses the list and what happens if position is beyond length.

The method traverses nodes but does not insert if position is beyond list length, so the list remains unchanged.

❓ Predict Output

expert

Final list after multiple insertions at various positions

Given the following operations on an empty doubly linked list, what is the final printed list? Operations: - insert_at(1, 0) - insert_at(2, 1) - insert_at(3, 1) - insert_at(4, 3) - insert_at(5, 10) Assume insert_at does not insert if position is out of bounds.

DSA Rust

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

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

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

    fn insert_at(&mut self, data: i32, position: usize) {
        if position == 0 {
            let mut new_node = Box::new(Node { data, prev: None, next: self.head.take() });
            self.head = Some(new_node);
            return;
        }

        let mut current = self.head.as_mut();
        let mut index = 0;

        while let Some(node) = current {
            if index + 1 == position {
                let next = node.next.take();
                let mut new_node = Box::new(Node { data, prev: None, next });
                node.next = Some(new_node);
                return;
            }
            current = node.next.as_mut();
            index += 1;
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        let mut result = String::new();
        while let Some(node) = current {
            result.push_str(&format!("{} <-> ", node.data));
            current = node.next.as_ref();
        }
        result.push_str("null");
        println!("{}", result);
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.insert_at(1, 0);
    dll.insert_at(2, 1);
    dll.insert_at(3, 1);
    dll.insert_at(4, 3);
    dll.insert_at(5, 10);
    dll.print_list();
}

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

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

C 1 <-> 3 <-> 2 <-> 4 <-> 5 <-> null

D 1 <-> 3 <-> 2 <-> 4 <-> null

💡 Hint

Trace each insertion step carefully and note that insertion at position 10 does nothing.

Insertions happen as follows: - insert_at(1,0): list = 1 - insert_at(2,1): list = 1 <-> 2 - insert_at(3,1): list = 1 <-> 3 <-> 2 - insert_at(4,3): list = 1 <-> 3 <-> 2 <-> 4 - insert_at(5,10): position out of bounds, no insertion Final list: 1 <-> 3 <-> 2 <-> 4 <-> null

Practice

1. What does inserting at a specific position in a doubly linked list involve?

easy

A. Adjusting the previous and next pointers of nodes around the position

B. Only changing the head pointer of the list

C. Reversing the entire list before insertion

D. Deleting the node at that position first

Solution

1. Step 1: Understand doubly linked list node connections

   Each node has pointers to both previous and next nodes, so insertion requires updating these pointers around the insertion point.

2. Step 2: Adjust pointers for insertion

   To insert at a specific position, update the previous node's next pointer and the next node's previous pointer to point to the new node.

3. Final Answer:

   Adjusting the previous and next pointers of nodes around the position -> Option A

4. Quick Check:

   Pointer updates = Adjust previous and next pointers [OK]

Hint: Remember: update both previous and next pointers [OK]

Common Mistakes:

• Only updating one pointer and ignoring the other
• Not handling edge cases like inserting at head or tail
• Forgetting to update the new node's pointers

2. Which Rust code snippet correctly declares a doubly linked list node struct for insertion?

easy

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

B. struct Node { data: i32, prev: Option<*mut Node>, next: Option<*mut Node> }

C. struct Node { data: i32, prev: Option, next: Option }

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

Solution

1. Step 1: Understand Rust ownership for doubly linked lists

   Doubly linked lists require shared ownership and mutability, so Rc is used to allow multiple owners and interior mutability.

2. Step 2: Identify correct pointer types

   Option> allows optional pointers with shared ownership and mutability, suitable for prev and next pointers.

3. Final Answer:

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

4. Quick Check:

   Use Rc<RefCell> for shared mutable pointers [OK]

Hint: Use Rc<RefCell> for doubly linked list nodes in Rust [OK]

Common Mistakes:

• Using Box without Rc causes ownership errors
• Using raw pointers without unsafe code
• Not wrapping pointers in Option for nullable links

3. Given this Rust code snippet inserting a node at position 2 in a doubly linked list with nodes 1 <-> 3, what is the list after insertion of node 2?

medium

A. 3 <-> 2 <-> 1

B. 2 <-> 1 <-> 3

C. 1 <-> 2 <-> 3

D. 1 <-> 3 <-> 2

Solution

1. Step 1: Identify insertion position and existing list

   The list is 1 <-> 3, and we insert node 2 at position 2, meaning after node 1 and before node 3.

2. Step 2: Insert node 2 between nodes 1 and 3

   Update node 1's next to node 2, node 2's prev to node 1, node 2's next to node 3, and node 3's prev to node 2.

3. Final Answer:

   1 <-> 2 <-> 3 -> Option C

4. Quick Check:

   Insert at position 2 places node 2 between 1 and 3 [OK]

Hint: Insert node between previous and next nodes at position [OK]

Common Mistakes:

• Inserting node at wrong position
• Not updating both prev and next pointers
• Confusing position indexing starting at 0 or 1

4. In this Rust code for inserting at position 3, the program panics with 'index out of bounds'. What is the likely cause?

medium

A. The new node's pointers are not initialized

B. The list has fewer than 2 nodes, so position 3 is invalid

C. The head pointer is null

D. The insertion code forgets to update the tail pointer

Solution

1. Step 1: Analyze the error message and position

   The panic 'index out of bounds' means the code tried to access a position beyond the list length. Position 3 requires at least 2 nodes before it.

2. Step 2: Check list length against insertion position

   If the list has fewer than 2 nodes, position 3 is invalid, causing the panic.

3. Final Answer:

   The list has fewer than 2 nodes, so position 3 is invalid -> Option B

4. Quick Check:

   Position > list length causes index out of bounds [OK]

Hint: Check list length before inserting at position [OK]

Common Mistakes:

• Not validating position against list length
• Assuming tail pointer updates fix index errors
• Ignoring null or empty list cases

5. You have a doubly linked list with nodes 10 <-> 20 <-> 30. Write the steps to insert a node with value 25 at position 3 and show the final list.

hard

A. 25 <-> 10 <-> 20 <-> 30

B. 10 <-> 25 <-> 20 <-> 30

C. 10 <-> 20 <-> 30 <-> 25

D. 10 <-> 20 <-> 25 <-> 30

Solution

1. Step 1: Locate position 3 in the list

   Position 3 means the new node goes after the second node (20) and before the third node (30).

2. Step 2: Update pointers to insert node 25

   Set node 20's next to new node 25, new node 25's prev to node 20, new node 25's next to node 30, and node 30's prev to new node 25.

3. Final Answer:

   10 <-> 20 <-> 25 <-> 30 -> Option D

4. Quick Check:

   Insert at position 3 places 25 between 20 and 30 [OK]

Hint: Insert between nodes at position - 1 and position [OK]

Common Mistakes:

• Inserting node at wrong position
• Not updating both prev and next pointers correctly
• Confusing position indexing starting at 0 or 1