## 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.