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?
The LinkedList allows pushing and popping elements at either end in constant time. A LinkedList with a known list of items can be initialized from an array: use std::collections::LinkedList; let list = LinkedList::from([1, 2, 3]);
It is difficult to implement Linked List in Rust as what is allowed in most languages is simply not allowed in Rust, While it may seem to be a little difficult but the Rust compiler also at the same time makes sure that your code is memory safe.
A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail). Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list.
In its most simplest form, a singly linked list is a linked list where each node is an object that stores a reference to an element and a reference, called next, to another node. Note that a node is defined in terms of itself, which is called self-referential structure.
Your issue is that you are attempting to use a value (node
) after having moved it; since Box<Node<T>>
does not implement Copy
, when you use it in the match
expression:
match self.tail {
None => self.head = Some(node),
Some(ref mut tail) => tail.append(node),
}
node
is moved either to self.head
or to self.tail
and can no longer be used later. Other than reading the obligatory Learning Rust With Entirely Too Many Linked Lists to see the different ways in which you can implement linked lists in Rust, I suggest that you first do some more research in the field of Rust's basic concepts, especially:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With