Implementing a Queue Using a Linked List in Java

When it comes to data structures, queues are a fundamental concept that often comes in handy for various applications. A queue operates on the principle of First In, First Out (FIFO), where the first element added to the queue will be the first one to be removed. In this article, we’ll dive into implementing a queue using a linked list in Java, providing you with clear examples, step-by-step instructions, and actionable insights.

What is a Queue?

A queue is a linear data structure that allows you to store and manage data in a sequential manner. Unlike arrays or other collections, queues excel in scenarios where order matters, such as handling tasks in a scheduling system or processing requests in a server environment.

Key Characteristics of a Queue

• FIFO Structure: The first element added is the first one to be removed.
• Dynamic Size: Unlike arrays, the size of a queue can grow and shrink dynamically.
• Enqueue and Dequeue Operations: The primary operations are adding (enqueue) and removing (dequeue) elements.

Why Use a Linked List for a Queue?

Using a linked list to implement a queue has several advantages:

• Dynamic Memory Allocation: Unlike arrays, linked lists do not require a predefined size, allowing for more flexibility.
• Efficient Insertions and Deletions: Inserting or removing elements from a linked list can be done in constant time, O(1), especially at the front and rear.
• No Wasted Space: Unlike an array that might allocate more space than needed, linked lists utilize memory more efficiently.

Implementing a Queue with a Linked List in Java

Let's break down the implementation into manageable steps.

Step 1: Create the Node Class

The first step is to create a Node class that will represent each element in the queue.

class Node {
    int data;
    Node next;

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

Step 2: Create the Queue Class

Next, we’ll create the Queue class. This class will have methods for enqueueing, dequeueing, and checking if the queue is empty.

class Queue {
    private Node front;
    private Node rear;
    private int size;

    public Queue() {
        front = null;
        rear = null;
        size = 0;
    }

Step 3: Enqueue Operation

The enqueue method will add an element to the rear of the queue.

    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
        System.out.println(data + " enqueued to queue");
    }

Step 4: Dequeue Operation

The dequeue method will remove and return the front element of the queue.

    public int dequeue() {
        if (front == null) {
            throw new IllegalStateException("Queue is empty");
        }
        int data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        System.out.println(data + " dequeued from queue");
        return data;
    }

Step 5: Check if the Queue is Empty

We need a method to check if the queue is empty.

    public boolean isEmpty() {
        return size == 0;
    }

Step 6: Size of the Queue

To keep track of the number of elements in the queue, we can add a method to return the size.

    public int size() {
        return size;
    }
}

Complete Queue Implementation

Here’s the complete Queue class:

class Queue {
    private Node front;
    private Node rear;
    private int size;

    public Queue() {
        front = null;
        rear = null;
        size = 0;
    }

    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
        System.out.println(data + " enqueued to queue");
    }

    public int dequeue() {
        if (front == null) {
            throw new IllegalStateException("Queue is empty");
        }
        int data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        System.out.println(data + " dequeued from queue");
        return data;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
}

Step 7: Testing the Queue

Finally, let’s 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);

        System.out.println(queue.dequeue() + " dequeued from queue");
        System.out.println("Queue size: " + queue.size());
    }
}

Use Cases for Queues

Queues are used in various domains, including but not limited to:

• Task Scheduling: Managing tasks in operating systems.
• Print Queue Management: Handling print jobs in printers.
• Service Requests: Managing requests in web servers.

Conclusion

Implementing a queue using a linked list in Java is a powerful way to manage data efficiently. With the dynamic nature of linked lists, you’re equipped to handle varying data sizes without the constraints of static arrays. By following the steps outlined in this article, you can create a robust queue system tailored to your needs.

Don’t hesitate to experiment with the implementation, add more functionalities, or optimize the code further. Happy coding!