Using Linked Lists in Rust

Linked list with next and back implementations

This bit of learning is inspired by Merge Two Sorted Lists. It does not contain any solution code.

In this problem it's immediately required to understand implementing manually managed memory with heap allocations. I didn't think it'd happen so fast, but here we are.

Immediately when you open the problem you'll notice this type-definition:

---

Option<Box<ListNode>>

---

Every character in that line was alien to me other than the <> symbols. But I was able to determine that ListNode was a user-defined struct, but did that mean that Box and Option are built-ins?

They are both built-ins:

Option Docs

Box Docs

What is 'Option'?

Option<...>

This is "How to tell the Rust compiler that the variable enclosed in the <> may or may not exist". If it doesn't exist it's evaluated as None. If it does, then it's whatever type is enclosed. I later learned it’s technically an Enum, but I won’t go into that for now.

What is 'Box'?

Box<...>

This is "How to allocate, and reference memory on the heap in Rust".

‘Box’ is a way to create references to an allocation of memory on the heap. Which is different from a stack memory allocation. The Rust manual describes the difference in great detail.

So by now, we have a manually allocated 'box' of memory in the heap, that may or may not exist. Sweet.

What is ListNode?

This was a custom type defined in the Leetcode problem. It's a struct, but that was still a blocker for me because I didn't know how to instantiate or work with a struct at all.

struct ListNode {
    pub val i32;
}

// Create a new element
let my_node: ListNode = ListNode::new(10);

Leveled Up!

Ok, so no I’ve got a ListNode created, and I can even create a new one in a box, that is an option. This allows me to work with elements that may or may not exist on the heap (since it’s boxes) and those specific elements are ListNodes. Seems like a fitting architecture for Linked Lists.

Ah, Crap.

A plain struct with no syntactical sugar, doesn't print using my newly discovered "{:?}" method. It turns out you need to enable the Debug feature on Structs in order for them to print using the debug template.

#[derive(Debug)]  

pub struct ListNode {
    pub val: i32 
}

The Rust Compiler Hype is Real

1. I love that the compiler plainly differentiates between suggestions and error reporting.

2. It told me Debug is not implemented.

3. It told me where it wants not implemented.

4. It gave me multiple tips on how to resolve the issue.

Conclusion

That's enough for today. I've learned and implemented some new things. And I want to mess around with those a bit before I move on to deeper implementations because I feel that my grasp is still too feeble to understand strengths and weaknesses just yet.

In the next post, I'll cover how to traverse the items in a linked list, how to update which items they point to safely, and how to reference items from within a linked list.

My Homework

• Learn more about the decorators for structs

• Learn how to reference boxes across contexts (since that memory shouldn’t release)

• Learn more deeply about enums (Since Options are technically enums)