Insert at End of Doubly Linked List in DSA Rust - Execution Trace

Concept Flow - Insert at End of Doubly Linked List

Create new node with data

↓

Is list empty?

↓

Set head = new, tail = new

↓

Done

↓

new.prev = tail

↓

Update tail = new

↓

Done

Create a new node, check if list is empty. If empty, set head and tail to new node. Otherwise, link new node after tail and update tail pointer.

Execution Sample

DSA Rust

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

// Insert new node at end

Node structure definition for doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=40	10 <-> 20 <-> 30	new_node.prev = None, new_node.next = None	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │ │ prev:──┼──→ │ prev:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
2	Check if list empty	10 <-> 20 <-> 30	No change	Same as step 1
3	Start at tail node (30)	10 <-> 20 <-> 30	current = tail (node 30)	Same as step 1
4	Link new node after tail	10 <-> 20 <-> 30 <-> 40	tail.next = new_node, new_node.prev = tail	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │ │ prev:──┼──→ │ prev:──┼──→ │ prev:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head tail new tail
5	Update tail pointer to new node	10 <-> 20 <-> 30 <-> 40	tail = new_node	Same as step 4
6	Done	10 <-> 20 <-> 30 <-> 40	No change	Final list state as step 5

💡 Insertion complete, new node added at end and tail updated

Variable Tracker

Variable	Start	After Step 1	After Step 4	Final
head	Node(10)	Node(10)	Node(10)	Node(10)
tail	Node(30)	Node(30)	Node(30)	Node(40)
new_node	None	Node(40)	Node(40)	Node(40)
current	None	None	Node(30)	Node(30)

Key Moments - 3 Insights

Why do we need to update the new node's prev pointer?

Because the new node must point back to the old tail to maintain the doubly linked structure, as shown in step 4 where new_node.prev = tail.

What happens if the list is empty when inserting?

If empty, we set head and tail to the new node directly, skipping traversal. This is shown in the concept flow but not in this example since list was not empty.

Why do we update the tail pointer after insertion?

Because the new node becomes the last node, so tail must point to it. Step 5 shows tail = new_node.

Visual Quiz - 3 Questions

Look at the execution table, what is the tail pointer after step 4?

A Node with data 40

B Node with data 30

C Node with data 20

D None

💡 Hint

Check 'tail' variable in variable_tracker after step 4

At which step does the new node get linked after the tail?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at 'Operation' and 'Pointer Changes' columns in execution_table

If the list was empty, which pointer would be set to the new node first?

A tail

B current

C head

D new_node.prev

💡 Hint

Refer to concept_flow where empty list sets head = new node

Concept Snapshot

Insert at End of Doubly Linked List:
- Create new node with data
- If list empty: head = tail = new node
- Else: tail.next = new node, new_node.prev = tail
- Update tail pointer to new node
- Maintains forward and backward links

Full Transcript

To insert at the end of a doubly linked list, first create a new node with the given data. Check if the list is empty. If it is, set both head and tail to this new node. If not empty, start at the tail node, link the new node after it by setting tail.next to new node and new_node.prev to tail. Then update the tail pointer to the new node. This keeps the list connected in both directions. The execution table shows each step and how pointers change, with the final list having the new node at the end.

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