Enqueue Using Linked List in DSA Rust

Mental Model

Add a new item at the end of a line so the first who came stays first. We keep track of the last item to add quickly.

Analogy: Imagine a queue at a ticket counter where new people join at the end. The last person in line helps us know where to add the next person.

front -> 1 -> 2 -> 3 -> null ← rear
                   ↑rear points here

Dry Run Walkthrough

Input: queue: 1 -> 2 -> 3 -> null, enqueue value 4

Goal: Add value 4 at the end of the queue so it becomes 1 -> 2 -> 3 -> 4 -> null

Step 1: Create new node with value 4 and next null

new_node: 4 -> null

Why: We need a new node to add at the end

Step 2: Link current rear node (3) next to new node (4)

1 -> 2 -> 3 -> [next->4] -> null

Why: Attach new node after the last node

Step 3: Update rear pointer to new node (4)

front -> 1 -> 2 -> 3 -> 4 -> null ← rear

Why: Rear must point to the new last node

Result:

front -> 1 -> 2 -> 3 -> 4 -> null ← rear

Annotated Code

DSA Rust

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

#[derive(Debug)]
struct Queue {
    front: Option<Rc<RefCell<Node>>>,
    rear: Option<Rc<RefCell<Node>>>,
}

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

    fn enqueue(&mut self, val: i32) {
        let new_node = Rc::new(RefCell::new(Node { value: val, next: None }));
        // If queue is empty, front and rear both point to new node
        if self.rear.is_none() {
            self.front = Some(Rc::clone(&new_node));
            self.rear = Some(Rc::clone(&new_node));
            return;
        }
        // Link current rear's next to new node
        if let Some(rear_node) = &self.rear {
            rear_node.borrow_mut().next = Some(Rc::clone(&new_node));
        }
        // Update rear to new node
        self.rear = Some(Rc::clone(&new_node));
    }

    fn print_queue(&self) {
        let mut current = self.front.as_ref().map(Rc::clone);
        while let Some(node) = current {
            print!("{} -> ", node.borrow().value);
            current = node.borrow().next.as_ref().map(Rc::clone);
        }
        println!("null");
    }
}

fn main() {
    let mut queue = Queue::new();
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.print_queue();
    queue.enqueue(4);
    queue.print_queue();
}

let new_node = Rc::new(RefCell::new(Node { value: val, next: None }));

Create new node with given value and next null

if self.rear.is_none() { self.front = Some(Rc::clone(&new_node)); self.rear = Some(Rc::clone(&new_node)); return; }

If queue empty, front and rear point to new node

rear_node.borrow_mut().next = Some(Rc::clone(&new_node));

Link current rear node's next to new node

self.rear = Some(Rc::clone(&new_node));

Update rear pointer to new node

Output

1 -> 2 -> 3 -> null

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(1) because we add the new node directly at the rear without traversing

Space: O(1) because we only create one new node per enqueue

vs Alternative: Compared to adding at front or traversing to end (O(n)), this method is faster because rear pointer avoids traversal

Edge Cases

Empty queue

front and rear both point to the new node

DSA Rust

if self.rear.is_none() { self.front = Some(Rc::clone(&new_node)); self.rear = Some(Rc::clone(&new_node)); return; }

Single element queue

rear's next points to new node and rear updates to new node

DSA Rust

rear_node.borrow_mut().next = Some(Rc::clone(&new_node));

When to Use This Pattern

When you need to add items to the end of a line quickly, use enqueue with a rear pointer to avoid walking through the whole list.

Common Mistakes

Mistake: Not updating the rear pointer after adding the new node
Fix: Always set rear to the new node after linking it

Mistake: Not handling empty queue case separately
Fix: Check if rear is None and set both front and rear to new node

Summary

Adds a new element at the end of a linked list queue efficiently.

Use when you want to keep the order of elements and add new ones at the back quickly.

Keep a rear pointer to avoid traversing the whole list when adding.

Practice

1. What does the enqueue operation do in a linked list implementation of a queue?

easy

A. Adds a new element at the beginning (head) of the linked list

B. Removes the first element from the linked list

C. Adds a new element at the end (tail) of the linked list

D. Deletes the last element from the linked list

Solution

1. Step 1: Understand enqueue operation in queue

   Enqueue means adding an element to the queue, which is done at the end (tail) in a linked list.

2. Step 2: Identify linked list position for enqueue

   In a linked list queue, new nodes are added at the tail to maintain FIFO order.

3. Final Answer:

   Adds a new element at the end (tail) of the linked list -> Option C

4. Quick Check:

   Enqueue = Add at tail [OK]

Hint: Enqueue always adds at the tail in linked list queue [OK]

Common Mistakes:

• Confusing enqueue with dequeue operation
• Adding new element at head instead of tail
• Thinking enqueue removes elements

2. Which of the following Rust code snippets correctly enqueues a new node with value val into a linked list queue?

