Chapter 10: Queue Using Linked List (Java)

Difficulty: Beginner → Intermediate
Prerequisites: Queue Fundamentals, Linked Lists, Java Basics

Learning Objectives

After completing this chapter, you will be able to:

• Understand how a Queue is implemented using a Linked List.
• Learn why a Linked List overcomes the limitations of an array-based Queue.
• Understand the roles of the Front and Rear pointers.
• Implement all Queue operations in Java.
• Analyze time and space complexity.
• Perform dry runs of Queue operations.
• Handle Queue Underflow correctly.
• Answer common Queue interview questions.

Introduction

In previous chapters, we implemented a Queue using:

• Array
• Circular Array

Although these implementations are efficient, they have one limitation:

The maximum size is fixed.

For example:

QueueUsingArray queue = new QueueUsingArray(5);

This Queue can store only 5 elements.

If a sixth element is inserted:

Queue Overflow

A Linked List solves this problem by allocating memory dynamically whenever a new element is inserted.

What is a Queue Using Linked List?

A Queue using a Linked List stores each element inside a Node.

Each node contains:

• Data
• Reference to the next node

Unlike arrays:

• Nodes are not stored continuously in memory.
• Memory is allocated dynamically.
• Queue size grows as needed.

Why Use a Linked List?

Imagine a Queue where thousands of customers arrive.

With an array:

Capacity = 1000

After 1000 insertions:

Queue Overflow

With a Linked List:

Customer1
↓
Customer2
↓
Customer3
↓
...

The Queue continues growing until the available heap memory is exhausted.

Node Structure

Each node stores:

+-----------+
|   Data    |
+-----------+
|   Next    |
+-----------+

Java class:

class Node {

int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Why Do We Need Front and Rear?

Unlike a Stack, a Queue performs operations at both ends.

Front
 ↓
10 → 20 → 30
            ↑
           Rear

• Front removes elements.
• Rear inserts elements.

Internally:

Node front;
Node rear;

Initially

front = null;
rear = null;

Memory Representation

Suppose we insert:

10
20
30

Memory may look like:

Address      Data      Next
5000         10       2000
2000         20       9000
9000         30       NULL

Queue

Front
 ↓
10 → 20 → 30
            ↑
           Rear

Notice:

Nodes can exist anywhere in memory.

Queue Operations

| Operation | Description               |
| --------- | ------------------------- |
| Enqueue   | Insert at Rear            |
| Dequeue   | Remove from Front         |
| Peek      | Return Front element      |
| isEmpty   | Check if Queue is empty   |
| Size      | Return number of elements |
| Display   | Print Queue               |

Enqueue Operation

Insert an element at the Rear.

Current Queue

Front
 ↓
10 → 20
      ↑
     Rear

Execute

enqueue(30);

Step 1

Create new node.

30 → NULL

Step 2

Attach new node to current rear.

rear.next = newNode;

Queue

10 → 20 → 30

Step 3

Move rear.

rear = newNode;

Final Queue

Front
 ↓
10 → 20 → 30
            ↑
           Rear

Enqueue Algorithm

Create New Node

If Queue Empty
    Front = Rear = New Node
Else
    Rear.Next = New Node
    Rear = New Node

Java Implementation of Enqueue

public void enqueue(int value) {

Node newNode = new Node(value);
    if (isEmpty()) {
        front = rear = newNode;
    } else {
        rear.next = newNode;
        rear = newNode;
    }
    size++;
}

Dry Run of Enqueue

Initially

Front = NULL
Rear = NULL

enqueue(10)

Front
 ↓

10
 ↑
Rear

enqueue(20)

Front
 ↓
10 → 20
      ↑
     Rear

enqueue(30)

Front
 ↓
10 → 20 → 30
            ↑
           Rear

Dequeue Operation

Remove the Front node.

Get Pavan Pithdiya’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Current Queue

Front
 ↓
10 → 20 → 30
            ↑
           Rear

Execute

dequeue();

Removed

10

Move front.

front = front.next;

Result

Front
 ↓
20 → 30
      ↑
     Rear

The removed node becomes unreachable and Java’s Garbage Collector (GC) automatically reclaims its memory.

Dequeue Algorithm

If Queue Empty

Underflow
Else
    value = Front.Data
    Front = Front.Next
If Front == NULL
    Rear = NULL
Return value

Java Implementation of Dequeue

public int dequeue() {

if (isEmpty()) {
        System.out.println("Queue Underflow");
        return -1;
    }

    int value = front.data;
    front = front.next;

    if (front == null)
        rear = null;

    size--;
    return value;
}

Peek Operation

Peek returns the Front element.

public int peek() {

if (isEmpty()) {
        System.out.println("Queue is Empty");
        return -1;
    }
    return front.data;
}

isEmpty()

public boolean isEmpty() {
  return front == null;
}

Size Operation

public int size() {
  return size;
}

Display Operation

public void display() {

if (isEmpty()) {
        System.out.println("Queue is Empty");
        return;
    }
    Node current = front;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}

Complete Java Implementation

public class QueueUsingLinkedList {

private static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
    }
    private Node front;
    private Node rear;
    private int size;
    public boolean isEmpty() {
        return front == null;
    }
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue Underflow");
            return -1;
        }
        int value = front.data;
        front = front.next;
        if (front == null)
            rear = null;
        size--;
        return value;
    }
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        return front.data;
    }
    public int size() {
        return size;
    }
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is Empty");
            return;
        }
        Node current = front;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        QueueUsingLinkedList queue = new QueueUsingLinkedList();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.display();
        System.out.println("Front: " + queue.peek());
        System.out.println("Removed: " + queue.dequeue());
        queue.display();
        System.out.println("Size: " + queue.size());
    }
}

