I've been trying to teach myself some Rust lately and wanted to practice a bit by implementing a simple linked list. I took some inspiration from the Rust library's linked list and tried to replicate the parts I already understood. Also I decided to make it singly-linked for now.
struct Node<T> {
element: T,
next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
fn new(element: T) -> Self {
Node {
element: element,
next: None,
}
}
fn append(&mut self, element: Box<Node<T>>) {
self.next = Some(element);
}
}
pub struct LinkedList<T> {
head: Option<Box<Node<T>>>,
tail: Option<Box<Node<T>>>,
len: u32,
}
impl<T> LinkedList<T> {
pub fn new() -> Self {
head: None,
tail: None,
len: 0,
}
pub fn push(&mut self, element: T) {
let node: Box<Node<T>> = Box::new(Node::new(element));
match self.tail {
None => self.head = Some(node),
Some(mut ref tail) => tail.append(node),
}
self.tail = Some(node);
self.len += 1;
}
pub fn pop(&mut self) -> Option<T> {
//not implemented
}
pub fn get(&self, index: u32) -> Option<T> {
//not implemented
}
}
This is what I've got so far; from what I understand, the problem with this code is that the Box
can not have more than one reference to it in order to preserve memory safety.
So when I set the list head to node in
None => self.head = Some(node),
I can't then go ahead and set
self.tail = Some(node);
later, am I correct so far in my understanding? What would be the correct way to do this? Do I have to use Shared
like in the library or is there a way in which the Box
or some other type can be utilized?