Queue Implementation Using Linked List in DSA Rust

Mental Model

A queue is like a line where the first person in is the first person out. Using a linked list means each person holds a hand to the next, so we can add at the end and remove from the front easily.

Analogy: Imagine a line of people holding hands. The first person in line leaves first, and new people join at the end. Each person only knows who is next, not the whole line.

front -> [node1] -> [node2] -> [node3] -> null
rear ↑

Dry Run Walkthrough

Input: Start with empty queue, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements are added at the rear and removed from the front using linked list pointers

Step 1: enqueue 10: create new node with value 10, set front and rear to it

front -> [10] -> null
rear ↑

Why: Queue was empty, so front and rear both point to the new node

Step 2: enqueue 20: create new node with value 20, link rear.next to it, move rear to new node

front -> [10] -> [20] -> null
rear ↑

Why: Add new element at the end, update rear pointer

Step 3: dequeue: remove node at front (10), move front to next node (20)

front -> [20] -> null
rear ↑

Why: Remove first element, front moves forward

Step 4: enqueue 30: create new node with value 30, link rear.next to it, move rear to new node

front -> [20] -> [30] -> null
rear ↑

Why: Add new element at the end, update rear pointer

Result:

front -> [20] -> [30] -> null
rear ↑

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

// Node struct with value and optional next pointer
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

// Queue struct with front and rear pointers
struct Queue {
    front: Option<Rc<RefCell<Node>>>,
    rear: Option<Rc<RefCell<Node>>>,
}

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

    // Add value to rear
    fn enqueue(&mut self, val: i32) {
        let new_node = Rc::new(RefCell::new(Node { value: val, next: None }));
        match self.rear.take() {
            Some(old_rear) => {
                old_rear.borrow_mut().next = Some(new_node.clone()); // link old rear to new node
                self.rear = Some(new_node); // update rear
            }
            None => {
                // Queue empty, front and rear are new node
                self.front = Some(new_node.clone());
                self.rear = Some(new_node);
            }
        }
    }

    // Remove value from front
    fn dequeue(&mut self) -> Option<i32> {
        self.front.take().map(|old_front| {
            if let Some(next_node) = old_front.borrow().next.clone() {
                self.front = Some(next_node); // move front to next
            } else {
                // Queue is now empty
                self.rear = None;
            }
            Rc::try_unwrap(old_front).ok().unwrap().into_inner().value
        })
    }

    // Print queue from front to rear
    fn print(&self) {
        let mut current = self.front.clone();
        while let Some(node) = current {
            print!("{} -> ", node.borrow().value);
            current = node.borrow().next.clone();
        }
        println!("null");
    }
}

fn main() {
    let mut queue = Queue::new();
    queue.enqueue(10);
    queue.enqueue(20);
    queue.dequeue();
    queue.enqueue(30);
    queue.print();
}

old_rear.borrow_mut().next = Some(new_node.clone());

link old rear node to new node to add at end

self.rear = Some(new_node);

update rear pointer to new node

