Queue Implementation Using Linked List in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after enqueue and dequeue operations?

Consider a queue implemented using a linked list. The following operations are performed in order:

enqueue(10), enqueue(20), dequeue(), enqueue(30), dequeue()

What is the printed state of the queue after these operations?

DSA Java

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

class Queue {
    Node front, rear;

    void enqueue(int x) {
        Node temp = new Node(x);
        if (rear == null) {
            front = rear = temp;
            return;
        }
        rear.next = temp;
        rear = temp;
    }

    int dequeue() {
        if (front == null) return -1;
        int val = front.data;
        front = front.next;
        if (front == null) rear = null;
        return val;
    }

    void printQueue() {
        Node temp = front;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.print("null");
    }
}

public class Main {
    public static void main(String[] args) {
        Queue q = new Queue();
        q.enqueue(10);
        q.enqueue(20);
        q.dequeue();
        q.enqueue(30);
        q.dequeue();
        q.printQueue();
    }
}

A 20 -> 30 -> null

B 10 -> 20 -> 30 -> null

C null

D 30 -> null

💡 Hint

Trace each operation step-by-step, updating the front and rear pointers.

After enqueue(10) and enqueue(20), queue is 10 -> 20 -> null. dequeue() removes 10, queue is 20 -> null. enqueue(30) adds 30 at rear, queue is 20 -> 30 -> null. dequeue() removes 20, queue is 30 -> null.

🧠 Conceptual

intermediate

What happens when dequeue is called on an empty queue?

In a queue implemented using a linked list, what is the expected behavior when the dequeue operation is called but the queue is empty?

A Returns -1 indicating the queue is empty

B Removes the last element in the queue

C Throws a NullPointerException

D Adds a new node with value 0

💡 Hint

Check the dequeue method's return value when front is null.

The dequeue method checks if front is null and returns -1 to indicate the queue is empty, avoiding exceptions.

🔧 Debug

advanced

Identify the bug in this enqueue method

The following enqueue method is intended to add a new element to the rear of the queue. What is the bug that will cause incorrect behavior?

DSA Java

void enqueue(int x) {
    Node temp = new Node(x);
    if (front == null) {
        front = temp;
    }
    rear.next = temp;
    rear = temp;
}

A rear.next will cause NullPointerException when queue is empty

B front is not updated when queue is empty

C rear is not updated after adding new node

D temp node is not created properly

💡 Hint

Consider what happens when rear is null and you try to access rear.next.

When the queue is empty, rear is null. Accessing rear.next causes NullPointerException. The code should check if rear is null before accessing rear.next.

📝 Syntax

advanced

Which option will cause a syntax error in Java?

Given the following snippet from a queue implementation, which option contains a syntax error?

DSA Java

Node temp = new Node(x);
if (rear == null) {
    front = rear = temp;
    return;
}
rear.next = temp;
rear = temp;

A

Node temp = new Node(x);
if (rear == null) {
    front = rear = temp;
    return;
}
rear.next = temp;
rear = temp;

B

Node temp = new Node(x)
if (rear == null) {
    front = rear = temp;
    return;
}
rear.next = temp;
rear = temp;

C

Node temp = new Node(x);
if (rear == null) {
    front = rear = temp
    return;
}
rear.next = temp;
rear = temp;

D

Node temp = new Node(x);
if (rear == null) {
    front = rear = temp;
    return;
}
rear.next = temp
rear = temp;

💡 Hint

Look for missing semicolons in Java statements.

Option B is missing a semicolon after 'new Node(x)', causing a syntax error.

🚀 Application

expert

What is the time complexity of enqueue and dequeue in linked list queue?

For a queue implemented using a linked list with pointers to front and rear, what is the time complexity of enqueue and dequeue operations respectively?

A Enqueue: O(n), Dequeue: O(1)

B Enqueue: O(1), Dequeue: O(n)

C Enqueue: O(1), Dequeue: O(1)

D Enqueue: O(n), Dequeue: O(n)

💡 Hint

Consider how pointers to front and rear help in adding/removing nodes.

With pointers to front and rear, enqueue adds at rear in O(1), dequeue removes from front in O(1). No traversal needed.

Practice

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

easy

A. Dynamic size, no fixed limit on queue length

B. Faster access to elements by index

