I have started learning rust a few days ago. I had heard that implementing Data Structures in rust are pretty confusable though I wanted to give it a try. The choice fell on the simplest LinkedList.
I implemented a Node as a struct:
#[derive(Debug, Clone)]
struct Node {
value: i32,
next: Option<Box<Node>>,
}
Without a generic value, for simplicity.
I implemented fmt::Display in order to write tests, and a simple new function for node creation.
impl fmt::Display for Node {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{:?}", self)
}
}
impl Node {
fn new(value: i32) -> Node {
Node {
value,
next: None,
}
}
}
Then I created a LinkedList struct that holds the head and the tail.
struct LinkedList {
head: Option<Box<Node>>,
tail: Option<Box<Node>>,
}
For now, I only tried to implement push_back() function and it turned out to be hard enough for me to fail.
It is the current state of it:
impl LinkedList {
pub fn push_back(&mut self, value: i32) {
let new_node = Box::new(Node::new(value));
match self.tail {
Some(ref mut tail) => {
tail.next = Some(new_node.clone());
swap(&mut Some(new_node.clone()), &mut self.tail);
}
None => {
self.head = Some(new_node.clone());
self.tail = Some(new_node.clone());
}
}
}
}
Before I show the results of it, let me explain how do I understand my code - which is where most likely the error occurs.
I create an immutable pointer to the newly created node. Pointer - Box - is stored on the stack and points to the node created on the heap.
Then I match self.tail to see if the list is empty. In such a case I execute this block of code:
self.head = Some(new_node.clone());
self.tail = Some(new_node.clone());
So I'm deluding myself that self.head and self.tail points to the same address on the heap, because I only clone the pointer. If I understand my debugger properly, it - unfortunately - ain't the case.
If I naively execute it on the empty list, it compiles and assigns some Node to the tail. When I try to add another node, the first arm executes:
tail.next = Some(new_node.clone());
swap(&mut Some(new_node.clone()), &mut self.tail);
Here, I want to operate on the tail, which should be the exact same node as the head, and modify its next property. Afterward, I try to swap the current tail, with the newly created node.
Thus, on this state, I would expect my LinkedList to look like that:
Head: Node { value: 5, next: Node { value: 3, next: None } }
Tail: Node { value: 3, next: None }
My code doesn't meet my expectations though.
It outputs:
Head: Node { value: 5, next: None }
Tail: Node { value: 3, next: None }
What do I misunderstand? I'd be grateful for any hints.
If someone wants to reproduce the code, I also share the code I wrote that is responsible for tests.
fn scan_list(list: &LinkedList) -> impl Iterator<Item=Node> {
let mut current_node = list.head.clone();
std::iter::from_fn(move || {
match current_node.clone() {
None => {
None
}
Some(node) => {
current_node = node.clone().next;
Some(node.as_ref().clone())
}
}
})
}
tests.rs
#[cfg(test)]
mod tests {
use super::*;
use expect_test::{expect, Expect};
use crate::{scan_list, LinkedList, Node};
fn test_list(src: &LinkedList, expect: Expect) {
let actual: String = scan_list(src).map(|node| format!("{:?}\n", node)).collect();
expect.assert_eq(&actual)
}
#[test]
fn test_empty_list() {
let list = LinkedList { head: None, tail: None };
test_list(
&list,
expect![r#""#],
)
}
#[test]
fn test_list_with_single_node() {
let list = LinkedList { head: Some(Box::new(Node::new(5))), tail: None };
test_list(
&list,
expect![r#"
Node { value: 5, next: None }
"#],
)
}
#[test]
fn test_list_with_two_nodes() {
let mut list = LinkedList { head: None, tail: None };
list.push_back(5);
list.push_back(3);
test_list(
&list,
expect![r#"
Node { value: 5, next: Node { value: 3, next: None } }
Node { value: 3, next: None }
"#],
)
}
}
It of course doesn't pass the last one.