How to Implement a Queue Using Linked List in Java

Queues are fundamental data structures used in various applications, from handling requests in web servers to managing tasks in multi-threaded environments. Unlike arrays, which have a fixed size, linked lists provide a dynamic way to manage data. In this article, we will explore how to implement a queue using a linked list in Java. We will cover definitions, use cases, and provide actionable insights with clear code examples.

Understanding Queues

A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are widely used in scenarios such as:

• Task scheduling: Managing tasks in operating systems.
• Order processing: Handling requests in e-commerce systems.
• Data buffering: Managing data in streaming applications.

Key Operations of a Queue

1. Enqueue: Add an element to the end of the queue.
2. Dequeue: Remove an element from the front of the queue.
3. Peek: View the front element without removing it.
4. isEmpty: Check if the queue is empty.

Why Use Linked Lists for Queues?

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

• Dynamic Size: Unlike arrays, linked lists can grow and shrink in size as needed.
• Efficient Memory Usage: Memory is allocated only when required, reducing waste.
• No Shifting: Elements can be added or removed without shifting other elements, making operations faster.

Implementing a Queue Using Linked List in Java

Let's walk through implementing a queue using a singly linked list in Java.

Step 1: Create the Node Class

First, we need to define a Node class that will represent each element in the queue.

class Node {
    int data; // Data part of the node
    Node next; // Pointer to the next node

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

Step 2: Create the Queue Class

Next, we will create a Queue class that uses the Node class to implement the queue functionalities.

class Queue {
    private Node front; // Pointer to the front of the queue
    private Node rear;  // Pointer to the rear of the queue

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

    // Enqueue operation
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = rear = newNode; // Queue is empty
            return;
        }
        rear.next = newNode; // Link new node at the end
        rear = newNode; // Update rear
    }

    // Dequeue operation
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int data = front.data; // Get data from front
        front = front.next; // Move front to next node
        if (front == null) {
            rear = null; // If queue is empty, update rear
        }
        return data;
    }

    // Peek operation
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.data; // Return front data
    }

    // Check if the queue is empty
    public boolean isEmpty() {
        return front == null;
    }
}

Step 3: Testing the Queue Implementation

Now that we have our queue implementation, let’s test it with some sample operations.

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

        // Enqueue elements
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);

        // Peek at the front element
        System.out.println("Front element is: " + queue.peek());

        // Dequeue elements
        System.out.println("Dequeued: " + queue.dequeue());
        System.out.println("Dequeued: " + queue.dequeue());

        // Check if the queue is empty
        System.out.println("Is queue empty? " + queue.isEmpty());

        // Dequeue the last element
        System.out.println("Dequeued: " + queue.dequeue());

        // Check if the queue is empty
        System.out.println("Is queue empty? " + queue.isEmpty());
    }
}

Explanation of the Code

• Node Class: Each Node contains data and a pointer to the next node.
• Queue Class: It maintains pointers to the front and rear of the queue.
• Enqueue Method: Adds a new node at the rear. If the queue is empty, both front and rear point to the new node.
• Dequeue Method: Removes a node from the front. If the queue becomes empty after this operation, rear is also set to null.
• Peek Method: Returns the data at the front without removing it.
• isEmpty Method: Checks if the queue is empty.

Troubleshooting Common Issues

When implementing a queue with a linked list, you might encounter some common issues:

• NullPointerException: This can occur if you try to dequeue from an empty queue. Always check if the queue is empty before performing dequeue operations.
• Memory Leaks: Ensure that nodes are properly dereferenced when they are removed to avoid memory leaks.

Conclusion

Implementing a queue using a linked list in Java is a straightforward process that provides a flexible and efficient way to manage data. By following the steps outlined in this article, you can create a robust queue implementation that can be used in various applications. Whether you're handling tasks in a multi-threaded environment or managing requests in a server, mastering this data structure will enhance your programming skills and problem-solving abilities. Happy coding!