Queue Implementation Using Linked List in DSA Rust - Build from Scratch

Queue Implementation Using Linked List

📖 Scenario: You are building a simple queue system like a line at a grocery store. People join the line at the end and leave from the front. You will use a linked list to keep track of who is in line.

🎯 Goal: Create a queue using a linked list in Rust. You will add people to the queue, remove them in order, and then show who is left in the queue.

📋 What You'll Learn

Create a linked list node struct called Node with a value and a next pointer

Create a Queue struct with front and rear pointers

Implement enqueue to add a value to the rear of the queue

Implement dequeue to remove a value from the front of the queue

Print the queue contents after operations

💡 Why This Matters

🌍 Real World

Queues are used in real life to manage lines, like waiting for a bus or processing tasks in order.

💼 Career

Understanding queue implementation helps in jobs involving system design, backend development, and managing data flow efficiently.

1

Create the Node and Queue structs

Create a struct called Node with a field value: i32 and a field next: Option>. Then create a struct called Queue with two fields: front: Option> and rear: Option<*mut Node>.

DSA Rust

// Define Node and Queue structs here
// Your code here

Hint

Use Option> for the next pointer to allow for empty or next nodes. Use a raw pointer *mut Node for the rear to allow mutable access.

2

Add a new empty queue constructor

Add an impl Queue block with a function new() that returns an empty Queue with front and rear set to None.

DSA Rust

impl Queue {
    // Add new() function here
    // Your code here
}

Hint

The new() function creates an empty queue with no nodes.

3

Implement enqueue to add values

Inside impl Queue, add a function enqueue(&mut self, value: i32) that creates a new Node with the given value and adds it to the rear of the queue. Update front and rear pointers accordingly.

DSA Rust

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

    // Add enqueue function here
    // Your code here
}

Hint

Use a raw pointer for rear to update the last node's next safely inside an unsafe block.

4

Implement dequeue and print the queue

Add a function dequeue(&mut self) -> Option that removes the front node and returns its value. Then write a print_queue(&self) function that prints all values in the queue separated by arrows like 1 -> 2 -> 3 -> None. Finally, create a main function that creates a queue, enqueues 10, 20, 30, dequeues one value, and prints the queue.

DSA Rust

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

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

        if self.rear.is_none() {
            self.front = Some(new_node);
            self.rear = Some(raw_node);
        } else {
            unsafe {
                (*self.rear.unwrap()).next = Some(new_node);
            }
            self.rear = Some(raw_node);
        }
    }

    // Add dequeue function here
    // Add print_queue function here
}

fn main() {
    // Create queue, enqueue 10, 20, 30
    // Dequeue one value
    // Print queue
    // Your code here
}

Hint

Use take() on front to remove the first node safely. Update rear to None if queue becomes empty. Print all values with arrows and end with None.

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