C. Uses less memory than arrays

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 allows dynamic size

   Linked lists can grow or shrink as needed, so queues using linked lists have no fixed size limit.

3. Final Answer:

   Dynamic size, no fixed limit on queue length -> Option A

4. Quick Check:

   Linked list queue size = dynamic [OK]

Hint: Linked list queues grow dynamically, arrays do not [OK]

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed with size flexibility
• Assuming linked lists are simpler to implement

2. Which of the following is the correct way to declare a node class for a linked list queue in Java?

easy

A. class Node { int data; int next; }

B. class Node { int data; Node prev; }

C. class Node { Node data; Node next; }

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

Solution

1. Step 1: Identify node fields for linked list queue

   A node should store data and a reference to the next node.

2. Step 2: Check each option's correctness

   class Node { int data; Node next; } has int data and Node next, which is correct. Others have incorrect types or missing next pointer.

3. Final Answer:

   class Node { int data; Node next; } -> Option D

4. Quick Check:

   Node stores data + next pointer [OK]

Hint: Node must link to next node, not previous or int [OK]

Common Mistakes:

• Using 'prev' pointer instead of 'next' for queue node
• Declaring next as int instead of Node
• Using Node type for data field

3. What will be the output after executing the following code snippet for a linked list queue?

Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.enqueue(30);
q.display();

Assuming display() prints elements front to rear separated by ' -> ' and ends with ' -> null'.

medium

A. 20 -> 30 -> null

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

C. 30 -> null

D. 20 -> null

Solution

1. Step 1: Trace enqueue and dequeue operations

   Enqueue 10: queue = 10
   Enqueue 20: queue = 10 -> 20
   Dequeue: removes 10, queue = 20
   Enqueue 30: queue = 20 -> 30

2. Step 2: Display queue elements

   Queue elements front to rear are 20 followed by 30, so output is '20 -> 30 -> null'.

3. Final Answer:

   20 -> 30 -> null -> Option A

4. Quick Check:

   After dequeue, front is 20, then 30 [OK]

Hint: Dequeue removes front; enqueue adds rear [OK]

Common Mistakes:

• Not removing the first element on dequeue
• Appending new elements at front instead of rear
• Confusing order of elements in display

4. Identify the error in this dequeue method of a linked list queue:

public int dequeue() {
  if (front == null) {
    System.out.println("Queue is empty");
    return -1;
  }
  int value = front.data;
  front = front.next;
  if (front == null) {
    rear = null;
  }
  return value;
}

medium

A. Should update rear before front

B. No error, method works correctly

C. Returns wrong value after dequeue

D. Does not handle empty queue properly

Solution

1. Step 1: Check empty queue handling

   Method checks if front is null and returns -1 with message, which is correct.

2. Step 2: Check updating front and rear pointers

   After removing front node, front is updated to next node. If front becomes null, rear is also set to null. This is correct to keep queue consistent.

3. Final Answer:

   No error, method works correctly -> Option B

4. Quick Check:

   Dequeue updates front and rear properly [OK]

Hint: Set rear null only if front becomes null after dequeue [OK]

Common Mistakes:

• Not setting rear to null when queue becomes empty
• Returning wrong value after dequeue
• Not checking for empty queue before dequeue

5. You want to implement a method reverseQueue() that reverses the order of elements in a linked list queue without using extra data structures. Which approach is best?

hard

A. Create a new linked list and enqueue elements in reverse order

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

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

D. Use a stack to store elements and then enqueue back

Solution

1. Step 1: Understand constraints

   We cannot use extra data structures like stack or new linked list, so options C and D are invalid.

2. Step 2: Evaluate remaining options

   Traverse linked list and swap data of front and rear nodes repeatedly swaps data repeatedly but is inefficient and complex. Use recursion to dequeue elements and enqueue them back in reverse order uses recursion to dequeue all elements, then enqueue them back in reverse order, effectively reversing the queue without extra structures.

3. Final Answer:

   Use recursion to dequeue elements and enqueue them back in reverse order -> Option C

4. Quick Check:

   Recursion reverses queue without extra structures [OK]

Hint: Recursion can reverse queue without extra storage [OK]

Common Mistakes:

• Using extra data structures despite constraints
• Trying to swap node data instead of rearranging nodes
• Not handling empty or single-element queue cases