Box<T> is a smart pointer in Rust that allows you to store data on the heap instead of the stack. It’s a wrapper around heap-allocated data that provides ownership semantics while maintaining a lightweight pointer on the stack.

Here’s a basic use of Box<T>:

fn main() {
    let x = Box::new(42);
    println!("{}", x);   // Works because Box<T> implements Deref<Target=T>
    println!("{}", *x);  // Also works, manually dereferencing

Here, the value 42 is stored on the heap, but x is a pointer to that data on the stack.

Stack                Heap
+------+       +----------------+
| x -> | ----> | value: 42      |
+------+       +----------------+

When should you use Box<T>?

• Recursive data structures: Rust requires knowing the size of every type at compile time. Recursive types (like linked lists, graphs, or trees) don’t have a fixed size, so Box<T> is used to store the recursive part on the heap.
• Indirection with ownership: When you want to transfer ownership of large data but avoid copying it.
• Trait objects: When you want to store data of types that implement a particular trait but don’t know the exact type at compile time.

---

Box<T> in Recursive Structures

Example using Linked List

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

The next field is an Option<Box<ListNode>>, meaning it can either be:

• None (end of the list), or
• A Box pointing to another ListNode on the heap.

---

Example: Merging Two Sorted Lists

Consider merging two linked lists:

pub fn merge_two_lists(
    list1: Option<Box<ListNode>>,
    list2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    // Implementation here
}

We can visualize list1 and list2 like this:

list1: Some(Box) --> ListNode { val: 1, next: Some(Box) --> ListNode { val: 3, next: None } }
list2: Some(Box) --> ListNode { val: 2, next: Some(Box) --> ListNode { val: 4, next: None } }

Each Box holds the next node on the heap, making the structure dynamically sized while maintaining ownership and memory safety.

---

Key Points About Box<T>

• Zero-cost abstraction: Accessing data in a Box<T> is as fast as using a regular pointer.
• Automatic deallocation: When a Box<T> goes out of scope, Rust automatically frees the heap memory.
• Single ownership: Box<T> cannot be copied; it ensures that only one owner exists for the heap data.

---

When Not to Use Box<T>

• Use Vec<T> for resizable arrays.

• Use Rc<T> or Arc<T> for shared ownership.

• Use references (&T or &mut T) when ownership transfer isn’t required.

---