Node Structure and Pointer Design in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Rust code with linked list nodes?

Consider the following Rust code that creates a simple singly linked list with nodes holding integers. What will be printed after running this code?

DSA Rust

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

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

fn main() {
    let node3 = Rc::new(RefCell::new(Node { value: 3, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: Some(Rc::clone(&node3)) }));
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: Some(Rc::clone(&node2)) }));

    let mut current = Some(Rc::clone(&node1));
    while let Some(node) = current {
        print!("{} -> ", node.borrow().value);
        current = node.borrow().next.clone();
    }
    print!("null");
}

A 1 -> 2 -> null

B 3 -> 2 -> 1 -> null

C null

D 1 -> 2 -> 3 -> null

💡 Hint

Trace the nodes starting from node1 following the next pointers.

The code creates three nodes linked from node1 to node3. The loop prints values from node1 to node3 in order, ending with null.

❓ Predict Output

intermediate

What error does this Rust code produce when creating a cyclic linked list?

This Rust code tries to create a cycle in a linked list using Rc and RefCell. What error or behavior will it produce?

DSA Rust

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

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

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: Some(Rc::clone(&node1)) }));

    // Creating cycle: node1.next points to node2
    node1.borrow_mut().next = Some(Rc::clone(&node2));

    println!("Created cyclic list");
}

A Compile-time error due to mutable borrow conflict

B Program runs and prints 'Created cyclic list' without error

C Runtime stack overflow if traversing the list

D Panic at runtime due to borrow checker violation

💡 Hint

Rc and RefCell allow runtime mutable borrows; cycle creation is possible but dangerous.

The code compiles and runs printing the message. However, traversing this cyclic list would cause infinite loops or stack overflow.

🔧 Debug

advanced

Why does this Rust code cause a compile error with node pointers?

Identify the cause of the compile error in this Rust code that tries to create a linked list node with a next pointer.

DSA Rust

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

fn main() {
    let node1 = Node { value: 1, next: None };
    let node2 = Node { value: 2, next: Some(Box::new(node1)) };
    println!("{:?}", node2);
}

A Cannot move node1 because it is used after move in node2

B Missing lifetime annotations for Node struct

C Box<Node> requires unsafe code to use

D Option<Box<Node>> cannot be None

💡 Hint

Check ownership rules when moving node1 into node2.

node1 is moved into node2's next field, so node1 cannot be used again. The code tries to use node1 after move causing compile error.

❓ Predict Output

advanced

What is the output of this Rust code using Rc and Weak pointers?

This Rust code creates nodes with Rc and Weak pointers to avoid cycles. What will be printed?

DSA Rust

use std::rc::{Rc, Weak};
use std::cell::RefCell;

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

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None, prev: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: None, prev: Some(Rc::downgrade(&node1)) }));
    node1.borrow_mut().next = Some(Rc::clone(&node2));

    let prev_of_node2 = node2.borrow().prev.as_ref().unwrap().upgrade();
    match prev_of_node2 {
        Some(prev_node) => println!("Prev value: {}", prev_node.borrow().value),
        None => println!("No previous node"),
    }
}

A Prev value: 1

B No previous node

C Compile-time error due to Weak usage

D Runtime panic due to unwrap on None

💡 Hint

Weak pointers can be upgraded to Rc if the original Rc exists.

node2.prev is a Weak pointer to node1. Upgrading it succeeds because node1 is alive, so it prints Prev value: 1.

🧠 Conceptual

expert

Which pointer design prevents memory leaks in cyclic Rust data structures?

In Rust, when designing node structures that can form cycles, which pointer type combination is best to prevent memory leaks?

A Use Box for all pointers to ensure ownership

B Use Rc for all pointers including back pointers

C Use Rc for next pointers and Weak for back pointers

D Use raw pointers (*) for all links to avoid ownership issues

💡 Hint

Think about how Rust's reference counting works and how cycles affect it.

Using Rc for next pointers and Weak for back pointers breaks cycles, allowing memory to be freed properly.

Practice

1. What is the primary purpose of a next pointer in a singly linked list node structure?

easy

A. To indicate the size of the list

B. To store the data value of the node

C. To point to the next node in the list

D. To point to the previous node in the list

Solution

1. Step 1: Understand the role of pointers in linked lists

   In a singly linked list, each node contains data and a pointer to the next node to maintain the sequence.

2. Step 2: Identify the function of the next pointer

   The next pointer specifically points to the next node, enabling traversal through the list.

3. Final Answer:

   To point to the next node in the list -> Option C

4. Quick Check:

   next pointer = next node address [OK]

