Queue Implementation Using Linked List in DSA C++

Mental Model

A queue is like a line where people join at the back and leave from the front. Using a linked list means each person knows who is next, so we can add or remove quickly.

Analogy: Imagine a line at a coffee shop. New customers join at the end, and the barista serves the customer at the front. Each customer holds the hand of the next one, so the line stays connected.

front -> [node1] -> [node2] -> [node3] -> null ← rear
↑front pointer          ↑rear pointer

Dry Run Walkthrough

Input: Start with empty queue, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements are added at rear and removed from front using linked list

Step 1: enqueue 10: create node with 10, front and rear point to it

front -> [10] -> null ← rear
↑front ↑rear

Why: First element sets both front and rear pointers

Step 2: enqueue 20: create node with 20, link rear.next to it, move rear to new node

front -> [10] -> [20] -> null ← rear
↑front           ↑rear

Why: Add new element at rear and update rear pointer

Step 3: dequeue: remove node at front (10), move front to next node (20)

front -> [20] -> null ← rear
↑front           ↑rear

Why: Remove from front to maintain queue order

Step 4: enqueue 30: create node with 30, link rear.next to it, move rear to new node

front -> [20] -> [30] -> null ← rear
↑front           ↑rear

Why: Add new element at rear and update rear pointer

Result:

front -> [20] -> [30] -> null ← rear
↑front           ↑rear

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) { // queue empty
            front = rear = newNode; // front and rear point to new node
            return;
        }
        rear->next = newNode; // link new node at rear
        rear = newNode; // move rear pointer
    }

    void dequeue() {
        if (!front) return; // queue empty, nothing to remove
        Node* temp = front; // store front node
        front = front->next; // move front pointer
        if (!front) rear = nullptr; // if queue becomes empty, rear also null
        delete temp; // free old front node
    }

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

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.dequeue();
    q.enqueue(30);
    q.display();
    return 0;
}

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

create new node with given value

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

if queue empty, front and rear point to new node

rear->next = newNode; rear = newNode;

link new node at rear and update rear pointer

if (!front) return;

check if queue is empty before dequeue

Node* temp = front; front = front->next;

remove front node by moving front pointer

if (!front) rear = nullptr;

if queue empty after dequeue, set rear to nullptr

delete temp;

free memory of removed node

while (temp) { cout << temp->data << " -> "; temp = temp->next; }

traverse and print all nodes from front to rear

Output

20 -> 30 -> null

Complexity Analysis

Time: O(1) for enqueue and dequeue because we add or remove nodes directly at rear or front without traversal

Space: O(n) because each element is stored in a separate node linked together

vs Alternative: Compared to array-based queue, linked list avoids shifting elements on dequeue, making operations faster and memory usage dynamic

Edge Cases

dequeue from empty queue

nothing happens, no error, queue remains empty

DSA C++

if (!front) return;

enqueue first element into empty queue

front and rear both point to the new node

DSA C++

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

dequeue last element leaving queue empty

front becomes nullptr and rear also set to nullptr

DSA C++

if (!front) rear = nullptr;

When to Use This Pattern

When you need a first-in-first-out (FIFO) structure with dynamic size and fast insert/remove at ends, use a linked list queue to avoid costly shifts.

Common Mistakes

Mistake: Not updating rear pointer when enqueueing new node
Fix: Always move rear pointer to the new node after linking it

Mistake: Not setting rear to nullptr when queue becomes empty after dequeue
Fix: Check if front is nullptr after dequeue and set rear to nullptr to avoid dangling pointer

Summary

Implements a queue using a linked list where elements are added at rear and removed from front.

Use when you want a queue with dynamic size and efficient enqueue and dequeue operations.

The key is to keep track of both front and rear pointers to add and remove nodes in O(1) time.

Practice

1. What is the main advantage of implementing a queue using a linked list instead of an array?

easy

A. Dynamic size without fixed capacity

B. Faster access to middle elements

C. Uses less memory always

D. Simpler to implement than arrays

Solution

1. Step 1: Understand queue size limitation in arrays

   Arrays have fixed size, so queues implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic size

   Linked lists can grow or shrink dynamically, so queues using linked lists do not have fixed capacity limits.

3. Final Answer:

   Dynamic size without fixed capacity -> Option A

