Queue Using Linked List
A queue can also be implemented using a linked list, giving dynamic size. We maintain two pointers: `front` (head) and `rear` (tail). Enqueue adds at rear, dequeue removes from front.
Linked list-based queue implementation
public class LinkedListQueue<T> {
private static class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; }
}
private Node<T> front;
private Node<T> rear;
private int size;
public void enqueue(T item) {
Node<T> newNode = new Node<>(item);
if (isEmpty()) {
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
size++;
}
public T dequeue() {
if (isEmpty()) throw new RuntimeException("Queue underflow");
T data = front.data;
front = front.next;
if (front == null) rear = null;
size--;
return data;
}
public T front() {
if (isEmpty()) throw new RuntimeException("Queue empty");
return front.data;
}
public boolean isEmpty() {
return front == null;
}
public int size() {
return size;
}
}
Two Minute Drill
- Linked list queue uses front and rear pointers.
- Enqueue: O(1), dequeue: O(1).
- Dynamic size, no overflow (except memory).
- Each element consumes extra memory for the next pointer.
Need more clarification?
Drop us an email at career@quipoinfotech.com