self.front.take().map(|old_front| {

remove front node and get its value

if let Some(next_node) = old_front.borrow().next.clone() {

move front pointer to next node if exists

self.rear = None;

if no next node, queue is empty, so rear is None

Output

20 -> 30 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we keep direct pointers to front and rear nodes

Space: O(n) because each element is stored as a node in the linked list

vs Alternative: Compared to array-based queue, linked list avoids shifting elements on dequeue, making dequeue O(1) instead of O(n)

Edge Cases

dequeue from empty queue

returns None without error

DSA Rust

self.front.take().map(|old_front| {

enqueue on empty queue

front and rear both point to new node

DSA Rust

None => { self.front = Some(new_node.clone()); self.rear = Some(new_node); }

dequeue last element

front and rear become None, queue becomes empty

DSA Rust

self.rear = None;

When to Use This Pattern

When you need a first-in-first-out structure with efficient add and remove operations, use a queue with linked list to get O(1) enqueue and dequeue.

Common Mistakes

Mistake: Not updating rear pointer after enqueue, causing enqueue to fail or lose track of last node
Fix: Always update rear pointer to the new node after linking it

Mistake: Not handling empty queue case when dequeueing, causing panic or error
Fix: Check if front is None before dequeue and return None safely

Summary

Implements a queue using a linked list with pointers to front and rear nodes.

Use when you want efficient FIFO behavior without shifting elements like in arrays.

Keep track of both front and rear pointers to achieve O(1) enqueue and dequeue.

Practice

1. What is the main advantage of implementing a Queue using a linked list instead of an array?

easy

A. Simpler to implement than arrays

B. Faster access to elements by index

C. Dynamic size without fixed capacity limit

D. Uses less memory for small queues

Solution

1. Step 1: Understand queue size behavior

   Arrays have fixed size or require resizing, linked lists grow dynamically.

2. Step 2: Compare memory and resizing

   Linked lists allocate nodes as needed, so no fixed capacity limit exists.

3. Final Answer:

   Dynamic size without fixed capacity limit -> Option C

4. Quick Check:

   Linked list queues grow dynamically = D [OK]

Hint: Linked lists grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking linked lists allow fast random access
• Assuming arrays use less memory always
• Confusing implementation simplicity

2. Which of the following is the correct Rust syntax to define a node struct for a linked list queue?

easy

A. struct Node { data: i32, next: Option }

B. struct Node { data: i32, next: Node }

C. struct Node { data: i32, next: &Node }

D. struct Node { data: i32, next: Box<Node> }

Solution

1. Step 1: Understand Rust ownership for linked lists

   Rust requires heap allocation for recursive types using Box and Option for nullable links.

2. Step 2: Analyze options

   struct Node { data: i32, next: Option } uses Option which is correct for nullable next pointer; others cause infinite size or borrowing issues.

3. Final Answer:

   struct Node { data: i32, next: Option } -> Option A

4. Quick Check:

   Use Option for nullable next in Rust [OK]

Hint: Use Option for next pointer in Rust linked list [OK]

Common Mistakes:

• Using direct Node type causes infinite size error
• Using references (&Node) without lifetime causes errors
• Omitting Option for nullable next pointer

3. Given the following Rust code snippet for a queue implemented with a linked list, what will be printed after enqueueing 10, 20 and then dequeueing once?

let mut queue = Queue::new();
queue.enqueue(10);
queue.enqueue(20);
let val = queue.dequeue();
println!("Dequeued: {:?}", val);
queue.print();

medium

A. Dequeued: Some(10)
20 -> null

B. Dequeued: Some(20)
10 -> null

C. Dequeued: None
10 -> 20 -> null

D. Dequeued: Some(10)
10 -> 20 -> null

Solution

1. Step 1: Trace enqueue operations

   Enqueue 10 adds node with 10, then enqueue 20 adds node with 20 at the end.

2. Step 2: Trace dequeue operation

   Dequeue removes front node (10), returns Some(10). Remaining queue has 20 only.

3. Final Answer:

   Dequeued: Some(10) 20 -> null -> Option A

4. Quick Check:

   First in first out, dequeue returns 10, queue left with 20 [OK]

Hint: Dequeue removes front, so first enqueued is first out [OK]

Common Mistakes:

• Assuming dequeue removes last element
• Printing queue before dequeue
• Confusing Some and None return values

4. Identify the bug in this Rust enqueue method for a linked list queue:

fn enqueue(&mut self, data: i32) {
    let new_node = Box::new(Node { data, next: None });
    if self.tail.is_none() {
        self.head = Some(new_node);
    } else {
        self.tail.as_mut().unwrap().next = Some(new_node);
    }
    self.tail = Some(new_node);
}

medium

A. Not updating head when queue is empty

B. Using Box instead of Rc for nodes

C. Missing return statement in enqueue

D. Assigning new_node to tail after moving it causes use-after-move error

Solution

1. Step 1: Analyze ownership of new_node

   new_node is moved into head or tail.next, so cannot be moved again.

2. Step 2: Identify use-after-move error

   Assigning self.tail = Some(new_node) after moving new_node causes compile error.

3. Final Answer:

   Assigning new_node to tail after moving it causes use-after-move error -> Option D

4. Quick Check:

   Moving new_node twice causes error [OK]

Hint: Don't move ownership twice; clone or restructure [OK]

Common Mistakes:

• Ignoring Rust ownership rules
• Not updating tail pointer correctly
• Confusing Box and Rc usage

5. You want to implement a method peek for your linked list queue in Rust that returns the front element without removing it. Which approach is correct?

hard

A. Return Option<i32> by cloning data from head node

B. Return Option<&i32> by borrowing data from head node

C. Return i32 directly, panicking if queue is empty

D. Return Option by moving head node

Solution

1. Step 1: Understand peek method goal

   Peek returns front element without removing it, so no ownership transfer.

2. Step 2: Choose correct return type

   Borrowing data with Option<&i32> avoids cloning or moving, safe and efficient.

3. Final Answer:

   Return Option<&i32> by borrowing data from head node -> Option B

4. Quick Check:

   Peek borrows front data, no ownership change [OK]

Hint: Peek borrows front data, don't move or clone unnecessarily [OK]

Common Mistakes:

• Moving head node causing queue modification
• Returning owned data causing unnecessary clone
• Panicking instead of returning Option