Hint: Next pointer always links to the following node [OK]

Common Mistakes:

• Confusing next pointer with previous pointer
• Thinking next stores data instead of address
• Assuming next pointer stores list size

2. Which of the following is the correct Rust syntax to define a singly linked list node struct with a next pointer using Option and Box?

easy

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

B. struct Node { data: i32, next: &Node }

C. struct Node { data: i32, next: Box<Node> }

D. struct Node { data: i32, next: Option<&Node> }

Solution

1. Step 1: Recall Rust ownership and pointer rules for linked lists

   Rust requires heap allocation for recursive types, so Box is used to allocate nodes on the heap. The Option type allows for a nullable pointer.

2. Step 2: Analyze each option's correctness

   struct Node { data: i32, next: Box<Node> } lacks Option, so it cannot represent the end of the list (null). struct Node { data: i32, next: Option } correctly uses Option. struct Node { data: i32, next: &Node } uses a reference without lifetime, which is invalid. struct Node { data: i32, next: Option<&Node> } uses a reference inside Option, which is problematic for ownership.

3. Final Answer:

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

4. Quick Check:

   Use Option for nullable heap pointer [OK]

Hint: Use Option for nullable next pointer in Rust [OK]

Common Mistakes:

• Omitting Option to represent null
• Using references without lifetimes
• Not boxing recursive types

3. Given the following Rust code for a singly linked list node, what will be printed?

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

fn main() {
    let node3 = Node { data: 3, next: None };
    let node2 = Node { data: 2, next: Some(Box::new(node3)) };
    let node1 = Node { data: 1, next: Some(Box::new(node2)) };

    let mut current = &node1;
    while let Some(ref next_node) = current.next {
        println!("{} ->", current.data);
        current = next_node;
    }
    println!("{} -> null", current.data);
}

medium

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

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

C. 1 -> 2 -> null

D. Compilation error due to ownership

Solution

1. Step 1: Trace the linked list construction

   node1 points to node2, node2 points to node3, node3 points to None (end).

2. Step 2: Follow the while loop printing data

   The loop prints current.data and moves to next node until next is None. It prints 1, then 2, then 3, then prints 3 -> null after loop.

3. Final Answer:

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

4. Quick Check:

   Traverse nodes in order: 1, 2, 3 [OK]

Hint: Follow next pointers from head to end [OK]

Common Mistakes:

• Confusing order of nodes
• Expecting reverse print
• Thinking ownership causes compile error here

4. Identify the error in this Rust code snippet defining a linked list node:

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

medium

A. Data type i32 is invalid for node data

B. Missing Box to allocate next node on heap

C. Option cannot be used with structs

D. next should be a reference &Node instead

Solution

1. Step 1: Understand recursive struct requirements in Rust

   Rust needs recursive types to use indirection like Box to know size at compile time.

2. Step 2: Analyze the next field type

   Using Option<Node> causes infinite size because Node contains Node directly. It must be Option to compile.

3. Final Answer:

   Missing Box to allocate next node on heap -> Option B

4. Quick Check:

   Recursive structs need Box for next pointer [OK]

Hint: Use Box for recursive node pointers in Rust [OK]

Common Mistakes:

• Omitting Box causes compile error
• Using references without lifetimes
• Thinking Option<Node> is enough

5. You want to design a doubly linked list node in Rust with safe ownership. Which of the following node struct definitions correctly uses pointers to represent prev and next nodes without causing ownership or borrowing errors?

hard

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

B. struct Node { data: i32, prev: Option<&Node>, next: Option<&Node> }

C. struct Node { data: i32, prev: Option<*mut Node>, next: Option }

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

Solution

1. Step 1: Understand ownership challenges in doubly linked lists

   Doubly linked lists have nodes pointing both ways, causing multiple ownership which Rust's default ownership model disallows.

2. Step 2: Analyze pointer types for safe shared ownership

   struct Node { data: i32, prev: Option, next: Option } uses Box for both prev and next, causing ownership conflicts. struct Node { data: i32, prev: Option<*mut Node>, next: Option } uses raw pointer for prev, unsafe. struct Node { data: i32, prev: Option<&Node>, next: Option<&Node> } uses references without lifetimes, invalid. struct Node { data: i32, prev: Option>, next: Option> } uses Rc allowing multiple owners and interior mutability safely.

3. Final Answer:

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

4. Quick Check:

   Use Rc and RefCell for safe shared mutable ownership [OK]

Hint: Use Rc for doubly linked list nodes [OK]

Common Mistakes:

• Using Box for both prev and next causes ownership errors
• Using raw pointers without safety
• Using references without lifetimes