Sample Output

10 20 30
Front: 10
Removed: 10
20 30
Size: 2

Dry Run

Initial

Front = NULL
Rear = NULL

enqueue(10)

Front
 ↓
10
 ↑
Rear

enqueue(20)

Front
 ↓
10 → 20
      ↑
     Rear

enqueue(30)

Front
 ↓
10 → 20 → 30
            ↑
           Rear

dequeue()

Removed

10

Queue

Front
 ↓
20 → 30
      ↑
     Rear

peek()

20

Edge Cases

Queue Underflow

Queue

[]

Calling

dequeue();

Output

Queue Underflow

Queue with One Element

Queue

Front
 ↓
10
 ↑
Rear

After

dequeue();

Both pointers become:

Front = NULL
Rear  = NULL

This ensures the Queue correctly returns to the empty state.

Large Queue

Unlike an array-based Queue, a Linked List Queue continues growing dynamically until the JVM runs out of heap memory.

Time Complexity

| Operation | Time Complexity                         |
| --------- | --------------------------------------- |
| Enqueue   | **O(1)**                                |
| Dequeue   | **O(1)**                                |
| Peek      | **O(1)**                                |
| isEmpty   | **O(1)**                                |
| Size      | **O(1)** *(when maintained as a field)* |
| Search    | **O(n)**                                |
| Display   | **O(n)**                                |

Space Complexity

Each node stores:

• Data
• Reference to the next node

For n elements:

Space Complexity = O(n)

Array Queue vs Circular Queue vs Linked List Queue

| Feature           | Array Queue | Circular Queue | Linked List Queue             |
| ----------------- | ----------- | -------------- | ----------------------------- |
| Memory Allocation | Fixed       | Fixed          | Dynamic                       |
| Overflow          | Yes         | Yes            | Only when memory is exhausted |
| Memory Wastage    | Yes         | No             | No                            |
| Enqueue           | O(1)        | O(1)           | O(1)                          |
| Dequeue           | O(1)        | O(1)           | O(1)                          |
| Extra Memory      | No          | No             | One reference per node        |
| Cache Performance | Better      | Better         | Slightly worse                |

Advantages

• Dynamic size.
• No fixed capacity.
• No memory wastage.
• Fast enqueue and dequeue operations.
• Well-suited when the maximum Queue size is unknown.

Disadvantages

• Extra memory is required for node references.
• Nodes are scattered in memory, reducing cache locality.
• More object allocations than an array-based implementation.

Real-World Applications

• Print spoolers
• Task scheduling systems
• Message queues
• Event-driven systems
• Breadth-First Search (BFS)
• Operating system process scheduling
• Network packet processing
• Customer service systems

Common Interview Questions

1. Why does a Queue implemented with a Linked List require both front and rear pointers?
2. Why is enqueue() O(1)?
3. What happens if you don’t update rear after removing the last element?
4. Why doesn’t a Linked List Queue have a traditional Queue Overflow?
5. Compare Array Queue, Circular Queue, and Linked List Queue.
6. What is the role of the Garbage Collector after dequeue()?
7. Why is a Linked List Queue preferred when the queue size is unknown?

Common Mistakes

• Forgetting to update rear when the last node is removed.
• Traversing the entire list during enqueue() instead of maintaining a rear pointer.
• Accessing front.data without checking if the queue is empty.
• Forgetting to increment or decrement the size field.

Best Practices

• Maintain both front and rear pointers to keep enqueue() and dequeue() at O(1).
• Keep a separate size field for constant-time size retrieval.
• Always reset both pointers to null when the queue becomes empty.
• Use a Linked List Queue when the maximum number of elements is not known in advance.

Chapter Summary

• A Queue using a Linked List stores elements as dynamically allocated nodes connected by references.
• It maintains front and rear pointers to ensure both enqueue() and dequeue() run in O(1) time.
• Unlike an array-based queue, it has no fixed-capacity limitation and does not waste memory by leaving unused positions.
• The trade-off is a small memory overhead for storing node references and slightly lower cache efficiency.
• This implementation is ideal for applications where the queue size is unpredictable and can grow dynamically.

Next Chapter

Chapter 11 — Java Queue Interface (java.util.Queue)

In the next chapter, you’ll learn:

• What is the Queue interface?
• The relationship between Queue, Deque, and concrete implementations.
• LinkedList, ArrayDeque, and PriorityQueue as Queue implementations.
• Methods such as offer(), poll(), peek(), add(), remove(), and element().
• Differences between methods that throw exceptions and those that return special values.
• Best practices and interview questions related to the Java Collections Framework.