How to Implement a Queue Using Linked List

Introduction

Queues are an essential data structure in computer science, and they can be implemented in various ways. In this guide, we will focus on how to implement a queue using a linked list in Java. By the end of this article, you’ll understand the fundamentals of a queue, how linked lists work, and how to Implement a Queue Using Linked List.

What is a Queue?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. It is like a line of people waiting for service—those who arrive first are served first.

Key Operations of a Queue:

• Enqueue: Add an element to the end of the queue.
• Dequeue: Remove an element from the front of the queue.
• Peek/Front: Retrieve the front element without removing it.
• IsEmpty: Check if the queue is empty.

Why Use a Linked List for Queue Implementation?

Using a linked list to implement a queue has some advantages over using arrays:

• Dynamic Size: Unlike arrays, linked lists can grow and shrink in size, allowing for more flexibility.
• No Memory Wastage: Memory is allocated as needed, so there is no waste like in fixed-size arrays.

How to Implement a Queue Using a Linked List in Java

Let’s create a queue using a singly linked list. We will define a Node class to represent each element and a Queue class to manage the queue operations.

Step 1: Define the Node Class

The Node class will represent each element in the queue. Each node stores data and a reference to the next node.

class Node {
    int data;
    Node next;

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

Step 2: Define the Queue Class

The Queue class will manage the queue’s operations, keeping references to both the front and rear nodes for efficient enqueue and dequeue operations.

class Queue {
    Node front, rear;

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

Step 3: Enqueue Operation

The enqueue method adds a new node to the end of the queue. If the queue is empty, the new node becomes both the front and the rear.

void enqueue(int value) {
    Node newNode = new Node(value);

    if (rear == null) {
        front = rear = newNode;
        System.out.println(value + " enqueued to the queue.");
        return;
    }

    rear.next = newNode;
    rear = newNode;
    System.out.println(value + " enqueued to the queue.");
}

Step 4: Dequeue Operation

The dequeue method removes the front node from the queue. If the queue becomes empty after dequeuing, update the rear to null.

int dequeue() {
    if (front == null) {
        System.out.println("Queue is empty. Cannot dequeue.");
        return Integer.MIN_VALUE;
    }

    int dequeuedValue = front.data;
    front = front.next;

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

    System.out.println(dequeuedValue + " dequeued from the queue.");
    return dequeuedValue;
}

Step 5: Peek Operation

The peek method retrieves the front element without removing it.

int peek() {
    if (front == null) {
        System.out.println("Queue is empty. No elements to peek.");
        return Integer.MIN_VALUE;
    }
    return front.data;
}

Step 6: IsEmpty Method

Check if the queue is empty by verifying if front is null.

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

Step 7: Main Method to Test the Queue

Now, let’s add a main method to test our queue implementation.

public class Main {
    public static void main(String[] args) {
        Queue queue = new Queue();

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);

        System.out.println("Front element is: " + queue.peek());

        queue.dequeue();
        queue.dequeue();

        queue.enqueue(50);

        System.out.println("Front element is: " + queue.peek());
    }
}

Output:

10 enqueued to the queue.
20 enqueued to the queue.
30 enqueued to the queue.
40 enqueued to the queue.
Front element is: 10
10 dequeued from the queue.
20 dequeued from the queue.
50 enqueued to the queue.
Front element is: 30

Explanation of the Queue Operations

• Enqueue: Adds a new node at the rear of the queue and adjusts the rear pointer.
• Dequeue: Removes the front node and adjusts the front pointer. If the queue becomes empty, set rear to null.
• Peek: Returns the data of the front node without removing it.
• IsEmpty: Checks if front is null to determine if the queue is empty

Benefits of Using Linked Lists for Queue Implementation

• Dynamic Size: The queue size can increase as needed without worrying about a fixed capacity.
• Efficient Memory Usage: Nodes are created only when needed, reducing memory overhead.
• No Need for Shifting Elements: Unlike arrays, there is no need to shift elements during enqueue or dequeue operations.

Limitations of Linked List-Based Queues

• Extra Memory for Pointers: Each node requires additional memory for storing a pointer to the next node.
• Access Time: Linked lists can be slower for certain operations compared to arrays due to pointer traversal.

Conclusion

Implementing a queue using a linked list in Java is ideal for scenarios where a dynamic size is required. By following this guide, you now have a working implementation that is efficient and easy to understand. Whether you are preparing for coding interviews or building projects, mastering this data structure will be a valuable asset.