Enqueue Using Linked List in DSA Rust - Execution Trace

Concept Flow - Enqueue Using Linked List

Create new node with value

↓

Is queue empty?

Yes→Set head and tail to new node

No↓

Set tail.next to new node

↓

Update tail to new node

↓

Done

This flow shows how a new node is created and added at the end of the linked list representing the queue.

Execution Sample

DSA Rust

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

fn enqueue(tail: &mut Option<Box<Node>>, value: i32) {
    // Add new node at tail
}

This code snippet shows the structure of a node and a function to add a new node at the end of the linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with value 10	None	None	null
2	Check if queue is empty	None	None	null
3	Queue empty: set head and tail to new node	10 -> null	head = new_node, tail = new_node	10 -> null
4	Create new node with value 20	10 -> null	None	10 -> null
5	Check if queue is empty	10 -> null	None	10 -> null
6	Queue not empty: set tail.next to new node	10 -> 20 -> null	tail.next = new_node	10 -> 20 -> null
7	Update tail to new node	10 -> 20 -> null	tail = new_node	10 -> 20 -> null
8	Create new node with value 30	10 -> 20 -> null	None	10 -> 20 -> null
9	Check if queue is empty	10 -> 20 -> null	None	10 -> 20 -> null
10	Queue not empty: set tail.next to new node	10 -> 20 -> 30 -> null	tail.next = new_node	10 -> 20 -> 30 -> null
11	Update tail to new node	10 -> 20 -> 30 -> null	tail = new_node	10 -> 20 -> 30 -> null
12	End of enqueue operations	10 -> 20 -> 30 -> null	tail points to node with value 30	10 -> 20 -> 30 -> null

💡 All enqueue operations complete, tail updated to last node.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	Final
head	None	Node(10)	Node(10)	Node(10)	Node(10)
tail	None	Node(10)	Node(20)	Node(30)	Node(30)
list nodes	empty	10 -> null	10 -> 20 -> null	10 -> 20 -> 30 -> null	10 -> 20 -> 30 -> null

Key Moments - 3 Insights

Why do we need to check if the queue is empty before adding a new node?

Because if the queue is empty, both head and tail must point to the new node. This is shown in step 3 of the execution_table where head and tail are set to the new node when the list is empty.

Why do we update tail.next before moving tail to the new node?

Updating tail.next links the current last node to the new node, maintaining the chain. Then tail is updated to point to the new last node. This is shown in steps 6 and 7.

What happens if we forget to update the tail pointer after enqueue?

The tail pointer would still point to the old last node, breaking the queue's structure for future enqueues. This is why step 7 updates tail to the new node.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what change happens to the pointers?

A head is updated to the new node

B tail is set to None

C tail.next is set to the new node

D head.next is set to the new node

💡 Hint

Check the 'Pointer Changes' column at step 6 in the execution_table.

At which step does the queue change from empty to having one node?

A Step 1

B Step 3

C Step 5

D Step 7

💡 Hint

Look for when head and tail are first set to the new node in the execution_table.

If we skip updating tail in step 7, what will be the state of tail after enqueueing the second node?

A tail points to the first node

B tail points to the second node

C tail is None

D tail points to the third node

💡 Hint

Refer to the 'Pointer Changes' and 'Visual State' columns in steps 6 and 7.

Concept Snapshot

Enqueue Using Linked List:
- Create new node with value
- If queue empty: head and tail = new node
- Else: tail.next = new node, tail = new node
- Maintains FIFO order
- Tail always points to last node
- Head points to first node

Full Transcript

Enqueue operation in a linked list queue involves creating a new node with the given value. If the queue is empty, both head and tail pointers are set to this new node. Otherwise, the current tail's next pointer is set to the new node, and then the tail pointer is updated to this new node. This process maintains the order of elements in the queue, ensuring FIFO behavior. The execution table shows step-by-step how nodes are added and pointers updated. Key moments clarify why checking for empty queue and updating tail pointer are essential. The visual quiz tests understanding of pointer changes and queue state transitions.

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