Using Box<T> to Point to Data on the Heap

In Rust, `Box<T>` is a smart pointer that allows you to allocate values on the heap instead of the stack. When you place a value into a `Box`, the `Box` itself is stored on the stack (it's a fixed-size pointer), but the data it points to is moved to the heap.

Why use `Box<T>`?

1. Heap Allocation: `Box<T>` is primarily used for allocating data on the heap. This is useful for:
* Large Data Structures: When you have very large data structures that might overflow the stack if stored directly there.
* Unknown Size at Compile Time: When you need a type whose size cannot be determined at compile time, such as recursive data structures (e.g., linked lists, trees). `Box<T>` allows you to define these by providing a fixed-size pointer on the stack, while the actual data resides on the heap.
* Trait Objects: For creating 'trait objects' where you need to store values of different concrete types that implement a common trait. `Box<dyn Trait>` is a common pattern for this, allowing dynamic dispatch and storing the concrete type on the heap.

2. Ownership and Deallocation: `Box<T>` strictly adheres to Rust's ownership rules. When a `Box<T>` goes out of scope, its destructor is called, which automatically deallocates the heap memory it was pointing to. This guarantees memory safety and prevents memory leaks without manual memory management.

3. Fixed Size on Stack: Even if the actual data on the heap is large or of variable size, the `Box<T>` itself always occupies a fixed amount of memory on the stack (the size of a pointer). This makes it suitable for scenarios where you need a consistent stack footprint.

How `Box<T>` Works:

* `Box::new(value)` moves `value` from the stack to the heap and returns a `Box` smart pointer that points to it.
* `Box<T>` implements the `Deref` trait, which allows you to treat a `Box<T>` like a reference (`&T`) to the data inside it. This means you can use the `*` dereference operator to access the value or call methods directly on the `Box` as if it were the value itself.
* When the `Box` goes out of scope, Rust's ownership system ensures the memory on the heap is freed.

```rust
fn main() {
    // 1. Allocating a simple integer on the heap
    // 'b' is on the stack, but the value '5' is allocated on the heap.
    let b = Box::new(5);
    println!("Value in Box b: {}", b); // Box implements Deref, so it acts like &i32

    // You can explicitly dereference it if needed, though often not required due to Deref coercion.
    println!("Value in Box b (explicit deref): {}", *b);

    // 2. Allocating a String on the heap using Box
    let s = Box::new(String::from("Hello from the heap!"));
    println!("String in Box s: {}", *s); // Accessing the String content

    // 3. Common use case: Recursive data structures
    // Without Box, this enum definition would result in a compile-time error
    // because `List` would have an infinite size.
    // enum List { Cons(i32, List), Nil } // ERROR: recursive type has infinite size

    // With Box, `List` becomes a fixed size (size of i32 + size of a pointer).
    enum List {
        Cons(i32, Box<List>), // Box<List> holds the rest of the list on the heap
        Nil,
    }

    let list = List::Cons(10, Box::new(List::Cons(20, Box::new(List::Cons(30, Box::new(List::Nil))))));
    println!("Created a recursive linked list using Box.");
    // (Printing the elements would require a recursive function, but this demonstrates the definition)

    // 4. Ownership and Deallocation
    let x = Box::new(100); // 'x' owns the integer 100 on the heap
    println!("Original value of x: {}", *x);

    let y = x; // Ownership of the Box (and its heap data) moves from x to y

    // println!("Value of x after move: {}", *x); 
    // ^ This line would cause a compile-time error: "borrow of moved value: `x`"
    // because 'x' no longer owns the data.

    println!("Value of y after move: {}", *y);

    // When 'y' goes out of scope at the end of main, the heap memory allocated for '100'
    // will be automatically deallocated by Box's Drop implementation.
}
```