Enqueue Using Linked List in DSA C++ - Build from Scratch

Enqueue Using Linked List

📖 Scenario: Imagine you are managing a line of customers waiting to buy tickets. You want to add new customers to the end of the line efficiently. This line is represented using a linked list where each node holds a customer's ID.

🎯 Goal: You will build a simple linked list queue and add new customers to the end using the enqueue operation.

📋 What You'll Learn

Create a Node struct with an integer data and a pointer to the next Node

Create a Queue class with pointers to the front and rear nodes

Implement an enqueue method to add a new node at the rear

Print the queue contents after enqueue operations

💡 Why This Matters

🌍 Real World

Queues are used in real life to manage lines, like customers waiting, print jobs, or tasks waiting to be processed.

💼 Career

Understanding linked list queues is important for software developers working on systems that require efficient data processing and task scheduling.

1

Create Node struct and Queue class with front and rear pointers

Create a struct Node with an int data and a Node* next. Then create a class Queue with public Node* front and Node* rear pointers initialized to nullptr in the constructor.

DSA C++

// Define struct Node with int data and Node* next
// Define class Queue with Node* front and Node* rear initialized to nullptr
// Your code here

Hint

Use a constructor inside Node to set data and initialize next to nullptr. In Queue, set front and rear to nullptr in the constructor.

2

Add enqueue method to Queue class

Inside the Queue class, add a public method void enqueue(int val) that creates a new Node with val. If rear is nullptr, set both front and rear to the new node. Otherwise, set rear->next to the new node and update rear to the new node.

DSA C++

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

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

    // Implement enqueue method here
    // Your code here
};

Hint

Remember to handle the case when the queue is empty by setting both front and rear to the new node. Otherwise, link the new node at the end and update rear.

3

Create main function and enqueue values

Write a main function that creates a Queue object called q. Use q.enqueue(10), q.enqueue(20), and q.enqueue(30) to add these values to the queue.

DSA C++

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

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

    void enqueue(int val) {
        Node* newNode = new Node(val);
        if (rear == nullptr) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
    }
};

int main() {
    // Create Queue object q
    // Enqueue 10, 20, 30
    // Your code here
}

Hint

Create the queue object and call enqueue three times with the values 10, 20, and 30.

4

Print the queue contents after enqueue

In the main function, after enqueueing, use a Node* pointer called temp to traverse from q.front to nullptr. Print each node's data followed by " -> ". After the loop, print "null".

DSA C++

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

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

    void enqueue(int val) {
        Node* newNode = new Node(val);
        if (rear == nullptr) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    // Traverse and print queue
    // Your code here

    return 0;
}

Hint

Use a while loop to move through the linked list starting at q.front. Print each data followed by " -> ". After the loop, print "null".

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