DSA Rustprogramming

Insert at Specific Position in Doubly Linked List in DSA Rust

Choose your learning style10 modes available

Learn Why Deep Visual Try Challenge Project Recall Time

Mental Model

A doubly linked list lets you move forward and backward through nodes. To insert at a position, you find that spot and link the new node between its neighbors.

Analogy: Imagine a train with cars connected front and back. To add a new car in the middle, you disconnect the two cars at that spot and connect the new car between them.

null ← 1 ↔ 2 ↔ 3 -> null
           ↑ (head)

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at position 2 (0-based index)

Goal: Insert the value 4 between nodes 2 and 3, so the list becomes 1 ↔ 2 ↔ 4 ↔ 3

Step 1: start at head node 1

null ← [1] ↔ 2 ↔ 3 -> null

Why: We begin traversal from the head to find the insertion point

Step 2: move to node 2 (position 1)

null ← 1 ↔ [2] ↔ 3 -> null

Why: We advance to the node before the insertion position

Step 3: create new node 4 and link it after node 2

null ← 1 ↔ 2 ↔ [4] ↔ 3 -> null

Why: Insert new node by adjusting pointers between node 2 and node 3

Result:

null ← 1 ↔ 2 ↔ 4 ↔ 3 -> null

Annotated Code

DSA Rust

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

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

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

struct DoublyLinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

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

    fn append(&mut self, val: i32) {
        let new_node = Node::new(val);
        match self.head.clone() {
            None => self.head = Some(new_node),
            Some(head) => {
                let mut tail = head.clone();
                while let Some(next) = tail.borrow().next.clone() {
                    tail = next;
                }
                tail.borrow_mut().next = Some(new_node.clone());
                new_node.borrow_mut().prev = Some(tail);
            }
        }
    }

    fn insert_at_position(&mut self, val: i32, pos: usize) {
        let new_node = Node::new(val);
        if pos == 0 {
            if let Some(head) = self.head.take() {
                new_node.borrow_mut().next = Some(head.clone());
                head.borrow_mut().prev = Some(new_node.clone());
            }
            self.head = Some(new_node);
            return;
        }

        let mut current = match self.head.clone() {
            None => return, // empty list, do nothing
            Some(node) => node,
        };

        let mut index = 0;
        while index < pos - 1 {
            let next = current.borrow().next.clone();
            match next {
                Some(next_node) => current = next_node,
                None => return, // position out of bounds
            }
            index += 1;
        }

        let next_node = current.borrow().next.clone();
        current.borrow_mut().next = Some(new_node.clone());
        new_node.borrow_mut().prev = Some(current.clone());
        new_node.borrow_mut().next = next_node.clone();
        if let Some(next) = next_node {
            next.borrow_mut().prev = Some(new_node.clone());
        }
    }

    fn print_list(&self) {
        let mut current = self.head.clone();
        while let Some(node) = current {
            print!("{}", node.borrow().val);
            current = node.borrow().next.clone();
            if current.is_some() {
                print!(" ↔ ");
            }
        }
        println!();
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.append(1);
    dll.append(2);
    dll.append(3);
    dll.insert_at_position(4, 2);
    dll.print_list();
}

while let Some(next) = tail.borrow().next.clone() {
    tail = next;
}

advance tail to last node to append new node

tail.borrow_mut().next = Some(new_node.clone());
new_node.borrow_mut().prev = Some(tail);

link new node after tail for append

if pos == 0 {
    if let Some(head) = self.head.take() {
        new_node.borrow_mut().next = Some(head.clone());
        head.borrow_mut().prev = Some(new_node.clone());
    }
    self.head = Some(new_node);
    return;
}

handle insertion at head by adjusting pointers

while index < pos - 1 {
    let next = current.borrow().next.clone();
    match next {
        Some(next_node) => current = next_node,
        None => return,
    }
    index += 1;
}

traverse to node before insertion position

let next_node = current.borrow().next.clone();
current.borrow_mut().next = Some(new_node.clone());
new_node.borrow_mut().prev = Some(current.clone());
new_node.borrow_mut().next = next_node.clone();
if let Some(next) = next_node {
    next.borrow_mut().prev = Some(new_node.clone());
}

insert new node by linking it between current and next_node

OutputSuccess

1 ↔ 2 ↔ 4 ↔ 3

Complexity Analysis

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

Space: O(1) because insertion uses a fixed amount of extra space for the new node

vs Alternative: Compared to arrays, doubly linked lists allow insertion without shifting elements, making insertion O(1) once position is found, but finding position is O(n)

Edge Cases

empty list

inserting at position 0 sets new node as head; other positions do nothing

DSA Rust

if pos == 0 { ... } and match self.head.clone() { None => return }

insert at head (position 0)

new node becomes new head, old head's prev pointer updated

DSA Rust

if pos == 0 { ... }

position out of bounds (greater than list length)

insertion is ignored, list remains unchanged

DSA Rust

match next { None => return }

When to Use This Pattern

When you need to insert or remove elements at any position in a list and want efficient backward and forward traversal, use a doubly linked list insertion pattern.

Common Mistakes

Mistake: Not updating the prev pointer of the node after the inserted node
Fix: Always update the next node's prev pointer to point back to the new node

Mistake: Not handling insertion at position 0 (head) separately
Fix: Add a special case to update head pointer and prev of old head

Summary

Inserts a new node at a given position in a doubly linked list by adjusting next and prev pointers.

Use when you want to add elements anywhere in a doubly linked list efficiently.

The key is to link the new node between its previous and next nodes, updating all pointers carefully.

Practice

(1/5)

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

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Insert at Specific Position in Doubly Linked List in DSA Rust

Practice

Solution

Step 1: Understand doubly linked list node connections

Step 2: Adjust pointers for insertion

Final Answer:

Quick Check:

Solution

Step 1: Understand Rust ownership for doubly linked lists

Step 2: Identify correct pointer types

Final Answer:

Quick Check:

Solution

Step 1: Identify insertion position and existing list

Step 2: Insert node 2 between nodes 1 and 3

Final Answer:

Quick Check:

Solution

Step 1: Analyze the error message and position

Step 2: Check list length against insertion position

Final Answer:

Quick Check:

Solution

Step 1: Locate position 3 in the list

Step 2: Update pointers to insert node 25

Final Answer:

Quick Check:

Ready to prove it?