4. Quick Check:

   Linked list queues grow dynamically = D [OK]

Hint: Linked list queues grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking linked lists use less memory always
• Confusing access speed advantages
• Assuming linked lists are simpler to implement

2. Which of the following is the correct way to declare a node structure for a queue using a linked list in C++?

easy

A. struct Node { int data; Node* next; };

B. struct Node { int data; Node next; };

C. struct Node { int data; Node* prev; };

D. struct Node { int data; int next; };

Solution

1. Step 1: Understand node structure for linked list

   A node must contain data and a pointer to the next node.

2. Step 2: Analyze options

   struct Node { int data; Node* next; }; correctly uses a pointer to next node. struct Node { int data; Node next; }; uses next as object, which is invalid. struct Node { int data; Node* prev; }; uses prev pointer, which is for doubly linked list. struct Node { int data; int next; }; uses int for next, which is incorrect.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option A

4. Quick Check:

   Node with data and next pointer = A [OK]

Hint: Node must have pointer to next node, not object or int [OK]

Common Mistakes:

• Using object instead of pointer for next
• Confusing singly and doubly linked list nodes
• Using int instead of pointer for next

3. What will be the output after performing these operations on an empty queue implemented using linked list?

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

Print the queue elements from front to rear.

medium

A. 20 -> 30 -> null

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

C. 30 -> null

D. 10 -> 30 -> null

Solution

1. Step 1: Perform enqueue(10) and enqueue(20)

   Queue becomes: 10 -> 20 -> null

2. Step 2: Perform dequeue()

   Removes 10, queue becomes: 20 -> null

3. Step 3: Perform enqueue(30)

   Queue becomes: 20 -> 30 -> null

4. Step 4: Perform dequeue()

   Removes 20, queue becomes: 30 -> null

5. Final Answer:

   30 -> null -> Option C

6. Quick Check:

   After operations queue front is 30 [OK]

Hint: Track enqueue/dequeue stepwise to find final queue [OK]

Common Mistakes:

• Forgetting to remove front on dequeue
• Appending dequeue element instead of removing
• Mixing order of operations

4. Identify the error in this dequeue function for a queue implemented using linked list:

int dequeue() {
  if (front == nullptr) return -1;
  Node* temp = front;
  front = front->next;
  int val = temp->data;
  delete temp;
  return val;
}

medium

A. No error, function is correct

B. Does not update rear when queue becomes empty

C. Deletes front node before accessing data

D. Returns wrong value after deletion

Solution

1. Step 1: Analyze dequeue steps

   Function removes front node and returns its data correctly.

2. Step 2: Check rear pointer update

   If after dequeue front becomes nullptr (empty queue), rear should also be set to nullptr but this is missing.

3. Final Answer:

   Does not update rear when queue becomes empty -> Option B

4. Quick Check:

   Rear must be nullptr if queue empty [OK]

Hint: Update rear to nullptr when queue becomes empty [OK]

Common Mistakes:

• Ignoring rear pointer update on empty queue
• Deleting node before reading data
• Returning wrong value after deletion

5. You want to implement a function reverseQueue() that reverses the elements of a queue implemented using a linked list without using extra arrays or STL containers. Which approach is best?

hard

A. Use recursion to dequeue elements and enqueue them back in reverse order

B. Traverse linked list and swap data of front and rear nodes repeatedly

C. Create a new linked list and insert elements at front while dequeuing

D. Use two pointers to reverse links between nodes iteratively

Solution

1. Step 1: Understand reversing linked list nodes

   Reversing links between nodes iteratively changes the queue order without extra space.

2. Step 2: Analyze options

   Use recursion to dequeue elements and enqueue them back in reverse order uses recursion but may use call stack (extra space). Traverse linked list and swap data of front and rear nodes repeatedly swaps data but is inefficient and complex. Create a new linked list and insert elements at front while dequeuing creates new list (extra space). Use two pointers to reverse links between nodes iteratively reverses links in place efficiently.

3. Final Answer:

   Use two pointers to reverse links between nodes iteratively -> Option D

4. Quick Check:

   In-place link reversal is best for linked list queue reverse [OK]

Hint: Reverse links in place with two pointers for best solution [OK]

Common Mistakes:

• Using extra arrays or containers
• Swapping data instead of links
• Using recursion causing extra space