Why Doubly Linked List Over Singly Linked List in DSA Rust - See It Work

Why Doubly Linked List Over Singly Linked List

📖 Scenario: Imagine you are managing a playlist of songs. You want to move forward and backward through the songs easily. Using a linked list helps you keep track of the order of songs.

🎯 Goal: Build a simple doubly linked list in Rust and see how it allows moving forward and backward through the list, unlike a singly linked list.

📋 What You'll Learn

Create a doubly linked list with three nodes containing values 10, 20, and 30

Add a variable to keep track of the current node starting at the head

Write code to move forward to the next node and then backward to the previous node

Print the values of the nodes visited in order

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, web browsers (back and forward buttons), and undo-redo features where moving both ways is needed.

💼 Career

Understanding doubly linked lists helps in jobs involving system programming, game development, and any software requiring efficient two-way navigation through data.

1

Create a doubly linked list with three nodes

Create a struct called Node with fields value: i32, next: Option>, and prev: Option<*mut Node>. Then create three nodes with values 10, 20, and 30 linked as a doubly linked list.

DSA Rust

# Define the Node struct and create three linked nodes
# Your code here

Hint

Use Option> for next and raw pointers Option<*mut Node> for prev to avoid ownership issues.

2

Add a variable to track the current node

Add a mutable variable called current and set it to a mutable reference to node1 to start at the head of the list.

DSA Rust

use std::ptr;

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

