Skip to content

Instantly share code, notes, and snippets.

@leandronsp
Created July 25, 2023 02:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save leandronsp/49407240e6afcdf3fa64e4475483c7ed to your computer and use it in GitHub Desktop.
Save leandronsp/49407240e6afcdf3fa64e4475483c7ed to your computer and use it in GitHub Desktop.
a queue using singly linked list in Rust (with tail node)
struct Node<T> {
value: T,
next: Option<Box<Node<T>>>
}
impl<T> Node<T> {
fn new(value: T) -> Self {
Self { value, next: None }
}
}
struct LinkedListQueue<T> {
head: Option<Box<Node<T>>>,
tail: Option<Box<Node<T>>>
}
impl<T> LinkedListQueue<T> {
fn new() -> Self {
Self { head: None, tail: None }
}
// Slow (push back with no tail node)
//fn enqueue(&mut self, value: T) {
// let node = Box::new(Node::new(value));
// if let Some(ref mut head) = self.head {
// let mut current = head;
// while current.next.is_some() {
// current = current.next.as_mut().unwrap();
// }
// current.next = Some(node);
// } else {
// self.head = Some(node);
// }
//}
// Fast (using tail node)
fn enqueue(&mut self, value: T) {
let node = Box::new(Node::new(value));
if self.head.is_none() {
self.head = Some(node);
} else {
self.tail.as_mut().unwrap().next = Some(node);
}
self.tail = Some(node);
}
fn dequeue(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
node.value
})
}
}
fn main() {
let mut queue = LinkedListQueue::new();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
while let Some(element) = queue.dequeue() {
println!("{}", element);
}
}
@mrpandey
Copy link

Wrong code. Doesn't work.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment