A queue serves elements in FIFO order (First In, First Out): elements join at the rear (tail) and leave from the front (head).
A singly linked list with two references fits this perfectly: front points to the first node, where elements are removed, and rear points to the last node, where elements are added. Both operations change only one or two references, so they run in O(1), and the queue has no fixed capacity.
Operations in Queue
Enqueue: add an element at the rear.
Dequeue: remove the element at the front.
Peek or front: return the front element without removing it.
rear: return the rear element without removing it.
isFull: not needed here; a linked-list queue grows until memory runs out.
isEmpty: tell whether the queue has no elements (
front == null).
Example: Queue Implementation using Linked List in Java
Class: Node
class Node {
int data; // Store value
Node next; // Store address of next node
// Initializing a node with data in the constructor
public Node(int data) {
this.data = data;
this.next = null;
}
}
Class: LinkedListQueue
// A queue of int values built on a singly linked list
class LinkedListQueue {
private Node front; // first node: elements are removed here
private Node rear; // last node: elements are added here
boolean isEmpty() {
return front == null;
}
// Adds an element at the rear: O(1)
void enqueue(int data) {
Node node = new Node(data);
if (rear == null) {
// empty queue: the new node is both front and rear
front = rear = node;
return;
}
rear.next = node;
rear = node;
}
// Removes the element at the front: O(1)
void dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty.");
return;
}
front = front.next;
if (front == null) {
// the queue is now empty, so rear must not keep the old node
rear = null;
}
}
// Returns the front element (the queue must not be empty)
int getFront() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return front.data;
}
// Returns the rear element (the queue must not be empty)
int getRear() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return rear.data;
}
// Prints the elements from front to rear without changing the queue
void printQueue() {
for (Node current = front; current != null; current = current.next) {
System.out.print(current.data + " ");
}
System.out.println();
}
}
public class QueueImplUsingLinkedList {
public static void main(String[] args) {
LinkedListQueue queue = new LinkedListQueue();
queue.enqueue(10);
queue.enqueue(20);
System.out.println("Queue Front: " + queue.getFront());
System.out.println("Queue Rear: " + queue.getRear());
queue.dequeue();
queue.dequeue();
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
System.out.println("Queue Front: " + queue.getFront());
System.out.println("Queue Rear: " + queue.getRear());
System.out.println("Queue elements: ");
queue.printQueue();
}
}
Queue Front: 10 Queue Rear: 20 Queue Front: 30 Queue Rear: 50 Queue elements: 30 40 50