fn main() {
    let mut node3 = Box::new(Node { value: 30, next: None, prev: None });
    let mut node2 = Box::new(Node { value: 20, next: Some(node3), prev: None });
    let mut node1 = Box::new(Node { value: 10, next: Some(node2), prev: None });

    // Set prev pointers
    let node1_ptr: *mut Node = &mut *node1;
    let node2_ptr: *mut Node = match node1.next.as_mut() {
        Some(ref mut n) => &mut **n,
        None => ptr::null_mut(),
    };
    let node3_ptr: *mut Node = match node2.next.as_mut() {
        Some(ref mut n) => &mut **n,
        None => ptr::null_mut(),
    };

    unsafe {
        if !node2_ptr.is_null() {
            (*node2_ptr).prev = Some(node1_ptr);
        }
        if !node3_ptr.is_null() {
            (*node3_ptr).prev = Some(node2_ptr);
        }
    }

    // Add a mutable variable current to point to node1
    // Your code here

Hint

Use a raw pointer *mut Node for current to track the current node.

3

Move forward and backward through the list

Write unsafe code to move current forward to the next node, then backward to the previous node, updating current accordingly.

DSA Rust

use std::ptr;

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

fn main() {
    let mut node3 = Box::new(Node { value: 30, next: None, prev: None });
    let mut node2 = Box::new(Node { value: 20, next: Some(node3), prev: None });
    let mut node1 = Box::new(Node { value: 10, next: Some(node2), prev: None });

    // Set prev pointers
    let node1_ptr: *mut Node = &mut *node1;
    let node2_ptr: *mut Node = match node1.next.as_mut() {
        Some(ref mut n) => &mut **n,
        None => ptr::null_mut(),
    };
    let node3_ptr: *mut Node = match node2.next.as_mut() {
        Some(ref mut n) => &mut **n,
        None => ptr::null_mut(),
    };

    unsafe {
        if !node2_ptr.is_null() {
            (*node2_ptr).prev = Some(node1_ptr);
        }
        if !node3_ptr.is_null() {
            (*node3_ptr).prev = Some(node2_ptr);
        }
    }

    let mut current: *mut Node = &mut *node1;

    // Move current forward to next node and then backward to previous node
    // Your code here

Hint

Use unsafe block to dereference raw pointers and update current to next and prev nodes.

4

Print the values of visited nodes

Print the value of the starting node, then after moving forward, print the value of the next node, and after moving backward, print the value of the previous node again.

DSA Rust

use std::ptr;

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

fn main() {
    // Previous code here

    // Print the values of visited nodes
    // Your code here
}

Hint

Use println!("{}", (*current).value); inside an unsafe block to print the node values.

Practice

1. Why might a doubly linked list be preferred over a singly linked list in some cases?

easy

A. Because it cannot be used to implement stacks

B. Because it allows traversal in both forward and backward directions

C. Because it only stores one pointer per node

D. Because it uses less memory than singly linked list

Solution

1. Step 1: Understand traversal capabilities

   A singly linked list allows traversal only in one direction, from head to tail.

2. Step 2: Compare with doubly linked list

   A doubly linked list stores two pointers per node, allowing traversal both forward and backward.

3. Final Answer:

   Because it allows traversal in both forward and backward directions -> Option B

4. Quick Check:

   Traversal direction = Both forward and backward [OK]

Hint: Doubly linked lists have two pointers per node [OK]

Common Mistakes:

• Thinking doubly linked lists use less memory
• Confusing pointer count per node
• Assuming singly linked lists allow backward traversal

2. Which of the following is the correct way to declare a node struct for a doubly linked list in Rust?

easy

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

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

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

D. struct Node { data: i32, next: Node }

Solution

1. Step 1: Identify doubly linked list node fields

   A doubly linked list node must have pointers to both previous and next nodes, usually wrapped in Option and Box for ownership.

2. Step 2: Check each option

   struct Node { data: i32, prev: Option, next: Option } correctly declares both prev and next as Option. Others miss prev or use incorrect types.

3. Final Answer:

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

4. Quick Check:

   Prev and next pointers = struct Node { data: i32, prev: Option, next: Option } [OK]

Hint: Doubly linked nodes have prev and next pointers [OK]

Common Mistakes:

• Omitting prev pointer
• Using Box<Node> without Option
• Using next as Node instead of pointer

3. Given this Rust code snippet for a doubly linked list insertion at the end, what will be the printed list after inserting 3 nodes with values 10, 20, 30?

let mut list = DoublyLinkedList::new();
list.push_back(10);
list.push_back(20);
list.push_back(30);
list.print_forward();

medium

A. 10 -> 30 -> 20 -> null

B. 30 -> 20 -> 10 -> null

C. null -> 10 -> 20 -> 30

D. 10 -> 20 -> 30 -> null

Solution

1. Step 1: Understand push_back behavior

   push_back adds nodes at the end, so nodes are appended in order 10, then 20, then 30.

2. Step 2: Trace print_forward output

   Printing forward shows nodes from head to tail: 10 -> 20 -> 30 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option D

4. Quick Check:

   Insertion order = Printed order [OK]

Hint: push_back appends at tail, print_forward shows head to tail [OK]

Common Mistakes:

• Confusing push_back with push_front
• Printing backward instead of forward
• Mixing node order in output

4. In this Rust doubly linked list code, what is the bug causing incorrect backward traversal?

fn print_backward(&self) {
    let mut current = self.tail.clone();
    while let Some(node) = current {
        print!("{} -> ", node.data);
        current = node.next.clone();
    }
    println!("null");
}

medium

A. Not cloning the tail pointer

B. Printing node.data instead of node.prev

C. Using node.next instead of node.prev for backward traversal

D. Missing a break statement in the loop

Solution

1. Step 1: Analyze traversal direction

   Backward traversal should follow prev pointers, but code uses node.next which goes forward.

2. Step 2: Identify correct pointer usage

   Replacing node.next with node.prev fixes backward traversal.

3. Final Answer:

   Using node.next instead of node.prev for backward traversal -> Option C

4. Quick Check:

   Backward traversal = Use prev pointer [OK]

Hint: Backward traversal uses prev pointer, not next [OK]

Common Mistakes:

• Confusing next and prev pointers
• Not cloning pointers properly
• Printing wrong data fields

5. You want to implement a feature that allows quick removal of a node from the middle of a list without traversing from the head. Why is a doubly linked list better than a singly linked list for this task?

hard

A. Because doubly linked list nodes have pointers to previous nodes, enabling direct access to neighbors

B. Because singly linked lists store extra data for quick removal

C. Because doubly linked lists use less memory, making removal faster

D. Because singly linked lists allow backward traversal

Solution

1. Step 1: Understand node removal requirements

   Removing a node requires updating pointers of its neighbors, including the previous node.

2. Step 2: Compare singly and doubly linked lists

   Singly linked lists lack backward pointers, so to remove a node, you must traverse from head to find the previous node. Doubly linked lists have prev pointers, allowing direct access to neighbors.

3. Final Answer:

   Because doubly linked list nodes have pointers to previous nodes, enabling direct access to neighbors -> Option A

4. Quick Check:

   Prev pointer enables quick removal [OK]

Hint: Prev pointer lets you remove nodes without full traversal [OK]

Common Mistakes:

• Assuming singly linked lists have backward pointers
• Thinking memory usage affects removal speed
• Confusing traversal direction capabilities