Implementing a mutable linked list

We want to implement a singly linked list in Rust, capable of storing i32 values in its nodes. As you certainly know, such a data structure is recursive, made of two types of nodes, with each non-empty node pointing to the next node until the final (empty) node is reached, like this:

Rust enums are the right tool for the job, so as a first approximation we can start from:

#![allow(unused)]
fn main() {
pub enum List {
    Nil,
    Cons(i32, List),
}
}

Exercise 1.a: Try the above definition to see if it works. If not, explain in your own words why it doesn't, building upon the knowledge of some of the traits we have learned about in today's lecture.

Exercise 1.b: The Box type that you have learned about allows to put any value into a box of a fixed size. Use it to refine your List type definition so that it compiles. Then, create by hand (using Nil, Cons, and Box methods) sample list values:

the empty list,
a list containing one element,
a list containing two elements,
up to the list depicted in the figure above.

To help debugging the values you are building, implement the Debug trait for List, so that you can print your lists with the {:?} format string.

Exercise 1.c: Let's now use the linked list to build a proper abstract data type: a stack. Create a struct Stack that uses List internally to store its elements but also has a separate size field to keep track of the list size. All stack manipulations must respect the invariant that size always corresponds to the total number of non-Nil cells in the list. Add to your Stack an impl block that implements at least the following methods:

new that creates a fresh empty stack,
len that returns the stack length,
push that adds an i32 on top of the stack,
pop that removes and returns the top element (if it exists).

Make sure push and pop modify the stack list in place. (But feel free to implement an alternative purely functional version of the stack—returning fresh versions of the stack at each method call—as a separate exercise!)

Tip: due to memory ownership rules, implementing push and pop might be trickier than you would expect based on experience with other programming language. If you get stuck, have a look at the std::mem::replace stdlib function and ponder how it can help.

NET7212 Lab

Implementing a mutable linked list