Enqueue Using Linked List in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does 'enqueue' mean in the context of a queue data structure?

Enqueue means adding an element to the end (rear) of the queue.

beginner

Why is a linked list useful for implementing enqueue operation in a queue?

A linked list allows adding elements at the end efficiently without shifting elements, unlike arrays.

beginner

In enqueue using linked list, which pointer usually moves when a new element is added?

The 'rear' pointer moves to point to the newly added node at the end of the linked list.

intermediate

What happens if the queue is empty when we perform enqueue using a linked list?

Both 'front' and 'rear' pointers are set to the new node because it is the only element.

intermediate

Show the steps to enqueue an element '5' in a queue implemented with a linked list having elements 1 -> 2 -> 3 -> null.

1. Create a new node with value 5.
2. Set current rear node's next to new node.
3. Move rear pointer to new node.
Result: 1 -> 2 -> 3 -> 5 -> null

What pointer is updated when enqueueing a new element in a linked list queue?

A Rear pointer

B Front pointer

C Head pointer

D Tail pointer of the previous node only

The rear pointer moves to the new node added at the end.

If the queue is empty, what happens during enqueue?

A Only rear pointer is updated

B Only front pointer is updated

C No pointers are updated

D Both front and rear pointers point to the new node

When empty, both front and rear point to the new node as it is the only element.

What is the time complexity of enqueue operation using linked list?

A O(n)

B O(log n)

C O(1)

D O(n^2)

Enqueue is O(1) because we add at the rear directly without traversal.

Which of the following is NOT true about enqueue using linked list?

A Front pointer always moves

B Rear pointer moves to new node

C If empty, front and rear point to new node

D New node is added at the end

Front pointer only moves when dequeue happens, not during enqueue unless queue was empty.

What does the linked list node contain in a queue implementation?

A Data only

B Data and pointer to next node

C Pointer to previous node only

D Data and pointer to previous node

Each node stores data and a pointer to the next node.

Explain how enqueue operation works in a queue implemented using a linked list.

Think about what happens when the queue is empty versus when it has elements.

Describe the state of the queue after enqueueing elements 1, 2, and 3 in order using a linked list.

Visualize the linked list nodes and pointers after each enqueue.

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