easy

A. let new_node = Box::new(Node { data: val, next: None }); tail.next = Some(new_node); tail = tail.next.as_mut().unwrap();

B. let new_node = Box::new(Node { data: val, next: None }); head = Some(new_node);

C. let new_node = Box::new(Node { data: val, next: head }); head = Some(new_node);

D. let new_node = Box::new(Node { data: val, next: None }); tail = Some(new_node);

Solution

1. Step 1: Create new node with value and no next

   The new node is created with data = val and next = None, correct for enqueue at tail.

2. Step 2: Link new node at tail and update tail pointer

   Setting tail.next to new_node and moving tail pointer to new_node is correct enqueue logic.

3. Final Answer:

   let new_node = Box::new(Node { data: val, next: None }); tail.next = Some(new_node); tail = tail.next.as_mut().unwrap(); -> Option A

4. Quick Check:

   Enqueue = add at tail and update tail [OK]

Hint: Enqueue updates tail.next and tail pointer [OK]

Common Mistakes:

• Assigning new node to head instead of tail
• Not updating tail pointer after enqueue
• Linking new node's next to head (wrong for enqueue)

3. Given this Rust code snippet for enqueue operation on a linked list queue, what will be the printed queue after enqueuing values 10, 20, 30?

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

struct Queue {
    head: Option,
    tail: *mut Node,
}

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

    fn enqueue(&mut self, val: i32) {
        let mut new_node = Box::new(Node { data: val, next: None });
        let raw_node: *mut _ = &mut *new_node;
        if self.tail.is_null() {
            self.head = Some(new_node);
            self.tail = raw_node;
        } else {
            unsafe { (*self.tail).next = Some(new_node); }
            self.tail = raw_node;
        }
    }

    fn print_queue(&self) {
        let mut current = &self.head;
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = &node.next;
        }
        println!("null");
    }
}

fn main() {
    let mut q = Queue::new();
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.print_queue();
}

medium

A. 30 -> 20 -> 10 -> null

B. 10 -> 20 -> 30 -> null

C. null

D. 10 -> null

Solution

1. Step 1: Trace enqueue calls adding nodes at tail

   Enqueue adds 10, then 20, then 30 at the tail, preserving order.

2. Step 2: Print queue from head to tail

   Prints nodes in order: 10 -> 20 -> 30 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option B

4. Quick Check:

   Enqueue order preserved in print [OK]

Hint: Enqueue adds at tail, print from head shows insertion order [OK]

Common Mistakes:

• Assuming enqueue adds at head, reversing order
• Not updating tail pointer causing print errors
• Printing empty queue due to wrong head initialization

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

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

medium

A. Using unsafe block unnecessarily

B. Not setting new_node.next to None

C. Not updating head pointer when queue is empty

D. Assigning tail pointer to reference of new_node which is dropped after function ends

Solution

1. Step 1: Analyze new_node lifetime

   new_node is a local variable and will be dropped after function ends, so tail pointer becomes invalid.

2. Step 2: Understand pointer assignment issue

   Assigning tail to &mut *new_node stores pointer to dropped memory, causing undefined behavior.

3. Final Answer:

   Assigning tail pointer to reference of new_node which is dropped after function ends -> Option D

4. Quick Check:

   Pointer to dropped node causes bug [OK]

Hint: Tail must point to heap node, not local variable [OK]

Common Mistakes:

• Using local variable reference for tail pointer
• Ignoring unsafe pointer lifetime issues
• Not updating tail pointer at all

5. You want to implement a queue using a singly linked list in Rust that supports enqueue and dequeue efficiently. Which approach correctly handles enqueue operation to maintain O(1) time complexity and safe memory management? A) Add new node at head and update head pointer. B) Add new node at tail, update tail pointer, and use Option for next pointers. C) Add new node at tail but do not update tail pointer. D) Add new node at head and update tail pointer.

hard

A. Add new node at tail, update tail pointer, and use Option for next pointers.

B. Add new node at head and update head pointer.

C. Add new node at tail but do not update tail pointer.

D. Add new node at head and update tail pointer.

Solution

1. Step 1: Understand enqueue efficiency in linked list queue

   Enqueue must add at tail and update tail pointer to keep O(1) time complexity.

2. Step 2: Use Option for safe memory management

   Using Option for next pointers ensures ownership and safe heap allocation in Rust.

3. Step 3: Reject other options

   Adding at head breaks FIFO order; not updating tail pointer breaks enqueue logic.

4. Final Answer:

   Add new node at tail, update tail pointer, and use Option for next pointers. -> Option A

5. Quick Check:

   Enqueue at tail + safe pointers = O(1) enqueue [OK]

Hint: Enqueue at tail with Option ensures O(1) and safety [OK]

Common Mistakes:

• Adding at head breaks queue order
• Not updating tail pointer after enqueue
• Using raw pointers without ownership