Enqueue Using Linked List in DSA C++

Mental Model

Add a new item at the end of a chain of connected boxes, so the line grows from the back.

Analogy: Imagine people standing in a line waiting for ice cream. When a new person arrives, they join at the end of the line, not in the middle or front.

front -> [1] -> [2] -> [3] -> null
rear ↑

Dry Run Walkthrough

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

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

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

front -> [1] -> [2] -> [3] -> null
rear ↑    [4] -> null

Why: We need a new box to hold the new value at the end

Step 2: Link the current rear node's next pointer to the new node

front -> [1] -> [2] -> [3] -> [4] -> null
rear ↑                 [4]

Why: Connect the last box in the line to the new box

Step 3: Update rear pointer to point to the new node

front -> [1] -> [2] -> [3] -> [4] -> null
rear ↑                       [4]

Why: Rear must always point to the last box in the line

Result:

front -> [1] -> [2] -> [3] -> [4] -> null
rear ↑                       [4]

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class Queue {
private:
    Node* front;
    Node* rear;
public:
    Queue() : front(nullptr), rear(nullptr) {}

    void enqueue(int val) {
        Node* newNode = new Node(val); // create new node
        if (rear == nullptr) { // empty queue
            front = rear = newNode; // front and rear both point to new node
            return;
        }
        rear->next = newNode; // link last node to new node
        rear = newNode; // update rear to new node
    }

    void printQueue() {
        Node* temp = front;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "null" << endl;
    }
};

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.printQueue();
    return 0;
}

Node* newNode = new Node(val); // create new node

create a new node to hold the new value

if (rear == nullptr) { // empty queue front = rear = newNode; // front and rear both point to new node return; }

handle empty queue by setting front and rear to new node

rear->next = newNode; // link last node to new node

connect current rear node to new node

rear = newNode; // update rear to new node

move rear pointer to new last node

Output

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

Complexity Analysis

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

Space: O(1) because we only create one new node for each enqueue operation

vs Alternative: Compared to using an array where adding at the end might require resizing or shifting, linked list enqueue is faster and uses constant time

Edge Cases

empty queue

front and rear both point to the new node, starting the queue

DSA C++

if (rear == nullptr) { front = rear = newNode; return; }

single element queue

new node is linked after the single node, rear updated

DSA C++

rear->next = newNode; rear = newNode;

When to Use This Pattern

When you need to add items to the end of a line efficiently, use enqueue with a linked list to keep track of the last item and add in constant time.

Common Mistakes

Mistake: Not updating the rear pointer after adding the new node
Fix: Always set rear = newNode after linking the new node

Mistake: Not handling the empty queue case, causing null pointer errors
Fix: Check if rear is null and set front and rear to newNode in that case

Summary

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

Use when you want fast insertion at the end without shifting elements.

Keep track of the rear pointer to add new nodes in constant time.

Practice

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

easy

A. Adds an element at the end (rear) of the linked list

B. Removes an element from the front of the linked list

C. Deletes the entire linked list

D. Adds an element at the front (head) of the linked list

Solution

1. Step 1: Understand enqueue operation in queue

   Enqueue means adding an element to the queue.

2. Step 2: Identify linked list position for enqueue

   In a linked list queue, enqueue adds at the rear (end) to maintain FIFO order.

3. Final Answer:

   Adds an element at the end (rear) of the linked list -> Option A

4. Quick Check:

   Enqueue = Add at rear [OK]

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

Common Mistakes:

• Confusing enqueue with dequeue operation
• Adding element at front instead of rear
• Thinking enqueue removes elements

2. Which of the following is the correct syntax to create a new node and enqueue it in a linked list queue in C++?

easy

A. Node* temp = Node(data); rear->next = temp; rear = temp;

B. Node temp = new Node(data); rear->next = temp; rear = temp;

C. Node* temp = new Node(data); rear->next = temp; rear = temp;

D. Node* temp = new Node; rear->next = temp; rear = temp;

Solution

1. Step 1: Check node creation syntax in C++

   Correct way to create a node dynamically is Node* temp = new Node(data);.

2. Step 2: Verify linking and updating rear pointer

   Link new node by rear->next = temp; and update rear to new node rear = temp;.

3. Final Answer:

   Node* temp = new Node(data); rear->next = temp; rear = temp; -> Option C

4. Quick Check:

   Use new with pointer and update rear [OK]

Hint: Use 'new' keyword and pointer for node creation [OK]

Common Mistakes:

• Not using pointer (*) for node
• Missing 'new' keyword for dynamic allocation
• Incorrect assignment without pointers

3. What will be the state of the queue after executing the following enqueue operations on an empty linked list queue?

enqueue(10); enqueue(20); enqueue(30);

medium

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

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

C. null -> 10 -> 20 -> 30

D. 20 -> 30 -> 10 -> null

Solution

1. Step 1: Enqueue 10 on empty queue

   Queue becomes 10 -> null.

2. Step 2: Enqueue 20 and 30 sequentially

   Adding 20 at rear: 10 -> 20 -> null; then 30 at rear: 10 -> 20 -> 30 -> null.

3. Final Answer:

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

4. Quick Check:

   FIFO order maintained: 10, 20, 30 [OK]

Hint: Enqueue adds at rear, order stays same [OK]

Common Mistakes:

• Reversing order of elements
• Confusing enqueue with push front
• Ignoring null termination

4. Identify the error in the following enqueue function for a linked list queue:

void enqueue(int data) {
  Node* temp = new Node(data);
  if (rear == nullptr) {
    front = temp;
  } else {
    rear->next = temp;
  }
  // Missing update of rear pointer here
}

medium

A. rear pointer is not updated to the new node

B. front pointer should be updated to temp always

C. Node creation syntax is incorrect

D. next pointer of temp should be set to front

Solution

1. Step 1: Check rear pointer update after enqueue

   rear pointer must point to the newly added node to keep track of queue end.

2. Step 2: Identify missing update in code

   Code misses rear = temp; after linking new node.

3. Final Answer:

   rear pointer is not updated to the new node -> Option A

4. Quick Check:

   rear must update to new node [OK]

Hint: Always update rear to new node after enqueue [OK]

Common Mistakes:

• Forgetting to update rear pointer
• Updating front pointer incorrectly
• Setting next pointer wrongly

5. Given a linked list queue with elements 5 -> 15 -> 25 -> null, what will be the queue state after enqueueing 35 and then dequeueing one element?

hard

A. 35 -> 5 -> 15 -> 25 -> null

B. 5 -> 15 -> 25 -> 35 -> null

C. 25 -> 35 -> null

D. 15 -> 25 -> 35 -> null

Solution

1. Step 1: Enqueue 35 at rear

   Queue becomes 5 -> 15 -> 25 -> 35 -> null.

2. Step 2: Dequeue removes front element 5

   After dequeue, front moves to 15, so queue is 15 -> 25 -> 35 -> null.

3. Final Answer:

   15 -> 25 -> 35 -> null -> Option D

4. Quick Check:

   Enqueue rear, dequeue front; update pointers accordingly [OK]

Hint: Enqueue rear, dequeue front; update pointers accordingly [OK]

Common Mistakes:

• Removing wrong element on dequeue
• Not updating front pointer after dequeue
• Adding new element at front instead of rear