Java Queue Implementations: LinkedList vs PriorityQueue

Java Queue Implementations: LinkedList vs PriorityQueue

✅ Queue Interface Overview

Found in java.util.

Follows FIFO (First-In-First-Out) principle.

Common methods:

• add(e) / offer(e) – add element
• remove() / poll() – remove head
• element() / peek() – view head

🔹 LinkedList as a Queue

• Implements List, Deque, and Queue interfaces.
• Can be used as both a Queue and Deque (Double-ended Queue).
• Maintains insertion order.
• Allows null elements.
• Time complexity: O(1) for insertion/removal at ends.

📌 Example:

Queue<String> queue = new LinkedList<>();
queue.add("A");
queue.add("B");
queue.add("C");

System.out.println(queue.poll()); // A
System.out.println(queue.peek()); // B

🔹 PriorityQueue

• Implements Queue interface.
• Elements are ordered by natural order (Comparable) or a custom Comparator.
• Does NOT guarantee FIFO — head is always the least (or highest priority) element.
• Does NOT allow null elements.
• Time complexity: O(log n) for insertion and removal (backed by a binary heap).

📌 Example (Natural Order):

Queue<Integer> pq = new PriorityQueue<>();
pq.add(30);
pq.add(10);
pq.add(20);

System.out.println(pq.poll()); // 10 (lowest comes first)

📌 Example (Custom Comparator - Max Heap):

Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(30);
pq.add(10);
pq.add(20);

System.out.println(pq.poll()); // 30 (highest first)

🔁 Quick Comparison

Feature	LinkedList	PriorityQueue
Order	Insertion (FIFO)	Priority-based
Null allowed	✅ Yes	❌ No
Thread-safe	❌ No	❌ No
Use case	Simple queue/deque	Scheduling, task queue
Performance	O(1) insert/remove	O(log n) insert/remove