I want to convert an array to my own linked list. So Imagine I have the following array:
array: ["Manuel", "Antonio", "Elisa"]
that I want to convert to a linked list:
linked_list: "Manuel" -> "Antonio" -> "Elisa" -> None
I created the following code:
pub struct Player {
name: String
}
impl Player {
pub fn new(name: String) -> Self {
return Self {name}
}
}
pub struct PlayerList<'a> {
player: &'a Player,
next: Option<&'a PlayerList<'a>>
}
impl<'a> PlayerList<'a> {
pub fn of(player: &'a Player) -> Self {
return Self { player, next: None }
}
pub fn set_next(&mut self, player_list: &'a PlayerList<'a>) {
self.next = Some(player_list)
}
}
and the following method to "create" the linked list:
let mut head = PlayerList::of(players[0]); // so I create the head based on the first element in the array
for index in 1..players.len() {
if index == players.len()-1 {
break;
}
let player = players[index];
let next_player_round = PlayerList::of(player);
let mut current = &head;
// here I go to the tail of the linked list and append the next element
while current.next.is_some() {
current = current.next.unwrap()
}
current.set_next(&next_player_round); // here I get: `current` is a `&` reference, so the data it refers to cannot be borrowed as mutable
}
But I get:
current.set_next(&next_player_round);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `current` is a `&` reference, so the data it refers to cannot be borrowed as mutable
consider changing this to be a mutable reference
|
19 | let mut current = &mut head;
| ~~~~~~~~~~~~~~~~
Is this is a good approach? How do I do this properly?
I'm guessing that you want a linked list of objects, not references, i.e. the linked list that actually owns its contents.
First, I'd make Player copyable (manually, using Clone trait) to be able to easily deal with initializing the list from a statically-sized array. One can do without that but I wanted to avoid using Vec. Your call to change it later:
#[derive(Clone)]
pub struct Player {
name: String
}
Its constructor should probably take a string slice instead of consuming a String but that's not essentially wrong.
Now as for the list:
Rust does not easily allow defining recursive data structures. Similarly to C and C++, a structure in Rust cannot store itself. However, it might store an address of another object of its own type, in C and C++ that would be a pointer (an owning or non-owning one) or reference (non-owning only). In Rust the owning option would be a Box, Rc, or Arc. Box having unique ownership is probably the easiest one to reason about.
Now, because Rust does not have a null pointer, that Box is wrapped into an Option.
pub struct PlayerNode {
player: Player,
next: Option<Box<PlayerNode>>
}
As for the of and set_next:
of accepts the p argument by immutable reference. Then it copies the storage into the node. Note &Player and clone(). It could be done with just moves, but for the sake of the example I decided to follow that route.
set_next though takes the actual node, wraps it into Box (effectively putting it on the heap) and sets the current's node next to it. That's the intuitive one.
impl PlayerNode {
pub fn of(p: &Player) -> Self {
return Self { player: p.clone(), next: None }
}
pub fn set_next(&mut self, player_list: PlayerNode) {
self.next = Some(Box::new(player_list))
}
}
Also note, that in several places there are calls to functions as_ref and as_mut.
These are used because when iterating through the list references are used. However, when accessing "next", I do not want to take ownership of the node (Option<Node> type), nor do I want to replace the empty Option with something. The desired behaviour is to acquire the reference to the next node provided it's there.
Therefore the usage of as_ref which allows to access Option<T> as Option<&T> (immutable access) or as_mut -> Option<&mut T> respectively.
Whole code:
use std::str::FromStr;
#[derive(Clone)]
pub struct Player {
name: String
}
impl Player {
pub fn new(name: String) -> Self {
return Self {name}
}
}
pub struct PlayerNode {
player: Player,
next: Option<Box<PlayerNode>>
}
impl PlayerNode {
pub fn of(p: &Player) -> Self {
return Self { player: p.clone(), next: None }
}
pub fn set_next(&mut self, player_list: PlayerNode) {
self.next = Some(Box::new(player_list))
}
}
fn main() {
let players: [Player; 3] = [
Player::new(String::from_str("Antonio").expect("fatal Anr")),
Player::new(String::from_str("Roberto").expect("fatal Rob")),
Player::new(String::from_str("Jose").expect("fatal Jose"))];
let mut list_head: PlayerNode = PlayerNode::of(&players[0]);
let mut head = &mut list_head;
for p in &players[1..] {
println!("{}", p.name);
head.set_next(PlayerNode::of(p));
head = head.next.as_mut().expect("this should not be empty");
}
let mut head_view = &list_head;
loop {
println!("{}", head_view.player.name);
match head_view.next.as_ref() {
Some(x) => head_view = x,
None => break
};
}
}
There is one problem with that implementation though: with long enough linked list it might cause stack overflow when going out of scope. Note, that with the first node being destroyed, the next's "destructor" (I'm using C++ terminology here, pardon for that) is going to be called, then from the second one the third one and so on and so forth recursively. Not a big deal for lists of smaller size, but keep in the back of your head, that it's correct by design and unsafe in terms of exceeding the stack size at the same time. For that reason, iterative methods of releasing list nodes are oftentimes utilized.