Queue Implementation Using Linked List in DSA Java

Mental Model

A queue is like a line where the first person in is the first person out. Using a linked list means each person holds a pointer to the next person.

Analogy: Imagine a line of people waiting to buy tickets. The first person to join the line is the first to get the ticket and leave. Each person knows who is behind them, but not the whole line.

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

Dry Run Walkthrough

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

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

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

front -> [10] -> null
rear ↑

Why: First element added, so front and rear both point to it

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

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

Why: Add new element at rear, update rear pointer

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

front -> [20] -> null
rear ↑

Why: Remove element from front, update front pointer

Result:

front -> [20] -> null
rear ↑

Annotated Code

DSA Java

public class QueueUsingLinkedList {
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    static class Queue {
        Node front, rear;

        public Queue() {
            this.front = this.rear = null;
        }

        // Add element at rear
        void enqueue(int data) {
            Node newNode = new Node(data);
            if (rear == null) {
                front = rear = newNode; // first element
                return;
            }
            rear.next = newNode; // link new node at end
            rear = newNode; // move rear pointer
        }

        // Remove element from front
        int dequeue() {
            if (front == null) {
                return -1; // queue empty
            }
            int value = front.data; // store front data
            front = front.next; // move front pointer
            if (front == null) {
                rear = null; // queue became empty
            }
            return value;
        }

        // Print queue from front to rear
        void printQueue() {
            Node temp = front;
            while (temp != null) {
                System.out.print(temp.data + " -> ");
                temp = temp.next;
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        Queue q = new Queue();
        q.enqueue(10);
        q.enqueue(20);
        q.printQueue();
        int removed = q.dequeue();
        System.out.println("Dequeued: " + removed);
        q.printQueue();
    }
}

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

handle empty queue by setting front and rear to new node

rear.next = newNode; rear = newNode;

link new node at rear and update rear pointer

if (front == null) { rear = null; }

if queue becomes empty after dequeue, reset rear pointer

front = front.next;

move front pointer to next node to remove front element

Output

10 -> 20 -> null

Dequeued: 10

20 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we only update pointers without traversing the list

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 more flexible in size

Edge Cases

dequeue from empty queue

returns -1 indicating queue is empty, no error occurs

DSA Java

if (front == null) { return -1; }

enqueue first element when queue is empty

front and rear both point to the new node

DSA Java

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

dequeue last element making queue empty

front becomes null and rear is reset to null

DSA Java

if (front == null) { rear = null; }

When to Use This Pattern

When you need a first-in-first-out structure with dynamic size and efficient add/remove, use a linked list queue to avoid costly shifts.

Common Mistakes

Mistake: Not updating rear pointer after enqueue, causing incorrect queue end
Fix: Always move rear pointer to the new node after linking

Mistake: Not resetting rear to null when queue becomes empty after dequeue
Fix: Check if front is null after dequeue and set rear to null

Mistake: Trying to dequeue from empty queue without check, causing errors
Fix: Check if front is null before dequeue and handle empty case

Summary

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

Use when you want a queue that grows dynamically without fixed size limits and efficient operations.

The key is to keep track of both front and rear pointers to add and remove elements in constant time.

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