A queue is a FIFO (First In, First Out) data structure where elements are added at the rear and removed from the front. While a queue can be implemented using a fixed-size array, backing it with a linked list removes the capacity constraint — the queue grows and shrinks dynamically as elements are enqueued and dequeued.
In this post, we implement a queue using a singly linked list in Java, supporting enqueue, dequeue, peek, and display operations.
Java Program: Queue Using Linked List
import java.io.*;
// A single node in the linked list backing the queue
class QueueNode {
int data;
QueueNode next; // Pointer to the next node (towards the rear)
public QueueNode(int value) {
data = value;
next = null;
}
}
// Queue backed by a singly linked list
class LinkedQueue {
QueueNode front = null; // Front of queue (next to be dequeued)
QueueNode rear = null; // Rear of queue (last enqueued)
// Returns true if the queue has no elements
public boolean isEmpty() {
return (front == null || rear == null);
}
// Adds an element to the rear of the queue
public void enqueue(int value) {
QueueNode newNode = new QueueNode(value);
if (isEmpty()) {
front = rear = newNode; // First element: both pointers to same node
} else {
rear.next = newNode; // Link current rear to new node
rear = newNode; // Advance rear to new node
}
}
// Removes and returns the front element
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty - nothing to dequeue");
return -1;
}
int value = front.data;
front = front.next; // Advance front; old head is garbage-collected
return value;
}
// Returns the front element without removing it
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty - nothing to peek");
return -1;
}
return front.data;
}
// Displays all elements from front to rear
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
QueueNode current = front;
System.out.print("Queue (front to rear): ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class QueueUsingLinkedList {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int choice;
LinkedQueue queue = new LinkedQueue();
do {
System.out.println();
System.out.println("--- Queue (Linked List) Menu ---");
System.out.println("1. Enqueue (add element)");
System.out.println("2. Dequeue (remove element)");
System.out.println("3. Peek (front element)");
System.out.println("4. Display queue");
System.out.println("5. Exit");
System.out.print("Enter choice: ");
choice = Integer.parseInt(reader.readLine());
switch (choice) {
case 1:
System.out.print("Enter element to enqueue: ");
int element = Integer.parseInt(reader.readLine());
queue.enqueue(element);
System.out.println("Enqueued: " + element);
break;
case 2:
int removed = queue.dequeue();
if (removed != -1) System.out.println("Dequeued element: " + removed);
break;
case 3:
int peeked = queue.peek();
if (peeked != -1) System.out.println("Front element: " + peeked);
break;
case 4:
queue.display();
break;
case 5:
System.out.println("Exiting...");
break;
default:
System.out.println("Invalid choice");
}
} while (choice != 5);
}
}
How the Code Works
- QueueNode class — Each node holds an integer
dataand anextpointer to the node behind it in the queue (toward the rear). - enqueue() — Creates a new node and appends it to the rear. The
rearpointer is updated to the new node. On an empty queue, bothfrontandrearpoint to the single new node. - dequeue() — Saves the front node’s data, advances
fronttofront.next, and returns the saved value. The old front node is eligible for garbage collection. - peek() — Returns
front.datawithout modifying the queue. Useful for inspecting what will be dequeued next. - display() — Traverses from
frontthrough allnextpointers, printing elements in FIFO order. - No capacity limit — Unlike an array-based queue, this implementation grows dynamically. It is limited only by available heap memory.
Sample Output
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 1
Enter element to enqueue: 10
Enqueued: 10
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 1
Enter element to enqueue: 20
Enqueued: 20
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 1
Enter element to enqueue: 30
Enqueued: 30
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 1
Enter element to enqueue: 40
Enqueued: 40
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 4
Queue (front to rear): 10 20 30 40
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 3
Front element: 10
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 2
Dequeued element: 10
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 2
Dequeued element: 20
--- Queue (Linked List) Menu ---
1. Enqueue (add element)
2. Dequeue (remove element)
3. Peek (front element)
4. Display queue
5. Exit
Enter choice: 4
Queue (front to rear): 30 40Output Explanation
- Elements 10, 20, 30, 40 are enqueued in order. The queue display confirms FIFO order (10 is at the front).
- Peek returns 10 (the front) without removing it.
- After dequeuing 10 and 20, the remaining queue starts at 30, confirming FIFO removal order.
See Also
- Implementation of Circular Queue in Java with Array — Fixed-size queue with true circular wraparound
- Implementing Circular Queue in Java with Arrays — Alternate circular queue implementation
- Implementation of Stack using Linked List in Java — Stack also backed by a linked list
- Implementing Singly Linked List in Java — The underlying data structure used here
Conclusion
A linked list-backed queue provides an unbounded, dynamic FIFO collection — ideal when the number of elements is unknown at design time. Both enqueue and dequeue are O(1) operations because we maintain direct pointers to both front and rear nodes. This is the foundation for many real-world queue implementations, including thread pools and message broker buffers.
Any idea how can i write a search method in the linked list to search plz?
java provides implementation for all abstract data types such as Stack , Queue and LinkedList but it is always good idea to understand basic data structures and implement them yourself.