Insert at End of Doubly Linked List in DSA Rust

Mental Model

Add a new item at the very end of a list where each item knows both its previous and next neighbors.

Analogy: Imagine a train where each car is connected to the one before and after it. Adding a new car means hooking it to the last car and updating the last car to point to the new one.

null ← 1 ↔ 2 ↔ 3 -> null

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at end

Goal: Add the value 4 as the new last node in the doubly linked list

Step 1: Create new node with value 4

null ← 1 ↔ 2 ↔ 3 -> null   [new node: 4 (isolated)]

Why: We need a new node to add to the list

Step 2: Traverse from head to last node (3)

null ← 1 ↔ 2 ↔ [3 ↑] -> null   new node: 4

Why: We must find the last node to attach the new node after it

Step 3: Set last node's next pointer to new node

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

Why: Link last node to new node to extend the list

Step 4: Set new node's previous pointer to last node

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

Why: Link new node back to last node to maintain two-way connection

Result:

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> 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 insert_at_end(&mut self, val: i32) {
        let new_node = Node::new(val);
        match self.head.clone() {
            None => {
                self.head = Some(new_node);
            }
            Some(mut current) => {
                // advance to last node
                while let Some(next) = current.borrow().next.clone() {
                    current = next;
                }
                // link last node's next to new node
                current.borrow_mut().next = Some(new_node.clone());
                // link new node's prev to last node
                new_node.borrow_mut().prev = Some(current);
            }
        }
    }

    fn print_forward(&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 list = DoublyLinkedList::new();
    list.insert_at_end(1);
    list.insert_at_end(2);
    list.insert_at_end(3);
    list.insert_at_end(4);
    list.print_forward();
}

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

advance current to last node by following next pointers

current.borrow_mut().next = Some(new_node.clone());

link last node's next pointer to new node

new_node.borrow_mut().prev = Some(current);

link new node's prev pointer back to last node

Output

1 ↔ 2 ↔ 3 ↔ 4

Complexity Analysis

Time: O(n) because we must traverse all nodes to reach the end

Space: O(1) because we only create one new node and use constant extra space

vs Alternative: Compared to inserting at the head which is O(1), inserting at the end requires traversal making it O(n)

Edge Cases

empty list

new node becomes the head with no prev or next

DSA Rust

self.head = Some(new_node);

single element list

new node is linked after the single node, prev and next pointers updated

DSA Rust

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

When to Use This Pattern

When you need to add an item at the end of a list that allows backward and forward navigation, use this pattern to maintain both links correctly.

Common Mistakes

Mistake: Forgetting to update the new node's prev pointer to point back to the last node
Fix: Always set new_node.prev = last node after linking last node's next to new_node

Mistake: Not handling the empty list case, causing a crash or no insertion
Fix: Check if head is None and set head to new node directly

Summary

Adds a new node at the end of a doubly linked list, updating both next and prev pointers.

Use when you want to append data to the tail of a list that supports two-way traversal.

The key is to find the last node, link its next to the new node, and link the new node's prev back to it.

Practice

1. What is the main purpose of inserting a node at the end of a doubly linked list?

easy

A. To reverse the list

B. To remove the first node

C. To add a new element after the last node

D. To find the middle node

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes connected forward and backward, allowing traversal in both directions.

2. Step 2: Purpose of insertion at the end

   Inserting at the end means adding a new node after the current last node, updating pointers accordingly.

3. Final Answer:

   To add a new element after the last node -> Option C

4. Quick Check:

   Insert at end = add after last node [OK]

Hint: Insert at end means add after last node [OK]

Common Mistakes:

• Confusing insertion at end with deletion
• Thinking insertion reverses the list
• Assuming insertion happens at the start

2. Which Rust code snippet correctly creates a new node and inserts it at the end of a doubly linked list?

easy

A. let new_node = Node::new(value); new_node.prev = Some(head); head.next = Some(new_node);

B. let new_node = Node::new(value); head.prev = Some(new_node); new_node.next = Some(head);

C. let new_node = Node::new(value); new_node.next = Some(tail); tail.prev = Some(new_node);

D. let new_node = Node::new(value); tail.next = Some(new_node); new_node.prev = Some(tail);

Solution

1. Step 1: Create new node with given value

   Use Node::new(value) to create a new node.

2. Step 2: Link new node after tail

   Set tail.next to new_node and new_node.prev to tail to insert at end.

3. Final Answer:

   let new_node = Node::new(value); tail.next = Some(new_node); new_node.prev = Some(tail); -> Option D

4. Quick Check:

   New node after tail = let new_node = Node::new(value); tail.next = Some(new_node); new_node.prev = Some(tail); [OK]

Hint: New node's prev points to tail; tail's next points to new node [OK]

Common Mistakes:

• Linking new node before head instead of after tail
• Swapping next and prev pointers incorrectly
• Not updating tail's next pointer

3. Given the Rust code below, what will be the printed list after inserting 4 at the end?

struct Node {
    value: i32,
    prev: Option,
    next: Option,
}

// Assume list initially: 1 <-> 2 <-> 3
// Insert 4 at end
// Print list from head to tail

medium

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

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

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

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

Solution

1. Step 1: Understand initial list structure

   The list is 1 linked to 2, linked to 3, with 3 as tail.

2. Step 2: Insert 4 at the end

   Adding 4 after 3 updates 3.next to 4 and 4.prev to 3.

3. Final Answer:

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

4. Quick Check:

   Insert at end adds 4 after 3 [OK]

Hint: New node appears after last node in printed list [OK]

Common Mistakes:

• Inserting new node at start instead of end
• Not updating next pointer of last node
• Printing list without new node

4. Identify the error in this Rust code snippet for inserting at the end of a doubly linked list:

fn insert_end(tail: &mut Option, value: i32) {
    let mut new_node = Box::new(Node::new(value));
    new_node.prev = tail.clone();
    tail = Some(new_node);
}

medium

A. tail is not updated correctly; should update tail's next pointer

B. new_node.prev should be None for end insertion

C. new_node should not be boxed

D. value should be mutable

Solution

1. Step 1: Check pointer updates

   tail is reassigned locally, but tail's next pointer is not updated to link new_node.

2. Step 2: Correct linking needed

   Must set tail's next to new_node and new_node.prev to tail, then update tail reference.

3. Final Answer:

   tail is not updated correctly; should update tail's next pointer -> Option A

4. Quick Check:

   Update tail.next to new_node [OK]

Hint: Always update tail's next pointer when inserting at end [OK]

Common Mistakes:

• Only reassigning tail without linking nodes
• Setting prev pointer incorrectly
• Ignoring ownership rules in Rust

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30. You want to insert 25 at the end but also keep a pointer to the middle node for quick access. After insertion, which node should the middle pointer reference to keep it as the middle of the list?

hard

A. 25

B. 20

C. 30

D. 10

Solution

1. Step 1: Understand list before insertion

   List is 10 <-> 20 <-> 30; middle is 20 (second of three nodes).

2. Step 2: Insert 25 at end and find new middle

   List becomes 10 <-> 20 <-> 30 <-> 25. With 4 nodes, middle is between 20 and 30, usually the second node (20) to keep balance.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   Middle of 4 nodes = 2nd node [OK]

Hint: Middle of even nodes is lower middle [OK]

Common Mistakes:

• Moving middle pointer to last inserted node
• Choosing last node as middle
• Not updating middle pointer after insertion