Queue Implementation (Using Linked List)

A queue can also be implemented using a linked list, where elements are added at the rear (tail) and removed from the front (head). This naturally preserves the First In, First Out (FIFO) behavior.

Using a linked list allows the queue to grow dynamically without requiring contiguous memory.

Key Idea

To implement a queue with a linked list:

• Front of the queue → head of the list
• Rear of the queue → tail of the list
• Enqueue → insert at the tail
• Dequeue → remove from the head

Dequeue
   ↓
[1] → [2] → [3]
                 ↑
               Enqueue

Both operations run in constant time.

Queue Operations

The linked-list queue supports:

• Enqueue - add an element to the rear
• Dequeue - remove an element from the front
• Peek - view the front element
• Is Empty - check if the queue is empty

Rust Representation

This implementation uses a singly linked list with both head and tail pointers to guarantee O(1) enqueue and dequeue operations.

Rust Implementation

#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

#[derive(Debug)]
pub struct Queue<T> {
    head: Option<Box<Node<T>>>,
    tail: *mut Node<T>,
}

impl<T> Queue<T> {
    pub fn new() -> Self {
        Queue {
            head: None,
            tail: std::ptr::null_mut(),
        }
    }

    pub fn enqueue(&mut self, value: T) {
        let mut new_node = Box::new(Node { value, next: None });
        let raw_tail: *mut _ = &mut *new_node;

        if self.tail.is_null() {
            self.head = Some(new_node);
        } else {
            unsafe {
                (*self.tail).next = Some(new_node);
            }
        }

        self.tail = raw_tail;
    }

    pub fn dequeue(&mut self) -> Option<T> {
        self.head.take().map(|mut node| {
            self.head = node.next.take();

            if self.head.is_none() {
                self.tail = std::ptr::null_mut();
            }

            node.value
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.value)
    }

    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn queue_works() {
        let mut queue = Queue::new();

        assert!(queue.is_empty());

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        assert_eq!(queue.peek(), Some(&1));
        assert_eq!(queue.dequeue(), Some(1));
        assert_eq!(queue.dequeue(), Some(2));
        assert_eq!(queue.dequeue(), Some(3));
        assert!(queue.is_empty());
    }
}

Example Usage

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

    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    println!("Front: {:?}", queue.peek()); // Some(10)

    while let Some(value) = queue.dequeue() {
        println!("Dequeued: {}", value);
    }
}

Output:

Front: Some(10)
Dequeued: 10
Dequeued: 20
Dequeued: 30

Time and Space Complexity

Time Complexity

Space Complexity

VecDeque Queue vs Linked List Queue

When to Use a Linked List Queue

Use a linked list queue when:

• You need full control over memory layout
• You are implementing queues as part of a larger linked structure
• Educational purposes

In real-world Rust code, VecDeque is almost always preferred.

Summary

• Queue maps naturally to a linked list
• Head/tail pointers enable O(1) operations
• Slightly more complex and unsafe
• Useful for understanding low-level behavior

Playground Links

Rust - Queue Implementation (Using Linked List)