a queue using singly linked list in Rust (with tail node)

linked_list_queue.rs

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);
    }
}

Wrong code. Doesn't work.

Here is the correct implementation

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}
struct Queue {
    front: Option<Box<Node>>,
    rear: Option<*mut Node>, // Using `Option` to track rear safely
}

impl Queue {
    fn new() -> Self {
        Queue {
            front: None,
            rear: None,
        }
    }

    fn enqueue(&mut self, data: i32) {
        let mut new_node = Box::new(Node { data, next: None });
        let raw_node: *mut Node = &mut *new_node; // Get a mutable raw pointer safely

        if let Some(rear_ptr) = self.rear {
            unsafe {
                (*rear_ptr).next = Some(new_node); // Update rear's next safely
            }
        } else {
            self.front = Some(new_node); // If empty, front becomes the new node
        }

        self.rear = Some(raw_node); // Move rear to the new node
    }

    fn dequeue(&mut self) -> Option<i32> {
        if let Some(mut old_front) = self.front.take() {
            self.front = old_front.next.take(); // Move front to the next node
            if self.front.is_none() {
                self.rear = None; // If empty, reset rear
            }
            Some(old_front.data)
        } else {
            None
        }
    }

    fn display(&self) {
        let mut current = self.front.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = node.next.as_ref();
        }
        println!("None");
    }
}

fn main() {
    let mut q = Queue::new();

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();

    q.dequeue();
    q.display();

    q.enqueue(40);
    q.display();
}