Reverse a Doubly Linked List in DSA Rust - Build from Scratch

Reverse a Doubly Linked List

📖 Scenario: Imagine you have a list of train cars connected in order. Each car knows the car before it and the car after it. Sometimes, you want to reverse the order of the cars so the last car becomes the first and the first becomes the last.

🎯 Goal: You will build a doubly linked list in Rust using indices and then reverse it so the order of the nodes is flipped. Finally, you will print the reversed list to see the new order.

📋 What You'll Learn

Create a doubly linked list with exact nodes and values using Vec and indices

Add a helper variable to track the current node index

Write the logic to reverse the doubly linked list by swapping indices

Print the reversed list in order from head to tail

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in applications like music players to move forward and backward through songs, or in browsers to navigate back and forth between pages.

💼 Career

Understanding how to manipulate linked lists is important for software engineers working on low-level data structures, memory management, and performance-critical applications.

1

Create the doubly linked list

Create a struct called Node with fields value: i32, prev: Option<usize>, and next: Option<usize>. Then create a mutable Vec<Node> called nodes and link three nodes with values 1, 2, and 3 using indices 0 <-> 1 <-> 2. Store the head index in a mutable variable called head.

DSA Rust

// Define Node struct and create Vec with linked indices 0  1  2
// Your code here

Hint

Define the Node struct with usize indices for prev and next. Create let mut nodes = vec![], push nodes, and set bidirectional links using indices.

2

Add a helper variable for traversal

Add a mutable variable called current and set it equal to Some(head). This will help us move through the list while reversing.

DSA Rust

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

fn main() {
    let mut nodes = vec![];
    nodes.push(Node { value: 1, prev: None, next: None });
    let mut head: usize = 0;
    nodes[head].next = Some(1);
    nodes.push(Node { value: 2, prev: Some(head), next: None });
    nodes[1].next = Some(2);
    nodes.push(Node { value: 3, prev: Some(1), next: None });

    // Create a mutable variable current to start at head
    // Your code here
}

Hint

Use let mut current = Some(head); to start traversal from the head index.

3

Reverse the doubly linked list

Declare let mut new_head = None; Write a while loop that runs while current is Some(node). Inside the loop, swap the prev and next indices of nodes[node] using take(). If nodes[node].prev is None after swap, set new_head = Some(node). Move current to nodes[node].prev. After the loop, update head = new_head.unwrap();

DSA Rust

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

fn main() {
    let mut nodes = vec![];
    nodes.push(Node { value: 1, prev: None, next: None });
    let mut head: usize = 0;
    nodes[head].next = Some(1);
    nodes.push(Node { value: 2, prev: Some(head), next: None });
    nodes[1].next = Some(2);
    nodes.push(Node { value: 3, prev: Some(1), next: None });

    let mut current = Some(head);

    // Reverse the list by swapping prev and next indices
    // Your code here
}

Hint

Use while let Some(node) = current to loop. Swap using nodes[node].next.take() and assign swapped. Check if nodes[node].prev.is_none() to track new head. Set current = nodes[node].prev.

4

Print the reversed list

Write a while loop to print the values of the reversed list starting from head. Use a variable node to traverse the list by following next indices. Print each nodes[node].value followed by a space.

DSA Rust

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

fn main() {
    let mut nodes = vec![];
    nodes.push(Node { value: 1, prev: None, next: None });
    let mut head: usize = 0;
    nodes[head].next = Some(1);
    nodes.push(Node { value: 2, prev: Some(head), next: None });
    nodes[1].next = Some(2);
    nodes.push(Node { value: 3, prev: Some(1), next: None });

    let mut current = Some(head);
    let mut new_head = None;

    while let Some(node) = current {
        let next = nodes[node].next.take();
        let prev = nodes[node].prev.take();
        nodes[node].next = prev;
        nodes[node].prev = next;
        if nodes[node].prev.is_none() {
            new_head = Some(node);
        }
        current = nodes[node].prev;
    }

    head = new_head.unwrap();

    // Print the reversed list values
    // Your code here
}

Hint

Use let mut node = Some(head); then while let Some(n) = node to print nodes[n].value and move to nodes[n].next.

Practice

1. What is the main purpose of reversing a doubly linked list?

easy

A. To change the order of nodes so the last becomes first and vice versa

B. To delete all nodes from the list

C. To add new nodes at the end of the list

D. To sort the nodes in ascending order

Solution

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

   A doubly linked list has nodes connected both forward and backward.

2. Step 2: Purpose of reversing

   Reversing swaps the direction so the last node becomes the first and the first becomes the last.

3. Final Answer:

   To change the order of nodes so the last becomes first and vice versa -> Option A

4. Quick Check:

   Reversing means flipping order = C [OK]

Hint: Reversing flips the list order front to back [OK]

Common Mistakes:

• Confusing reversing with deleting nodes
• Thinking reversing sorts the list
• Mixing up adding nodes with reversing

2. Which Rust code snippet correctly swaps the next and prev pointers of a node in a doubly linked list?

easy

A. let temp = node.prev; node.prev = node.next; node.next = temp.next;

B. node.next = node.next; node.prev = node.prev;

C. node.prev = node.next; node.next = node.prev;

D. let temp = node.next; node.next = node.prev; node.prev = temp;

Solution

1. Step 1: Identify correct swapping logic

   Swapping means storing one pointer temporarily, then exchanging values.

2. Step 2: Check each option

   let temp = node.next; node.next = node.prev; node.prev = temp; correctly uses a temp variable to swap next and prev. Others either assign incorrectly or use wrong variables.

3. Final Answer:

   let temp = node.next; node.next = node.prev; node.prev = temp; -> Option D

4. Quick Check:

   Swap pointers with temp variable = D [OK]

Hint: Use a temp variable to swap pointers safely [OK]

Common Mistakes:

• Assigning pointers without temp causes data loss
• Mixing up next and prev in assignments
• Using wrong pointer in swap

3. Given the Rust code below that reverses a doubly linked list, what will be the printed output?

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

// Assume list is 1 <-> 2 <-> 3
// After reversal, print from head

// Output format: data values separated by spaces

// Output?

medium

A. 3 2 1

B. 1 2 3

C. 2 3 1

D. 3 1 2

Solution

1. Step 1: Understand initial list order

   The list is 1 <-> 2 <-> 3, so printing from head gives 1 2 3.

2. Step 2: Effect of reversal

   Reversing swaps next and prev pointers, so the new head is 3, and order is 3 2 1.

3. Final Answer:

   3 2 1 -> Option A

4. Quick Check:

   Reversed list prints backwards = 3 2 1 [OK]

Hint: Reversed doubly linked list prints nodes backward [OK]

Common Mistakes:

• Printing original order after reversal
• Confusing node data order
• Assuming reversal sorts nodes

4. Identify the bug in this Rust function that attempts to reverse a doubly linked list:

fn reverse(mut head: Option) -> Option {
    let mut current = head;
    while let Some(mut node) = current {
        let temp = node.next;
        node.next = node.prev;
        node.prev = temp;
        current = node.next;
    }
    head
}

medium

A. The loop condition should be while current.is_some()

B. Swapping next and prev pointers is done incorrectly

C. The function does not update head to the new first node after reversal

D. The function should return current instead of head

Solution

1. Step 1: Analyze pointer swapping

   Swapping next and prev is done correctly inside the loop.

2. Step 2: Check head update

   The function returns original head without updating it to the new first node after reversal, so head remains old start.

3. Final Answer:

   The function does not update head to the new first node after reversal -> Option C

4. Quick Check:

   Head must point to new first node after reverse = A [OK]

Hint: Update head to last processed node after reversal [OK]

Common Mistakes:

• Not updating head pointer after reversal
• Returning old head instead of new head
• Incorrect loop condition causing infinite loop

5. You have a doubly linked list with nodes containing integers. After reversing it, you want to find the sum of all nodes that were originally at even positions (2nd, 4th, etc.). Which approach correctly solves this in Rust?

hard

A. Reverse the list, then traverse and sum nodes at odd positions in the reversed list

B. Traverse original list, sum nodes at even positions, then reverse the list

C. Reverse the list, then sum all nodes without position checks

D. Traverse reversed list and sum nodes at even positions

Solution

1. Step 1: Understand position change after reversal

   Reversing changes node positions, so original even positions become different in reversed list.

2. Step 2: Correct approach

   Sum nodes at even positions before reversal to get original even-position sum, then reverse list if needed.

3. Final Answer:

   Traverse original list, sum nodes at even positions, then reverse the list -> Option B

4. Quick Check:

   Sum original even positions before reversing = A [OK]

Hint: Sum before reversing to keep original positions intact [OK]

Common Mistakes:

• Summing positions after reversal which changes order
• Ignoring position changes due to reversal
• Summing all nodes without filtering positions